The family the Fibonacci numbers belong to

Fibonacci Nim is one heap and one clause: a move may take any number of counters, except that after the first move it may not take more than twice what the previous player took. The heaps the opening player loses are exactly the Fibonacci numbers, and the winning move is the smallest term of the heap’s Zeckendorf representation.

That is one of the prettiest results in the impartial theory and the heap is not the position established it and then named what nobody had asked:

The first rung out is the factor. Two is arbitrary: a rule allowing at most c times the previous move gives a different game for each c, and the losing positions for c = 1 and c = 3 are two different integer sequences.

They are, and so are the ones for four, five, six, seven and eight. Laying them out side by side changes what the Fibonacci result looks like.

Eight games from one clause #

The census runs each factor’s recursion to twenty thousand counters and records every heap from which the opener loses. The recursion is the same one in every case — a state is a heap and a cap, and the mover wins if some legal take leaves the opponent a losing state — with the two in twice the previous move replaced by c times.

At c = 1 the losing heaps are the powers of two. The rule take at most as much as the last player took means the takes can only shrink, and a heap of 2ᵏ is exactly the heap a player cannot break down without handing over a smaller power. Fifteen of them fit under twenty thousand.

At c = 2 they are the Fibonacci numbers, and the census asserts it: a run in which the losing heaps stopped being 1, 2, 3, 5, 8, 13 would stop the build rather than quietly report a different sequence.

At c = 3 they are 1, 2, 3, 4, 6, 8, 11, 15, 21, 29, 40, 55, 76. At c = 4, 1, 2, 3, 4, 5, 7, 9, 12, 15, 19, 24. Every one of them starts with a run of consecutive integers and then thins out, and the thinning is what a factor buys: a larger factor lets a player take more, so more heaps are winnable and the losses are rarer.

Each of them has a rule #

A sequence of losing positions with no description is a table. The Fibonacci result is famous because it is not a table — the sequence has a two-line recurrence and a numeral system attached to it.

Every factor’s sequence here has a recurrence of the same shape, a(n) = a(n−1) + a(n−j) for some lag j, and the census finds it by trying every lag up to thirty and every starting index, and checking it over every remaining term.

At c = 2 the lag is two, which is the Fibonacci recurrence. At c = 3 it is four, at c = 4 it is six, at c = 5 it is eight.

That is a pattern with an obvious statement: the lag is twice one less than the factor. It gets the Fibonacci case right, it gets three more right, and it is the kind of formula that would make the whole family as tidy as its second member.

Where the pattern stops #

At c = 6 the pattern predicts a lag of ten. The lag is eleven.

At c = 7 it predicts twelve and the lag is fourteen. At c = 8 it predicts fourteen and the lag is seventeen.

So 2(c − 1) is right for four consecutive factors and wrong for the next three, and the census asserts that too — a sweep in which the rule held everywhere would stop the build, because the essay would then be about a different set of numbers.

The true lags run 1, 2, 4, 6, 8, 11, 14, 17. The differences between them are 1, 2, 2, 2, 3, 3, 3, which is a pattern of its own and one this page will not extrapolate: three factors is not enough to say the next three differences are four, and the sweep stops at eight because the ninth factor’s sequence is too sparse for a recurrence to be confirmed over enough terms.

Each recurrence starts late, which is worth reading rather than skipping. At c = 8 the rule does not begin holding until the thirty-first term. Every one of these sequences opens with a run of consecutive integers — a heap of six is lost at c = 6 because there is nothing clever to do with six counters when a player may take five — and the structural part of the sequence begins only once the factor stops being larger than the heaps.

That is the ordinary shape of an impartial sequence and it is the same shape an octal game’s Grundy sequence has: a prefix of exceptions and then a rule, with the length of the prefix the awkward part. The difference is that here the prefix is describable — it is the integers up to about the factor — and there it usually is not.

The golden ratio was never about gold #

The most-repeated fact about Fibonacci Nim is that the golden ratio turns up in it, and the family says exactly what that fact is worth.

A sequence satisfying a(n) = a(n−1) + a(n−j) grows like the real root of x^j = x^(j−1) + 1. At j = 2 that equation is x² = x + 1, whose root is φ, and φ is therefore the growth rate of the c = 2 losing heaps.

At j = 4 the root is 1.3803. At j = 6 it is 1.2852. At j = 8, 1.2321.

So there is one constant per game and one of them has a name. The golden ratio is in Fibonacci Nim because the lag is two, and the lag is two because the factor is two; it is not a sign that the game has anything to do with pentagons, sunflowers or the proportions of a rectangle. Wythoff’s game gets its golden ratio from a genuinely different place — a Beatty sequence rather than a recurrence — and the two coincidences are unrelated, which is worth knowing before either is used as evidence for the other.

That is the honest reading and it makes the c = 2 case less remarkable rather than more. What survives is that the constant is computable from the rule, which is a stronger statement about the family than any single value of it.

What a numeral system would be #

The other half of the Fibonacci result is the move rule: from a winning heap, take the smallest term of the Zeckendorf representation — the unique way of writing the heap as a sum of non-consecutive Fibonacci numbers.

The same machinery exists for every member of the family. A sequence growing under a(n) = a(n−1) + a(n−j) gives a greedy representation with its own non-adjacency condition: no j consecutive terms, rather than no two. So there is a c = 3 numeral system, a c = 4 numeral system, and so on, each with the losing heaps of its own game as digits.

This page has not checked that the move rule transfers, and the reason is the honest one: the representation exists and the theorem that the smallest term is a winning move is a separate claim requiring its own induction. What the census establishes is the sequences and their recurrences; the move rule at c = 2 is checked elsewhere on this site over three hundred heaps, and the same check on c = 3 is a piece of work rather than a corollary.

What the state has to carry #

The rung below’s finding is what makes the whole family well posed, and it is worth restating in the family’s terms because the answer changes with the factor.

A Fibonacci Nim position is not a heap. It is a heap and the cap the previous move left, and the rung below measures how many distinct states a heap of forty can be in. Change the factor and the number of states changes: at c = 1 a heap of n can be reached with caps 1 up to n, at c = 8 the caps jump in eights and the reachable set is sparser near the top and denser near the bottom.

That is why the family is a family of games rather than a family of sequences. A sequence of integers with a recurrence is a piece of arithmetic; what makes each of these a game is that the recursion runs over pairs, and the losing heaps are the heaps whose opening state is lost. A reader who reads the table of sequences as eight number patterns has read the interesting part out of it.

It also bounds what this page could have done. Sweeping to twenty thousand counters is affordable exactly because the pair (heap, cap) memoises, and a factor of nine would need a wider sweep to confirm its recurrence over enough terms — which is where the cost, rather than the mathematics, stops the census.

Why a bigger factor makes a duller game #

There is a trend in the family worth naming because it says where the interesting members are.

As the factor grows the losing heaps get denser at the start and sparser at the end. At c = 8 the first eight heaps are all losses — a heap of at most eight counters cannot be opened safely, because the opener must leave something and the responder may take eight times it — and after that the losses thin out to a growth rate of 1.13.

A game whose losing positions have density approaching zero is a game the opener nearly always wins, and a game the opener nearly always wins is not much of a game. So the family has a sweet spot and it is at small factors, which is presumably why the literature stopped at two: c = 1 is a game where the takes only shrink and is easy to see through, c = 2 is the one with a memorable answer, and everything above is a smooth degradation.

That is a judgement about interest rather than a result, and it comes with a caution. The opener nearly always wins says nothing about how hard the winning move is to find, and at c = 8 the recurrence does not start until the thirty-first term, so the region where a player has to think is larger rather than smaller.

What makes a numeral system, and what makes it work #

The phrase numeral system is doing real work in the last two sections and it is worth pinning down, because the family’s whole result turns on which of its two properties is the load-bearing one.

A greedy numeral system is a sequence $a_1 < a_2 < \dots$ such that every positive integer has a representation as a sum of distinct terms, obtained by repeatedly taking the largest term that fits. Every increasing sequence starting at 1 whose terms grow slowly enough gives one, and that is cheap — it needs no theorem and no property of the game.

What is not cheap is the separation condition: the statement that greedy representations never use two terms too close together in the sequence. Zeckendorf’s theorem is exactly that for the Fibonacci numbers — no two consecutive terms — and it is the half that does the work, because it is what bounds the size of the smallest term used against the whole number.

That bound is what makes the game come out. A winning move takes the smallest term of the representation, and the position is safe afterwards precisely when the next term the opponent could reach is too large for the cap the move leaves. So the condition being checked is not “these numbers form a numeral system” but “the gap in the condition is at least as large as the cap the rule imposes”, and those are different statements about different objects.

Which is why the recurrence is a red herring and the move rule is not. A sequence’s recurrence describes how it grows; the separation condition describes how its greedy representations behave; and the cap is a fact about the rule of the game. Two of those three have to match for the family result to hold, and the one that does not enter is the recurrence — which is the quantity this page has been using to describe the family throughout.

What the census does not say #

Four limits.

Eight factors and twenty thousand counters. The sweep stops at eight because the ninth sequence has too few terms below the bound for a recurrence over thirty candidate lags to mean anything. Nothing here says the lag pattern’s differences continue 4, 4, 4.

A recurrence found is not a recurrence proved. Each is checked over every term the sweep found past the index it starts at — thirty-five terms at c = 6, thirty-seven at c = 8 — and that is evidence rather than proof. A sequence that satisfies a linear recurrence for thirty-five terms and then stops is not a thing anybody has seen here, and it is not excluded.

Only one shape of recurrence was tried. a(n) = a(n−1) + a(n−j) is the shape the Fibonacci case has, and every factor in the sweep is fitted by one. A factor fitted by nothing of that shape would have been reported as having no rule, and the census refuses to build if one turns up — but a sequence with a different shape of rule and no rule of this shape would look, from here, like a failure.

And the move rule is not part of this. Everything above is about which heaps are lost. The winning move from a heap that is not lost is a separate question, answered for c = 2 and open here for the rest.

The convention, named #

Normal play, one heap, and a player unable to move loses — which here means the player facing an empty heap.

The opening move may take any number of counters except the whole heap, which is the standard convention and is what makes a heap of one a loss for the opener. Every later move may take at most ⌊c·t⌋ counters, where t is what the previous player took; the floor matters only for non-integer factors and every factor here is a whole number.

A losing heap is one from which the player to move loses under perfect play by both. The census computes them by the recursion on the pair (heap, cap), which is the state the rung below identified as the actual position — a heap alone does not determine the legal moves, and treating it as though it did is the trap that essay is about.

Where the ladder goes next #

The fibonacci-nim anchor has two rungs to here: that the position is a heap and a cap rather than a heap, and now that the factor two is one member of a family.

The rung above runs the check this page proposes and gets a cleaner answer than the conjecture asked for. What the numerals knew confirms that every factor gives a greedy numeral system whose smallest term is a winning move — so the whole family has the Fibonacci result and the Fibonacci case keeps no claim to being special. What it refutes is the prediction about which condition: the separation the numerals need was expected to be the lag of the recurrence the losing heaps satisfy, and it is not.

The two quantities are easy to confuse and they come apart at once. The gap in the non-adjacency condition is the factor itself — one at $c = 1$, Zeckendorf’s two at $c = 2$, and $c$ at every factor up to eight. The lag of the recurrence goes 1, 2, 4, 6, 8, 11, 14, 17 and abandons its own pattern at six. So the numeral system is indexed by the rule and the recurrence is indexed by something else, and reading one off the other is the error this page’s framing invites.

With the condition right, the numerals then do the whole job: every one of 194,480 states is settled, cap and all, which is the strongest form the family result takes.

Two neighbours are worth the trip. A golden ratio thirty years early is the other place the constant appears on this site and it appears for a completely different reason, which is the comparison that makes this page’s deflation of it land. And splitting is a move is another game whose losing positions have a formula, where the question this anchor is now asking — which rules give a describable sequence — is asked of the octal family instead.