Conway’s Subprime Fibonacci Sequences
The Fibonacci sequence is all about addition, right? Indeed, every element Fn of the Fibonacci sequence is the sum of the two previous elements: Fn = Fn-1 + Fn-2. Looking closer we see that the Fibonacci sequence grows like a geometric progression φn, where φ is the golden ratio. In addition, the Fibonacci sequence is a divisibility sequence. Namely, if m divides n, then Fm divides Fn.
My point: we define the sequence through addition, and then multiplication magically appears by itself. What would happen if we tweak the rule and combine addition and multiplication there?
John Conway did just that: namely, he invented a new sequence, or more precisely a series of sequences depending on the pair of the starting numbers. The sequences are called Conway’s subprime Fibonacci sequences. The rule is: the next term is the sum of the two previous terms, and, if the sum is composite, it is divided by its least prime factor.
Let me illustrate what is going on. First we start with two integers. Let’s take 1 and 1 as in the Fibonacci sequence. Then the next term is 2, and because it is prime and we do not divide by anything. The next two terms are 3 and 5. After that the sum of two terms is 8, which is now composite and it is divided by 2. So the sequence goes: 1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11 and so on.
The subprime Fibonacci sequences excite me very much. Not only does adding some multiplication to the rule make sense to me, but also, the sequences are fun to play with. I got so excited that I even coauthored a paper about these sequences titled, not surprisingly, Conway’s Subprime Fibonacci Sequences. The paper is written jointly with Richard K. Guy and Julian Salazar, and is available at the arXiv:1207.5099.
We can start a subprime Fibonacci sequence with any two positive numbers. You can see that such a sequence doesn’t grow fast, because we divide the terms too often. We present a heuristic argument in the paper that allows us to conjecture that no subprime Fibonacci sequence grows indefinitely, but they all start cycling. The conjecture is not proven and I dare you to try.
Meanwhile, the sequences are a lot of fun and I suggest a couple of exercises for you:
- Prove that there are no cycles of length two or three.
- Prove that the maximum number in a non-trivial cycle is prime.
- Prove that the smallest number in a non-trivial cycle is more than one. You can prove that it is more than 6 for extra credit.
By the way, a trivial cycle is the boring thing that happens if we start a sequence with two identical numbers n bigger than one: n, n, n, n, ….
Have fun.
Share:
emmanuel:
Is the cycle 7,14,7,14,7,14,… also trivial ?
30 July 2012, 2:19 pmTanya Khovanova:
Ennanuel,
The sequence is 7,14,7,7,7,7
30 July 2012, 2:27 pmemmanuel:
Oeps …
30 July 2012, 3:07 pmemmanuel:
… when corrected, it gives a proof of the non existence of cycles of length two. Indeed, these would start with a,ap-a, where p is a prime less than a. Then they continue with a,a,a,…
31 July 2012, 3:14 amObsessiveMathsFreak:
This is amazing!
3 August 2012, 5:52 am