Fibonacci hidden in Collatz

How the most famous sequence in mathematics turned up, uninvited, inside the problem nobody knows how to solve.

This story brings together two characters that, on the face of it, have nothing to do with each other. One is a celebrity: the Fibonacci numbers, the sequence that shows up in pop-science books, in sunflowers, even in The Da Vinci Code. The other is a problem with a curious reputation: the Collatz conjecture, a question with a childishly simple statement that fascinates amateurs, unsettles professional mathematicians, and has gone unanswered since 1937.

What I'm going to tell you here is a result from my doctoral thesis: a theorem showing that, inside the dynamics of Collatz, the Fibonacci numbers are counting something very specific. It's no numerical coincidence, no approximate curiosity: it's an exact equality, true forever, with a proof. And the best part is that the whole path —from the definition of Fibonacci to the theorem— can be walked with high-school mathematics. Let's walk it.

1. The Fibonacci numbers

The rule is as simple as it gets: start with \(1, 1\) and, from there, each term is the sum of the two before it.

\[ F(1)=1,\quad F(2)=1,\quad F(n)=F(n-1)+F(n-2). \]

Look at the ratio between consecutive terms shown by the simulator. As you go on, it closes in on one very specific number:

\[ \varphi=\frac{1+\sqrt5}{2}=1.6180339\ldots \]

It's the famous golden ratio. No coincidence: in the long run the Fibonacci numbers grow by multiplying by \(\varphi\) at each step. Keep this in mind, because \(\varphi\) will come back at the end of the story in the most unexpected place.

Where they really live (and where they don't)

You've surely heard that the nautilus shell is a «golden spiral». I'm sorry to spoil it: it isn't. It is a logarithmic spiral, yes, but with a different ratio; the Fibonacci claim there is a myth repeated from book to book. There are, though, places where the Fibonacci numbers really do show up, for reasons we can understand: the spirals of seeds in a sunflower or the scales of a pinecone tend to come in pairs of consecutive Fibonacci numbers (8 and 13, 21 and 34), because that arrangement is the most efficient way to pack seeds that are born rotated by a fixed angle.

But Fibonacci's natural habitat isn't botany: it's counting paths. The classic example: in how many ways can you climb a staircase of \(n\) steps if at each move you go up 1 or 2?

The why fits in one sentence: to reach step \(n\), your last move was a 1 (you came from \(n-1\)) or a 2 (you came from \(n-2\)); therefore, ways to reach \(n\) = ways to reach \(n-1\) + ways to reach \(n-2\). That is exactly the Fibonacci rule. Whenever a problem reduces to counting paths with two options that chain together like this, Fibonacci shows up on its own. Remember this idea: it's the key to everything that follows.

2. The Collatz conjecture

Take any positive whole number. If it's even, divide it by 2. If it's odd, multiply it by 3 and add 1. Repeat. The Collatz conjecture says that, wherever you start, you always end up reaching 1. Almost ninety years on, nobody has been able to prove it or to find a counterexample — and not for lack of evidence: it has been checked by computer, one by one, for every number up to \(2^{71}\) (more than two sextillion). That it holds two sextillion times in a row doesn't prove it holds always: that gap between checking and proving is the heart of the problem.

Mathematicians usually use an «accelerated» version of the rule. Since \(3n+1\) is always even when \(n\) is odd, we can divide by 2 right away and save a step:

\[ T(n)=\begin{cases} n/2 & \text{if } n \text{ is even},\\[2pt] \dfrac{3n+1}{2} & \text{if } n \text{ is odd}. \end{cases} \]

With this version, the end of the journey is the small cycle \(1\to2\to1\). Everything that follows uses \(T\).

Try 27: it climbs to almost 5,000 before giving up. Try 26: it gets home right away. Next-door neighbours, opposite fates. That's the character of the problem: the rule is trivial, but the behaviour is wild and unpredictable.

And yet, there is a way to tame that chaos. It consists of changing lens: to stop looking at the number and look at something far humbler.

That something is the remainder when you divide by 6: the number between 0 and 5 that's left over. 27 leaves remainder 3 (because \(27 = 4\cdot 6 + 3\)); 80 leaves remainder 2; and however huge the number, its remainder is always one of those six values. Nothing more.

Here is the decisive shift, and it's worth pausing on. Numbers live in an infinite space: they jump into the thousands, with no way to foresee where they'll go. But their remainders live in a tiny space — only six possible values, no matter what. So while a number's trajectory shoots off with no apparent pattern, the trajectory of its remainders is forced to move among six cells. And the best part: it doesn't jump between them at random, but by fixed rules. It's like swapping an infinite, road-less map for a board of six cells with the arrows already drawn.

Let's see it. Let's launch a trajectory again —the same one as before, if you like— but this time colouring each number by the remainder it leaves when divided by 6:

This is the thing to see: however far the trajectory flies, the colours only dance among six. That small dance, finite and rule-bound, is what we're going to study — and it's where, in the end, Fibonacci will appear.

3. A map with six regions

Let's name the six cells: we'll call them «regions», one for each remainder (0 to 5). The question, the only one we need, is: if a number is in region \(r\), which region can \(T\) send it to?

And it's answered with pure high-school arithmetic. Take region 1. A number with remainder 1 is written \(n=6k+1\) for some integer \(k\ge 0\); since it's odd, \(T\) sends it to:

\[ T(n)=\frac{3n+1}{2}=\frac{3(6k+1)+1}{2}=9k+2. \]

And what remainder does \(9k+2\) leave when divided by 6? Here's the idea, and it's the only thing to grasp: the result changes depending on whether \(k\) is even or odd. And the reason fits in one line: since \(9k+2 = 6k + (3k+2)\), the remainder is decided by \(3k\), which is 0 if \(k\) is even and 3 if it's odd. So \(9k+2\) leaves remainder 2 when \(k\) is even, and remainder 5 when it's odd. So region 1 has two exits — to 2 and to 5 —, one for each parity of \(k\). Those are the two arrows leaving region 1 on the map, and that's why they come in two colours: green for \(k\) even, amber for \(k\) odd.

With the other five regions it works the same (if \(n\) is even, you get \(n/2\), even simpler). The result is twelve arrows, two per region — this map. Click any region to see its calculation and light up its two arrows:

This map has two features worth a close look, because everything else flows from them.

Regions 0 and 3 have only outgoing arrows. They are different regions —0 is the multiples of 6 and 3 is the odd multiples of 3—, but together they form the multiples of 3, and they share a quirk: no arrow from the core reaches them. The reason is simple. To land on a multiple of 3 you'd have to start from one already: if \(n\) is odd, \(\tfrac{3n+1}{2}\) is never a multiple of 3 (because \(3n+1\) isn't); and if \(n\) is even, \(n/2\) is a multiple of 3 only when \(n\) already was. So you can start on a multiple of 3, but once you leave, you never return.

The other four regions \(\{1,2,4,5\}\) form the core of the system. Every trajectory ends up inside —by what we just saw: sooner or later you leave the club of multiples of 3 and never come back— and, once inside, you circulate among them forever. Each region of the core has exactly two exits: from 1 you go to 2 or 5; from 2, to 1 or 4; from 4, to 2 or 5; from 5, to 2 or 5. Two possible paths at each step means the number of trajectories doubles at every step: 2, 4, 8, 16… It grows fast, but in a perfectly regular way. Hold on to that word —doubles—, because in the next section we'll remove a single region from the map and watch that «doubling» turn, without warning, into something far more interesting.

4. The forbidden region: the subgraph \(H_4\)

Now comes the question that sets everything off. Of the four regions in the core, region 4 is special: you only reach it from one, region 2 (check it in the explorer above: it's the only arrow pointing to 4). What if a number manages to dodge it forever? How many can circulate through the core without ever stepping on region 4?

To answer that, we remove region 4 from the map and keep only \(\{1,2,5\}\) and the arrows between them. (A vocabulary bridge, because from here on it's handy: what we've been calling a «map» is really a graph, and each region is a vertex of it; removing a region leaves a subgraph. I call this one \(H_4\): the one that survives deleting region 4.)

Notice what happened when we deleted 4: regions 1 and 5 keep their two exits, but region 2 has lost one —its arrow towards 4— and is left with a single one: back to 1. The full core always offered two options per step; \(H_4\) offers two options, except when you step on 2, which offers only one. That small asymmetry —two paths almost always, just one when you step on 2— is what will manufacture Fibonacci. Let's see it.

The matrix that counts paths

Here is the only piece of algebra we need, and it's worth understanding, not just believing. Let's start with the easiest case. The matrix \(M\) itself already counts the paths of one step: its cell \((r,s)\) is 1 when there's an arrow from \(r\) to \(s\) —a path of length 1— and 0 when there isn't.

And the paths of two steps? To go from \(r\) to \(s\) in two steps you have to stop at some intermediate region \(t\): first \(r\to t\), then \(t\to s\). Counting in how many ways you can is exactly what multiplying the matrix by itself does: the cell \((r,s)\) of \(M^2\) runs over all possible intermediate regions \(t\) and adds up «is there an arrow \(r\to t\)?» times «is there an arrow \(t\to s\)?». Chaining the same thing step by step leads to the general rule:

And you needn't take it on faith: in the table below, click any cell and you'll see those paths written out one by one.

Slide it slowly and look at the matrix entries: 1, 1, 2, 3, 5, 8, 13, 21… Every single entry of \(M^k\) is a Fibonacci number, and so are the path totals per row. We didn't put them there: the graph manufactured them.

And why Fibonacci, and not just any sequence? The lovely thing is that you can see it without a single calculation, looking only at the map of \(H_4\). Let's count the paths of length \(k\) starting at region 1 —the very ones the simulator counts— and call them \(C(k)\). The first step can only go to 2 or to 5:

If it goes to 5, something fortunate happens: region 5 has exactly the same exits as 1 (in the matrix, their two rows are identical). So carrying on from 5 is like starting the count over from 1: there are \(C(k-1)\) paths left. If it goes to 2, region 2 can't choose —its only exit is back to 1—, so the path spends two steps (\(1\to2\to1\)) and returns to the starting point: there are \(C(k-2)\) paths left. Adding the two possibilities:

\[ C(k) = C(k-1) + C(k-2). \]

It is, letter for letter, the Fibonacci rule. And now it really is exactly the staircase: two ways to continue, one that advances a step (going to 5) and another that «jumps» two (the detour \(1\to2\to1\)). The asymmetry at 2 wasn't a detail: it was the engine.

Notice what that recurrence means for the rate of growth. In section 1 we saw that the Fibonacci numbers grow, in the long run, by multiplying by \(\varphi\) at each step. Since our paths obey exactly the same rule, they grow at the same rate: the number of paths through \(H_4\) multiplies by \(\varphi=1.618\ldots\) —I told you the golden ratio would come back—. In the full core, by contrast, where each region really does have two exits, the number of paths doubles: it multiplies by 2. Two different rates, \(\varphi\) against 2 (mathematicians call that rate the spectral radius of the graph), and that difference changes everything:

Watch the two bars pull apart: the larger \(m\) gets, the rarer it is to dodge region 4 — the paths that avoid it are a fraction of the total that shrinks without brake, at the rate \((\varphi/2)^m\). And now, at last, recall the question from the start. By the number↔path dictionary from the previous section, the numbers that dodge region 4 are exactly those paths in \(H_4\). So we now have the full answer: how many numbers dodge 4 is told by the Fibonacci numbers, and how rare they become is told by the ratio \(\varphi/2\). That, written cleanly, is the theorem.

5. The theorem

Let's put the pieces together. The numbers that avoid region 4 are, via the graph, paths in \(H_4\); the paths in \(H_4\) are counted by the powers of \(M\); and the powers of \(M\) manufacture Fibonacci numbers. But the exact statement sharpens two things that look like details and are precisely where the subtlety lies: it talks about odd numbers and starts looking from the second step. It's worth understanding why.

First, let's fix the words, because it's easy to get tangled here. The orbit of a number \(n\) is the sequence you get by applying \(T\) over and over: \(n,\ T(n),\ T(T(n)),\ \ldots\) We'll call \(n\) itself step 1, \(T(n)\) step 2, \(T(T(n))\) step 3, and so on: step \(k\) is the result of applying \(T\) a total of \(k-1\) times. (We'll always use «step» for that position and «apply \(T\)» for the operation; best not to mix the two words.)

And now the fact that explains it all, and that you can check: whatever odd number you take, a single application of \(T\) lands it in region 2 or 5 — that is, inside \(H_4\). Look: \(7\to11\equiv5\), \(9\to14\equiv2\), \(15\to23\equiv5\). It doesn't matter if the starting odd number is a multiple of 3 —like 3, 9 or 15, which live in region 3, outside the core—: on the first step it lands all the same, and cleanly, inside \(H_4\).

That's where the two conditions come from. We count odd numbers because their entry into \(H_4\) is always clean and in a single step; even numbers behave worse —a multiple of 6 can keep looping in region 0, which has an arrow to itself, for several steps before entering the core (for example \(24\to12\to6\to3\), three steps in region 0)—. And we look from step 2 because step 1 is the starting odd number: its remainder is never 4 (it's odd), so asking it to «avoid region 4» would say nothing, and besides it might be a multiple of 3, which isn't even in the core yet. It's from step 2 on that every odd number is guaranteed inside \(H_4\), and the question «does it manage to stay, dodging region 4?» becomes exactly our path count. Its answer is an exact statement:

Not «approximately», nor «for large \(m\)»: exactly the Fibonacci number \(F(m+1)\), for every \(m\). For example, with \(m=6\): of the 32 odd numbers up to 64, exactly 13 \(=F(7)\) dodge region 4. And the rate \((\varphi/2)^m\)? It's precisely the \(\varphi\)-against-2 duel from the previous viewer: the survivors grow like \(\varphi\) and the total like 2, so their proportion fades on its own. Dodging region 4 is possible, but ever rarer; almost every number ends up stepping on it.

Don't take my word for it — check it. This verifier runs the real count, number by number; and you can click any number to open its orbit and see how it dodges —or doesn't— region 4:

6. Why it matters

A connection between Fibonacci and Collatz is lovely in its own right, and it's not the first time someone has glimpsed it: in «Collatz Meets Fibonacci» (Albert, Gudmundsson and Ulfarsson, 2022), certain counts tied to Collatz coincide with the Fibonacci numbers… up to length 14, and from there the match breaks and «extra» terms appear. The difference here is that the count is exact —\(F(m+1)\), for every \(m\) without exception— and with a closed proof. But the theorem says, on top of that, something deeper about the structure of the problem.

In the paper it's proved that no vertex of the core is dispensable: delete whichever you like, the growth rate falls strictly below 2, and each vertex has its exact price. Deleting 4 (or 1) leaves it at \(\varphi\approx1.618\); deleting 5, at \(\sqrt2\approx1.414\); and deleting 2 sinks it to 1: without region 2, barely a thread of paths is left. The full hierarchy, \(1<\sqrt2<\varphi<2\), measures how much each region holds up the traffic of the dynamics.

And that has a direct consequence for the conjecture. If there were a cycle other than \(1\to2\to1\) —one of the two ways Collatz could be false—, that cycle would be a closed path in the graph, and a closed path has to square with the traffic rules of the map: in each region, the times you enter and the times you leave must balance out. From that bookkeeping comes something very concrete: the theorem forces every positive cycle of \(T\) to visit region 2, and moreover to spend more than 18% of its steps there. We don't know whether such cycles exist, but we already know something concrete about what they'd have to look like: there's no possible cycle living hidden in the margins of the map.

That, for me, is the moral of all this. The Collatz conjecture is still open, and this theorem doesn't settle it. But it shows that beneath the apparent chaos of the trajectories there is a rigid, measurable, exact structure — so exact that at its heart beat, from the very beginning and unseen by anyone, the Fibonacci numbers and the golden ratio.

---