Solving the 2,0,0,5 Sequence Puzzle - Prove Your Answer!

[b0mb0nika]

starting with 2,0,0,5 form the sequence 2,0,0,5,7,2,4,8,1 ...
where each successive digit is the unit digit of the sum of the previous 4 ( 2+0+0+5=7, 0+0+5+7=12 , write 2, .. etc.)

does the sequence 4,0,5,3 ever appear ? prove your answer

i have been trying to see some sort of pattern.. but i can't figure out anything
if anyone has any idea how to do it.. or maybe a hint.. i would really appreciate it..
thanks

 

[mahesh_2961]

hi
why can't u just try to generate the numbers previous to 4,0, 5,3 ... all the generated numbers should be single digit
i got ...11,3,0,4,8,5,7,4, 4,0,5,3,...
since we are getting 11 the sequence 4,0 ,5,3 will never appear

regards
Mahesh

 

[recon]

I don't see how you got 11, mahesh. You could have used 1, instead.

I tried looking at parity, but that didn't work.

 

[mahesh_2961]

yeah u r right.
that was a blunder from my part

Mahesh

 

[recon]

I am not really sure where to start from. Did you try looking at the problem in this way?

2,0,0,5,(2+5),(2+5+5),(2+2+5+5+5+5),...

Maybe there's some sort of pattern...not being able to see it is really starting to annoy me. We need experts!

 

[NateTG]

If you can prove that the sequence hits 2,0,0,5 again, you should be home free since 4,0,5,3 would have to come right before it.

 

[Galileo]

Is it at all possible for the sequence to NOT repeat itself?

 

[noelhustler]

Solution

Hi,
This is a Tetranacci number series modulo 10 and in this particular case has a period of 1560 and so the sequence 4,0,5,3 does first appear (because it is the last sequence of a period) at n=1557 assuming we start from n=1.

 

[b0mb0nika]

i did some research about those series.. didn't find too much
i don't understand how you got the period?

 

[noelhustler]

I'm rather interested in where you got this problem from.
A proof derived from base principles would be quite complicated.

 

[Alkatran]

Step one: The thing must fall into a loop because there are only 10000 possible arrangements.

Step Two: Write a computer program to iterate this thing 10000 times.

Step three: Check Answer

Answer: Yes. At 1557 iterations, 3117, 4768

Note: 3117 - 1557 = 1560
If we moved it backwards a bit...

 

[NateTG]

I'm rather interested in where you got this problem from.
A proof derived from base principles would be quite complicated.

Let's rewrite this sequence as a sequence of four digit numbers by grouping consecutive froursomes of digits:
2005
0057
0572
5724
.
.
Since there are only 10,000 possinbe 4 digit numbers, the sequence must eventually loop. Since the sequence is deterministic in both directions it must loop to 2005 rather than to some other point in the sequence (there are no dangling tails), and it doesn't take a whole lot of work to see that the four digits before 2,0,0,5 must be 4,0,5,3.

It's possible to ask all sorts of interesting questions about sequences like this or simpler fibonacci-esque sequences that may be difficult to prove. I recall tinkering with Fibonnaci (esque) seuqences mod a number to see if, for example, the period of the fibonnaci sequence modulo a number can be related to properties of that number.

 

[noelhustler]

Yes, I digressed.
I forgot the question simply asked whether or not it repeated.
I was thinking of a derivation of the period.

It is interesting to note that there are only 3 possible periods for any four starting digits.
For the particular starting sequence a,0,0,b they are:
If a = b = 5 then the period is 5 (obviously)
If a mod 2 = b mod 2 = 0 then the period is 312.
Otherwise the period is 1560.
I suppose this is related to the factors of 10 (the series mod 2 has period 5 and the seriod mod 5 has period 312).

This is discounting the trivial period of 1 given by starting from all zeros.

 

[NateTG]

I suppose this is related to the factors of 10 (the series mod 2 has period 5 and the seriod mod 5 has period 312

Right, and the period of the combination is a product of the periods as would be expected.

If a mod 2 = b mod 2 = 0 then the period is 312.

It's probably clearer to write that as
a=b=0 (mod 2)
or, even better:
$$a \equiv b \equiv 0 (mod 2)$$

 

[noelhustler]

The series mod 7 is peculiar. the other moduli 2..10 have a single period if prime or a single period plus the periods of their prime factors if not.
7 however has two distinct periods depite being prime.

Any ideas?

 

[b0mb0nika]

for noel:
i got this prob as a bonus question in one of my assignments from a 2nd yr math course. The prof said we should be able to solve it with math knowledge just from high school, and we're not allowed to write any computer programs..
i got to run to class now.. so i'll read all the posts later today..
thanks everyone:)

 

[noelhustler]

Ah yes, I misread the actual question.
Must remember to read the post before hitting submit.
Very important, that.

 

[CTS]

Does looking at a generating function help at all? It's easy to show that the numbers of the sequence, $$a_n$$, are given by the coefficients (mod10) of $$x_n$$ in the power series of $$\frac{3x^3-2x^2-2x+2}{1-x-x^2-x^3-x^4} = 2 + 0x + 0x^2 + 5x^3 + 7x^4 + 12x^5 + 24x^6 + 48x^7 + 91x^8 + 175x^9 + 338x^{10} + {\cal O}(x^{11})$$

 

[NateTG]

Does looking at a generating function help at all? It's easy to show that the numbers of the sequence, $$a_n$$, are given by the coefficients (mod10) of $$x_n$$ in the power series of $$\frac{3x^3-2x^2-2x+2}{1-x-x^2-x^3-x^4} = 2 + 0x + 0x^2 + 5x^3 + 7x^4 + 12x^5 + 24x^6 + 48x^7 + 91x^8 + 175x^9 + 338x^{10} + {\cal O}(x^{11})$$

Well, I was looking at the fibonacci series mod n with some computer programs and didn't see any paterns. That was a year or two ago - I'll see if I can dust it off.

 

[b0mb0nika]

Since there are only 10,000 possinbe 4 digit numbers, the sequence must eventually loop. Since the sequence is deterministic in both directions it must loop to 2005 rather than to some other point in the sequence (there are no dangling tails), and it doesn't take a whole lot of work to see that the four digits before 2,0,0,5 must be 4,0,5,3.

I don't understand why it eventually must loop. Just because there are 10000 possible 4 digit numbers ? It might get to some 4 digit number( or numbers ) and then repeat itself.

 

[Galileo]

I don't understand why it eventually must loop. Just because there are 10000 possible 4 digit numbers ? It might get to some 4 digit number( or numbers ) and then repeat itself.

No, because the whole process is reversible.
Here's an intuitive argument:
Suppose the sequence would 'enter' a loop and repeat itself indefinately.
We are able to work backwards to the numbers we started with at any point, but if we entered a loop, we would also be stuck in that loop while trying to go back, which contradicts the fact that we are able to get back to the numbers we started with by reversing the process.