What the numerals knew

Fibonacci Nim is one heap and one clause: a move may take at most twice what the previous move took, and whoever takes the last counter wins. The family the Fibonacci numbers belong to took the two out of that clause and left a factor $c$ behind, and found eight games where there had been one. Each has its own set of losing heaps, and each of those sets satisfies a linear recurrence of the form $a(n) = a(n-1) + a(n-j)$ for a lag $j$ that the sequence itself decides.

That page closed with a prediction, and the prediction is the reason this one exists:

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.

It is a natural guess. Zeckendorf’s condition on the Fibonacci numerals is no two consecutive, the Fibonacci lag is two, and two is two. The guess is that the lag carries through.

It does not. The separation condition of the greedy numeral system at factor $c$ is that two terms stand at least $c$ apart, and the lag has nothing to do with it. The two quantities agree at $c = 1$ and $c = 2$ — which is exactly the range in which the prediction was made — and part company at $c = 3$, where the lag is four and the gap is three.

What a numeral system is here #

Each game in the family supplies its own digits. Take the heaps from which the opener loses — the powers of two at $c = 1$, the Fibonacci numbers at $c = 2$, and five further sequences with no common name — and spell an arbitrary heap as a sum of them, greedily from the top, using each at most once.

That the spelling always exists is arithmetic rather than luck: every one of these sequences begins 1, 2, 3, …, so the remainder can always be reduced. That the spelling is unique is what the separation condition buys, and the condition is what this page is about.

The greedy algorithm never chooses. It takes the largest term not exceeding what is left, subtracts, and repeats. So the sequence of indices it produces is a fact about the sequence of digits, not about the algorithm, and asking how close together two indices can be is asking a question with one answer per game.

The measurement #

Every heap up to four thousand is spelled in every one of the eight numeral systems, and every gap between consecutive indices is recorded. Two numbers come out of it: the smallest gap that occurs, and how often the smallest gap occurs.

The first is the condition. The second is what stops the condition being a statement about the sweep: a bound nothing attains is a bound that might be loose, and at every factor the smallest gap is reached.

It is reached far less often at the sparse end. At $c = 1$ — where the digits are the powers of two and the numeral is ordinary binary — adjacent indices occur 10,660 times. At $c = 8$ they occur 150 times in the same four thousand heaps. The condition is tight everywhere and only just tight above $c = 5$, which is the sort of margin that would have hidden a wrong answer had the sweep been short.

Where the prediction went wrong, and why the mistake was reasonable #

The recurrence lag and the numeral gap are both quantities attached to the same sequence, and it is easy to say why one would expect them to agree.

If $a(n) = a(n-1) + a(n-j)$, then $a(n) - a(n-1) = a(n-j)$, so after taking $a(n)$ the remainder is at most $a(n-j) - 1$ and the next term is at most $a(n-j-1)$. That is a gap of $j + 1$, not $j$ — and it is an upper bound on the largest term, not a lower bound on the gap, which is the quantity the condition is about. The argument that feels like it gives the condition gives something else in the other direction.

What actually governs the gap is the game. A player who has just taken $t$ counters leaves an opponent who may take up to $ct$, so a term that is to be safe from the reply has to be more than $c$ times the term before it in the play, and the digits inherit that from the rule rather than from the recurrence.

That is the surprise worth carrying off this page. The recurrence was the first structure the family showed, it was the structure the rung below measured, and it is the derived quantity: it breaks its own pattern at $c = 6$ and keeps breaking it. The gap was invisible until the numerals were built, and it has no exception anywhere in the sweep.

How tight the condition is #

A condition that is respected and never met is not the condition; it is a consequence of a stricter one nobody has found. So the interesting half of the gap measurement is the count beside it.

At $c = 1$ the minimum is met 10,660 times in four thousand heaps, which is unremarkable: binary allows consecutive powers of two and almost every number uses some. At $c = 2$ it is met 6,214 times, and Zeckendorf numerals with two Fibonacci numbers exactly two indices apart are the common case rather than the corner.

From $c = 3$ the counts collapse — 379, 273, 224, 182, 152, 150 — and the pattern of gaps moves up. At $c = 5$ the commonest gap is eight, three above the minimum, and the minimum accounts for one gap in a hundred. The bound stays exact and stops being typical, which is the state a bound is in when it is about to be wrong and is not.

That is why the sweep runs to four thousand rather than to a few hundred. A hundred and fifty occurrences over four thousand heaps is fewer than ten over two hundred, and at two hundred the $c = 8$ system produces so few numerals of more than two terms that the smallest gap would plausibly not have appeared at all — leaving a measurement that reported a larger minimum and a condition that was wrong in the direction hardest to notice.

The rule the numerals give #

The condition is not the point of a numeral system; the move is. At $c = 2$, the classical result is that the smallest term of the Zeckendorf representation is a winning move, and the rung below could not check whether that transferred, because the transfer is a separate claim needing its own induction.

It transfers, and it transfers in a stronger form than the classical statement.

A Fibonacci Nim position is not a heap. The heap is not the position is the essay that establishes it: the position is a pair, the heap $n$ together with the cap the previous move left, and a heap of six under a cap of two is a different game from a heap of six under a cap of five. The classical rule is about the opening, where there is no cap.

The rule the numerals give is about the pair:

The mover loses exactly when the smallest term of the heap’s numeral exceeds the cap. Otherwise, taking that term wins.

At the opening the cap is effectively infinite, so the first clause reduces to the heap is a single term — that is, the heap is one of the losing heaps — and the second clause reduces to the classical move rule. The pair version contains both and says something at every position a game actually passes through.

What the check is #

The recursion is the one the rest of the family was computed with: a position is a win for the mover if some legal move leaves a loss, memoised on the heap and the cap with the cap clamped at the heap, since a cap larger than the heap and a cap equal to it permit the same moves.

For each factor, every state with a heap up to 220 is enumerated — 24,310 of them — and two questions are asked. Does the rule’s verdict match the recursion’s? And where the recursion says the mover wins, is the move the rule names actually a winning move?

Both answers are the same at every factor and the total is 194,480 states with no exception. The move check is the stronger of the two and is the one that matters to a player: a rule that names the loser and cannot name a move is a theorem that names no move, and this family has enough of those already.

The assertion is in the census rather than in the prose. It refuses to report at all if the smallest gap at any factor is not the factor, if any state disagrees, or if the $c = 2$ condition fails to come out as Zeckendorf’s non-adjacency — because a general condition that does not specialise to the known case is a general condition about something else.

What the condition costs #

A sparser numeral system spells the same heap with fewer terms, and each term has to be larger to make up the difference. That is not a side effect of the condition; it is the same fact seen from the other end.

Binary — the $c = 1$ system — needs 5.93 terms for the average heap below four thousand, and the longest numeral it produces has eleven. At $c = 8$ the average is 2.96 and the longest is four. The digits themselves thin out to match: twelve powers of two below four thousand against fifty-five digits at $c = 8$.

And that thinning is why a large factor makes a duller game. A generous rule leaves the opener winning from nearly everything, because the losing heaps are the digits and there are few of them; the numeral is short, the smallest term is easy to find, and the game is over. The factor that makes the sequence longest is the factor that makes the game hardest, and it is the smallest one.

The same numerals, in a game with a board #

The one thing on this site that shares the Fibonacci Nim numerals is not a heap game at all. The digits say which move wins is about Wythoff’s game — two heaps, a queen on a quarter-infinite board — where the losing positions are given by the golden ratio and the winning move is read off a Zeckendorf numeral.

Two games, no shared mechanism, and the same digits. A golden ratio thirty years early is where that coincidence is taken apart, and the finding there is worth repeating beside this page’s: the ratio is in Wythoff’s game because the Fibonacci numbers are, and the Fibonacci numbers are there for a reason about pairs rather than about caps.

This page says the same thing one level up. The golden ratio at $c = 2$ is one root of a family of equations, one per factor, and the numeral gap at $c = 2$ is one value of a condition, one per factor. Neither is special. What is special is that two is the smallest factor at which the game is not trivial, so it is the one anybody would have played.

A prediction refuted and a result strengthened #

Two things happen here at once and it is worth keeping them apart, because a page that refutes its own prediction can read as a failure and this one is the opposite.

The prediction fails. The separation condition was expected to be the lag of the recurrence the losing heaps satisfy, and it is not: the gap is the factor, one at $c=1$, two at $c=2$, and $c$ throughout — while the lag goes 1, 2, 4, 6, 8, 11, 14, 17 and abandons its own pattern at six.

The result is stronger than the prediction would have been. The gap being the factor is a simpler answer than the gap being the lag, and it is simpler in the way that matters: it is read off the rule of the game rather than computed from the sequence the rule produces. A condition indexed by the rule is available before anything is swept; one indexed by a recurrence requires the sweep first.

And the two quantities coincide exactly where the family is famous. At $c = 2$ the factor is two and the lag is two, so Zeckendorf’s condition is both, and the Fibonacci case gives no way to tell which generalises. That is the same failure mode this site keeps meeting: a distinguished case where two candidate laws agree, and a family where they do not.

So the useful reading is about where the prediction came from. It came from the best-known member, and the best-known member is nearly always the one where the most quantities coincide — which is what makes it the best-known and what makes it the worst place to generalise from.

What the census does not say #

Four limits, and the first is the important one.

It is checked, not proved. The smallest gap is $c$ holds on every heap to four thousand at eight factors, and the smallest term within the cap wins holds on 194,480 states. Neither is a theorem here. The shape a proof would take is visible — the gap ought to fall out of the reply bound in a paragraph, and the move rule out of an induction on the numeral — but a shape is not a proof, and this site does not claim to have settled what it has only searched.

Eight factors is a small family. The sweep stops at $c = 8$ because the losing heaps thin out and the sequences stop having enough terms below the bound to say anything. Whether the gap stays at $c$ for very large factors is a question about a game so generous that nearly every heap is a win, and the answer would say more about arithmetic than about play.

The state check is bounded by the heap, not by the cap. Heaps up to 220 with every cap gives every state a game of that size can be in, but a game played from a heap of four thousand passes through caps this sweep never built. The rule is stated for all of them and checked on a prefix.

And the numeral system is greedy by construction. A different representation over the same digits — one that is not greedy — could satisfy a different condition, and nothing here says the greedy one is the only representation with a move rule attached. It is the one with the classical result behind it at $c = 2$, which is why it is the one built.

The convention, named #

Normal play throughout: the player who cannot move loses, and the player who takes the last counter wins. Misère Fibonacci Nim is a different game and none of this holds in it.

The opener may not take the whole heap, which is the standard statement of the rule and is what makes the game finite in an interesting way — without it every heap is a win in one move. The cap after a move of $t$ counters is $\lfloor ct \rfloor$, which for integer $c$ is $ct$ and is written with the floor because the census was built to accept a rational factor and has not been run with one.

The index gap is between positions in the digit sequence, not between the digits themselves. Two Fibonacci numbers 8 and 21 are terms three apart in value and two apart in index, and it is the index that the condition is about.

Where the ladder goes next #

The fibonacci-nim anchor has three rungs: that the position is a heap and a cap rather than a heap, that the factor two is one member of a family, and now that the family’s numerals carry a condition the family’s recurrences do not predict.

The rung above is the proof, and it is unusually well posed for one. The gap condition should follow from the reply bound in a few lines, and the move rule from an induction on the number of terms; both are statements this page has data for at eight factors and neither is stated as anything but a measurement. It is the sort of rung that either falls out in a paragraph or turns out to need a careful invariant, and the interesting outcome is the second.

Two neighbours are worth the trip. The heap is not the position is where the state was identified, and this page is what that state turns out to be worth: the rule that could not be written about heaps alone is one sentence about heaps and caps. And the period is small and the proof does not say so is the other place on this site where a quantity everyone measures — a period, a lag — turns out not to be the quantity that governs, which is the shape of the finding here.