Recently I’ve been volunteering with the middle school math club at Penn Alexander, a PreK-8 school in my neighborhood. Today we did (among other things) a fun activity I’d never seen before, called “number bracelets”. The students seemed to enjoy it; it worked especially well with a bunch of students all working on it at the same time since they were able to compare notes.
Here’s the idea: start with any two one-digit numbers you like. For example, let’s choose 4 and 6. Next, add the two numbers: 4 + 6 = 10. Throw away the tens digit of your answer (if any); this is the next number in the sequence. In our case we get 0. Now we have 4, 6, 0 and we do the same thing with the last two numbers, 6 and 0: 6 + 0 = 6. So now we have 4, 6, 0, 6. Continuing, we get
4, 6, 0, 6, 6, 2, 8, 0, …
Try some different starting numbers. Do the sequences ever repeat? How many different sequences can you make? How long can they be? Can you generalize this to other sorts of rules for generating sequences?
A much better description (with pretty pictures, more questions for exploration, and spoilers) can be found here.
The Math Less Traveled 
You’re probably not looking for complete answers, but
1) Yes, the sequence is always periodic. One can see by Pigeonhole that it must have period at most 100, since a pair of consecutive entries uniquely determine both the entries before it and the entries after it and there are at most 100 such entries.
2) Actually, the period divides 60. For a conceptual way to show this one works first mod 2 and then mod 5. Modulo a prime one then finds the splitting field of the characteristic polynomial
of the sequence, which determines the period by a generalization of Fermat’s little theorem; the precise result for the Fibonacci sequence can be found here and one can write any sequence generated by this game as a linear combination of the Fibonacci sequence and the Lucas sequence, for which a similar result can be proven. The result you get is that both sequences have period 20 mod 5 and 3 mod 2.
3) Of course corresponding results hold for any sequence generated by a linear recurrence. If the recurrence isn’t invertible one in general only has eventual periodicity, not periodicity.
Qiaochu: cool, thanks for the analysis! I knew 1) and 3) but 2) is new to me (I had noticed that the period always divides 60 but didn’t know why).
I talked about this with my 8 year old son, and he quite enjoyed it. We created a complete table of all starting pairs and which chain they generated.
Then we tried it using other bases, and he noticed after a couple of examples that the starting values of 0, 1 generated the longest chain in all of the examples.
Having tested a few by hand, I wrote a program to check larger values, and I haven’t found a counter example below 800.
Does anyone know how to prove this? Even better, can anyone prove it in a way my 8 year old can understand? 🙂
Mark: Interesting question!
Some thoughts: suppose we are working mod m, and that x and y share a nontrivial divisor which is also a divisor of m. Then y and (x+y) mod m also share the same divisor. Conversely, if there is some divisor d of m which does not divide both x and y, then d also does not divide both y and (x+y) mod m—if it did then it is not hard to show that d would also divide x, but d didn’t divide both x and y.
So if we make a bracelet starting with two numbers that share a common factor d with each other and with m, then we can get a bracelet of size at most (m/d)^2. (Essentially this amounts to working in a subgroup of Z_m—such a bracelet will correspond to the bracelet you get starting with x/d and y/d when working mod m/d.)
So the intuition is that bracelets where the numbers share a common factor with the modulus will tend to be shorter, since there are fewer possibilities.
However, this isn’t a proof, since we don’t always get larger bracelets for smaller values of d—for example, with m = 10 the bracelet starting with 2,1 (where d = 1) is shorter (length 12) than the bracelet starting 0,2 (where d = 2, length 20). If your conjecture is true, there has to be something else that is special about the bracelet starting 0,1 besides the fact that d = 1.
There are actually a lot of cases where there are many equally long chains, 0,1 just happens to be one of them.
On particularly interesting one is mod 23. There are 12 chains including the trivial 0,0 chain, all of length 48.
0 0 -> 1
0 1 -> 48
0 2 -> 48
0 3 -> 48
0 4 -> 48
0 5 -> 48
0 6 -> 48
0 7 -> 48
0 8 -> 48
0 9 -> 48
0 10 -> 48
0 11 -> 48
The other interesting thing is to look at the sequence of longest chains for each modulus. The online encyclopedia of integer sequences has it here:
http://www.research.att.com/~njas/sequences/A001175
This fact was quite surprising to me:
Index the Fibonacci numbers so that 3 is the fourth number. If the modulo base is a Fibonacci number (>=3) with an even index, the period is twice the index. If the base is a Fibonacci number (>=5) with an odd index, the period is 4 times the index.
Pingback: m-bracelets « The Math Less Traveled
Mark: the Fibonacci sequence has period exactly 60 so this follows from property 2) in my first remark. If you want a “conceptual” reason why this should be the extremiser, I don’t know that there’s a good answer. The corresponding result for a simpler class of linear recurrences (i.e. geometric sequences) is about identifying the primitive roots of a base, and really there is no known good way to determine what these are.
do you have some screenshots of this number bracelets? thank you
Rubber Bracelets: yes, see this post!
I made a mutiplication version of this, and it repeats infinitely!
Jackson: neat! How does your multiplication version work?
Pingback: m-bracelets | The Math Less Traveled