We all know how the Fibonacci numbers, $F_n$, work: each number in the sequence is the sum of the previous two numbers, and if we make the usual start, we get \[ \begin{array}{cccccccc} F_1 & F_2 & F_3 & F_4 & F_5 & F_6 & F_7 & \cdots \\[1mm] 1 & 1 & 2 & 3 & 5 & 8 & 13 & \cdots \end{array} \] The numbers in this sequence grow larger and larger, and can be expressed with the help of the golden ratio $\phi= (1+\sqrt{5})/2$, by the surprising formula \[ F_n = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}. \] There is a vast amount of literature about this number, $\phi$, to which this article will make no contribution whatsoever.
Instead, we’re going to think about the consequences of interpreting the rule slightly differently. Since this interpretation of the rules is a little weird, we’ll call these the Weirdonacci numbers, $W_n$. One can imagine that this new sequence comes from someone who has misunderstood the construction of the Fibonacci numbers. Instead of adding up the last two numbers of the sequence, the person would add the last two digits in the sequence.
As a consequence, we are still going to get each term by adding together the previous two numbers, but we will think of 13 as two numbers (digits), 1 and 3. The sequence will now grow differently.
We get: \[ \begin{array}{ccccccccccccc} W_1 & W_2 & W_3 & W_4 & W_5 & W_6 & W_7 & W_8 & W_9 & W_{10} & W_{11} & W_{12} & \cdots \\[1mm] 1 & 1 & 2 & 3 & 5 & 8 & 1 & 3 & 4 & 7 & 1 & 1 & \cdots \end{array} \]
Cuckoo: Wellcome Trust, CC BY 4.0
Notice that after 10 terms, the sequence starts repeating itself: we can write this as $W_{\ell+j}=W_j$, where $\ell=10$ is the length of the cycle.
Sadly, now that we’ve seen it repeat, there doesn’t seem to be much more to say about this sequence.
But there is.
Since the digits are what matters here, it is important to notice that this sequence depends on the base in which the numbers are expressed.
The inevitability of cycles
Let’s see what happens with a couple of other choices of base. We will write $W_n^{(b)}$ for the Weirdonacci numbers generated in base $b$. In base eight, we have the following sequence with cycle length $\ell=7$: \[ \begin{array}{cccccccccc} W_1^{(8)} & W_2^{(8)} & W_3^{(8)} & W_4^{(8)} & W_5^{(8)} & W_6^{(8)} & W_7^{(8)} & W_8^{(8)} & W_9^{(8)} & \cdots \\[1mm] 1 & 1 & 2 & 3 & 5 & 1 & 0 & 1 & 1 & \cdots \end{array} \]
In base nine we have the sequence below with cycle length $\ell=11$: \[ \begin{array}{cccccccccccc} W_1^{(9)} & W_2^{(9)} & W_3^{(9)} & W_4^{(9)} & W_5^{(9)} & W_6^{(9)} & W_7^{(9)} & W_8^{(9)} & W_9^{(9)} & W_{10}^{(9)} & W_{11}^{(9)} & \cdots \\[1mm] 1 & 1 & 2 & 3 & 5 & 8 & 1 & 4 & 5 & 1 &0& \cdots \end{array} \]
which brings us back to 1,1, so we see that in each case the sequence jumps back to the start after some number of terms.
We might be tempted to conjecture that this always happens, but we should also bear in mind that three cases are a rather slender foundation to build a conjecture on. It’s worth looking at a few other possibilities before committing to trying to prove something.
This tempting conjecture would also prove true in base seven (you should use the margins of this page to check this), but in fact fails in base six: \[ \begin{array}{cccccccc} W_1^{(6)} & W_2^{(6)} & W_3^{(6)} & W_4^{(6)} & W_5^{(6)} & W_6^{(6)} & W_7^{(6)} & \cdots \\[1mm] 1 & 1 & 2 & 3 & 5 & 1 & 2 & \cdots \end{array} \]
Here, it has gone into a cycle, but it didn’t return to the start of the sequence. So in every case we still get a cycle, but now we know that the loop might not go back all the way to the beginning. This leads to a reasonable conjecture: no matter which base you choose, the Weirdonacci numbers will eventually go into a cycle and repeat forever.
It isn’t too hard to see that this must be the case (once you think about it the right way).
If we work in base $b$, then there are only $b$ distinct numbers that can occur in the sequence. But if there are only $b$ distinct numbers, there can’t be more than $b^2$ pairs of numbers. Then a sequence of more than $b^2$ terms must have some repeated pairs. Wherever we spot a pair repeating, we have identified a cycle.
So not only do we know that the Weirdonacci numbers always eventually repeat, we know that the length of the cycle can’t be any longer than $b^2$. (Question: can it be as long as $b^2$?)
We can see from the above example that the cycle doesn’t have to start with the pair of numbers 1,1. In fact we can start a Weirdonacci sequence with any pair of numbers we like, and it doesn’t matter what the starting values are, or what base we use, eventually the sequence must enter a cycle. One of the first questions we started thinking about was what the length of a cycle could be.
Cycles can be any length
We’re going to look at what lengths cycles can be now. The maths gets a bit more complicated, so don’t feel embarrassed about skipping to the conclusions after the scorpions at the end of this section, and coming back to this later.
Fibonacci numbers
Exercise for the reader
Let us write $\mathcal{F}_{n}(\alpha,\beta)$ for the $n$th Fibonacci number, with initial values $\alpha$ and $\beta$. For example, if we start the sequence with 2,5 we obtain \[ 2,5,7,12,\ldots \] and so $\mathcal{F}_3(2,5)=7$ and $\mathcal{F}_4(2,5)=12$.
We can show (this is left as an exercise for the reader) that these new sequences are related to the usual Fibonacci numbers by the formula
$$ \mathcal{F}_{n}(\alpha,\beta)=\alpha F_{n-2}+\beta F_{n-1}, $$
where the usual Fibonacci sequence had to be a little extended by adding the numbers $F_{-1}=1$ and $F_0=0$. Look at the same example as above (the sequence starting with 2,5), this formula correctly tells us that \[ \mathcal{F}_4(2,5)=5F_3+2F_2=5\times 2+2\times 1 = 12. \]
We easily verify that $\mathcal{F}_{1}(\alpha,\beta)=\alpha$ and $\mathcal{F}_{2}(\alpha,\beta)=\beta$, as well as $\mathcal{F}_{n}(1,1)=F_{n}$.
Weirdonacci numbers
Let us write $W^{(b)}_n(\alpha,\beta)$ for the $n$th Weirdonacci number, generated in base $b$, and with initial numbers $\alpha$ and $\beta$. As long as $\mathcal{F}_{n}(\alpha,\beta)$ is smaller than the base $b$, the Weirdonacci numbers $W^{(b)}_n(\alpha,\beta)$ are equal to $\mathcal{F}_{n}(\alpha,\beta)$.
We then define as $k$ the smallest integer such that $\mathcal{F}_{k}(\alpha,\beta)$ < $b$ $\le $ $\mathcal{F}_{k + 1}(\alpha,\beta)$. Therefore for any 1 $\le $ $n$ $\le $ $k$,
\[W_n^{(b)}(\alpha,\beta)=\alpha {F}_{n-2}+\beta {F}_{n-1}.\]
When we reach a number greater than the base $b$, the next two Weirdonacci are generated: remember that in base 10, $W_5^{(10)}=5$, $W_6^{(10)}=8$ and since $8+5=13$, one writes $W_7^{(10)}=1$ and $W_8^{(10)}=3$. We’ll call this a collapse.
In general, we can write $\mathcal{F}_{k+1}(\alpha,\beta)=qb+r$, so that the next two Weirdonacci numbers are $W^{(b)}_{k+1}(\alpha,\beta)=q$ and $W^{(b)}_{k+2}(\alpha,\beta)=r$. In fact, $q$ must be 1, because otherwise at least one of the two previous Weirdonacci numbers would have to be greater than $b$. Consequently, we can write $r=\mathcal{F}_{k+1}(\alpha,\beta)-b$.
It follows that every loop must at least contain one pair of the form $(1,\beta)$, which it is natural to consider as the start of the cycle. Starting with 1 and $\beta$, we can write
\[
\begin{array}{ccccccc}
W_1^{(b)}(1,\beta) & W_2^{(b)}(1,\beta) & \cdots & W_k^{(b)}(1,\beta) & W_{k+1}^{(b)}(1,\beta) & W_{k+2}^{(b)}(1,\beta) & \cdots \\[1mm]
1 & \beta & \cdots & \mathcal{F}^{(b)}_k(1,\beta) & 1 & r & \cdots
\end{array}
\]
where $r=\mathcal{F}_{k+1}(1,\beta)-b$.
Simple loops
A loop of length $\ell=k$ would be formed if $r=\beta$. We’ll call loops that arise this way simple loops. Of course this is not the only way to generate a loop, as it may take several collapses for the loop to close, but it makes sense to think about the simplest possibility first.
The equation
\[
\beta = \mathcal{F}_{k+1}(1,\beta)-b
\]
gives us a relation between $b$, $\beta$ and $k$ for all simple loops. We can then rewrite this equation as
\[
b-F_{k-1}=\beta(F_k-1).
\]
If we pick a desired cycle length $k=\ell$, we can use this formula to find a base and starting numbers to give this cycle length. This means that cycles of every length are possible.
There’s lots more we could think about here, including the following challenge.
Challenge 1:
The Weirdonacci sequences $W_n^{(6)}$ and $W_n^{(10)}$ both have a cycle of length 4.
Show that if the base $b$ is even, then it is possible to pick two starting numbers that lead to a Weirdonacci sequence with a cycle of length 4.
(If you’re stuck, there is a hint at the end of the article.)
Non-simple loops
Of course, one could try to find equations describing non-simple loops—those with more than one collapse. For example, we could look for loops like this (we’ve left out the $(1,\beta)$s in the top row): \[ \begin{array}{ccccccccccc} W_1^{(b)} & W_2^{(b)} & \cdots & W_k^{(b)} & W_{k+1}^{(b)} & W_{k+2}^{(b)} & \cdots & W_{k+q}^{(b)} & W_{k+q+1}^{(b)} & W_{k+q+2}^{(b)} & \cdots \\[1mm] 1 & \beta & \cdots & \mathcal{F}^{(b)}_k(1,\beta) & 1 & \beta’ & \cdots & \mathcal{F}^{(b)}_q(1,\beta’) & 1 &\beta & \cdots \end{array} \]
These constraints lead to the set of equations
\begin{align*} b+\beta’ &= F_{k-1}+\beta F_{k},\\ b+\beta &= F_{q-1}+\beta’ F_{q}, \end{align*}
where $k+q$ is the period of the loop.
We have in fact already seen two examples for such loops, in base $b=10$ and $b=9$, where we had $\beta=1$, $\beta’=3$, $k=6$, $q=4$; and $\beta=0$, $\beta’=4$, $k=8$, $q=3$ (respectively).
Again, there are many other things to think about here, including the following challenge.
Challenge 2: Show that it is not possible to have a non-simple loop with $k=q$. (If you’re stuck, there is a hint at the end of the article.)
Cycles
We’ve found out a bit about which cycles can happen. We know that if we are allowed to choose the base and initial values, we can get any length of cycle that we care to. We have some idea how simple loops—where the value only exceeds the base once—behave, but loops where this happens more than once are much harder to analyse.
We’re now going to hand the question…
…over to you
We are now in a position to ask a few questions:
- What is the sequence, generated in base $b$, following the initial two numbers $W_1^{(b)}$ and $W_2^{(b)}$?
- After how many steps does the sequence enter a cycle?
- What is the length of the cycle reached by the sequence?
- For a given base $b$, is there one unique cycle? If not, how many cycles are there?
There are lots of other questions you might be asking about these sequences. We leave it to you to think about them using the ideas from the previous section—and, of course, whatever other ideas you have yourself!
If you find out something interesting, why not write it up for Chalkdust issue 12?
Are they guaranteed to come out the other side in much the same way? And if not, how can we permute them? And if we may permute them, are all permutations possible? How many are possible?
In 2009, Maxim Konsevitch had shown the following: the permutations $(1\;3\;4\;2)$ and $(1\;2\;4\;3)$ cannot be realised by polynomials. All other 22 permutations of $\left\{ 1,2,3,4 \right\}$ can be realised, yet these 2 mysterious configurations are not possible to achieve with polynomial functions. To prove the permittable permutations is to write down 22 cases: an engaging activity of which it would be criminal to deprive the reader. To prove the impossibility of our mysterious pair, we will need to pull the concept of a valuation from our algebraic minibar.