Interesting Number Sequence Pattern

Date: 11/01/2004 at 11:28:14
From: Kamsin
Subject: Number series

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.

Date: 11/01/2004 at 15:20:29
From: Doctor Vogler
Subject: Re: Number series

Hi Kamsin,

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.

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).

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?

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 principal?  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
occurrance to the beginning of the second occurrance 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.

But now let's go backwards.  The m numbers before the first occurrance
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?

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/02/2004 at 12:43:15
From: Kamsin
Subject: Thank you (Number series)

Dear Dr. Vogler,

Thank you very much for the explanation to this problem which I've
been trying to solve for weeks.  This is a great site for a maths
enthusiast!