(An archive problem of the week)
While gathering sequence/pattern questions for my last post, I ran across a very different problem. Here we are told what the pattern is (a good example of one that you would probably never discover on your own), and asked some questions about later terms. It can be understood either using tools of number theory, or with only knowledge of arithmetic and some good insights.
A sequence of digits
Here is the question, from 2004:
Interesting Number Sequence Pattern The sequence of digits 1,2,3,4,0,9,6,9,4,8,7,... is constructed in the following way: every digit starting from the fifth is the last digit of the sum of the previous four digits. a) Do the digits 2,0,0,4 appear in the sequence in that order? b) Do the initial digits 1,2,3,4 appear again in the sequence in that order? I haven't come across such a series before. I really don't know how to continue.
To make sure we understand the pattern, here is how the first few terms are obtained:
1+2+3+4 = 10 --> 0 2+3+4+0 = 9 --> 9 3+4+0+9 = 16 --> 6 4+0+9+6 = 19 --> 9 0+9+6+9 = 24 --> 4 9+6+9+4 = 28 --> 8 6+9+4+8 = 27 --> 7
Now, how could we tell whether a given number appears ever, or a second time, in this sequence?
Some background
Doctor Vogler answered; not knowing what background Kamsin (an adult) had, he started by mentioning the Number Theory tools he used to solve the problem:
Thanks for writing to Dr. Math. Do you know what modular arithmetic is? You can refer to Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html Thinking of this in terms of modular arithmetic will probably be helpful. Then you have: Each term is the sum of the previous four, mod 10. By the Chinese Remainder Theorem, we can break this into two problems: Answer each question mod 2 and mod 5. That will make things easier. In case none of that made sense, I will try to avoid talk of modular arithmetic. But if you wonder how I came up with these ideas, then you should start by learning modular arithmetic.
The rest of what he says doesn’t require any knowledge beyond ordinary arithmetic, but can be better understood from the higher perspective. The modular arithmetic comes in due to the fact that taking the ones digit of a number is the same as dividing the number by 10 and taking the remainder; we say that the number is congruent to the remainder, “modulo 10”. For information about the Chinese Remainder Theorem, see
Chinese Remainder Theorem and Modular Arithmetic
Can 2004 ever appear?
But we’ll move on without these.
Now arithmetic mod 2 is simply a matter of odds or evens. So look at the pattern of odds and evens in your sequence: odd, even, odd, even, even, odd, even, odd, even, even, ... You should notice a repeat after every five terms. Can you prove that this pattern will continue indefinitely? Now answer part (a).
To make things more compact, rather than write “even” and “odd” over and over, I will just replace each number in our sequence with the remainder after division by 2, so that “0” means “even”, and “1” means “odd”:
1, 2, 3, 4, 0, 9, 6, 9, 4, 8, 7, … becomes
1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, …
We can build this new “even/odd” or “0/1” sequence by doing exactly what we did before, but starting with 1, 0, 1, 0, and adding, writing the remainder after division by 2 at each step (so that 1 + 1 = 0, since 2 is even):
1+0+1+0 = 0 0+1+0+0 = 1 1+0+0+1 = 0 0+0+1+0 = 1 0+1+0+1 = 0 1+0+1+0 = 0
Did you notice that we are right back where we started? From here on, the pattern will repeat forever, so that we will get 0, 1, 0, 1, 0 for every five terms.
But 2, 0, 0, 4 has the pattern 0, 0, 0, 0 (that is, all even). We’ve shown that this can never happen — the most we’ll ever get are two evens in a row. That concludes part (a).
Will 1234 ever reappear?
Part (b) is a little harder, but it only requires you to establish that this pattern has to repeat. So I'll give you the general ideas and hope that you can fill in the details and understand what is going on. First of all, you should notice that if you know any four consecutive numbers in the sequence, then you can start listing off all of the numbers that follow it, and you can start listing off all of the numbers that preceded it. Let's practice. Suppose that 5, 8, 1, 4 appears somewhere in the sequence (which it may or may not). If it does, then what do the next three or four numbers have to be? And what does the number before the 5 have to be? What about the two numbers before that?
This is the same idea we used to see that the pattern of odds and evens repeats, but this time applied to the original sequence, and going in both directions. The latter is true because we can find the previous number by subtracting and taking the remainder: if x + 5 + 8 + 1 = 4 (mod 10), then x = 4 – 1 – 8 – 5 (mod 10). (This is a little tricky: the subtraction gives -10, and if we add 10 to this we get 0, which is the answer. The number before that will be 1 – 8 – 5 – 0 = -12, and we have to add 20 to this, getting remainder 8. We can’t just divide -12 by 10 and say the remainder is 2, because that doesn’t take the sign into account.)
So each time a given group of four numbers appears, everything after it is just the same as the previous time it appeared.
Okay, so if the initial sequence 1, 2, 3, 4 ever appears later in the sequence (after the first time), then that means that the sequence repeats, right? Well, what if it doesn't repeat? What can happen? Well, there are only 10^4 possible sequences of four numbers. So let's think about the first 10^4 + 4 numbers, and every string of four of them makes a total of 10^4 + 1 different strings of four numbers. Do you know the pigeonhole principle? It tells us that some string of four numbers has to occur twice (at least). But that means that it repeats! Let's suppose this string (and we don't know what numbers it has) starts the first time at position n and the second time at position n+m. Then the m numbers (including the four from the first string) from the beginning of the first occurrence to the beginning of the second occurrence MUST be the next m numbers as well! Because the next m numbers are determined by the next four. So that means it has to repeat, every m numbers.
To put this very simply, suppose you made a list of the first 10,004 digits in this sequence, which constitute 10,001 groups of four digits. Since there are only 10,000 possible 4-digit numbers, the 10,001 numbers can’t all be different. There must be at least one number that repeats. But as we saw, if a number repeats once, then it repeats over and over — and not just that one number, but everything between the two occurrences we found.
We have used the pigeonhole principle in many answers, most of them cases where the student knows what it is, and didn’t need a full explanation. For one simple case including an explanation, see
Pieces on a Chess Board
Now, there is one possibility left. Maybe we start with 1234, and eventually reach a point where things start repeating, but the repeating part doesn’t include the 1234. Is that possible?
But now let's go backwards. The m numbers before the first occurrence must be the same as the m numbers after it, so that same pattern repeats. That means that every string of four numbers that appears in the sequence at all must repeat every m numbers! Is that right? Why can't we start going along and then get stuck somewhere? For example, why can't we have lots of random numbers coming along until we suddenly find four zeros in a row? If that ever happens, then it will just keep giving us zeros. So why can't that happen? (Hint: What was the last nonzero digit?) Does all of this discussion make sense to you? So what is the answer to the second question?
To answer the hint, if at some point we have 0000, then we have to continue with zeros both forward and backward — that is, we must have started with 0000. We can’t get there from any other start.
More questions
It’s easy to ask more questions about this sequence. For example when is the next occurrence of 1234? I made a spreadsheet to create the sequence, and found that it occurs after 1560 digits. Could we have worked that out without actually carrying this out? What if we started with a different set of digits? Under what conditions would we get a different number than 1560? What if we used more or less than four digits in defining the sequence?