Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The number sequence $1, 9, 8, 2...$ satisfies the following rule: each element of the sequence starting from the fifth, is equal to the last digit of the sum of the previous four members. Will we ever meet four successive members equal to $3, 0, 4, 4$.

My intuition said that this was a invariance problem. So I searched for the invariant. The only obvious invariant I could come up with was remainders modulo 2. These remainders form a sequence which repeats: $1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1...$ This invariant (maybe more of a semi-invariant) does not give a different result for the required sequence. I could not devise another invariant to solve the problem.

I tried other remainders: modulo $3$, modulo $5$, etc, but nothing yields the answer.

share|improve this question
1  
This sequence is clearly periodic because the number of combinations is finite. $3$ and $5$ give you the answer, but the period can be pretty long. –  Harold Jun 27 '13 at 3:44
    
Yes, $a_{1557}=3$, $a_{1558}=0$, $a_{1559}=4$, $a_{1560}=4$. It seems that period is $1560$. –  Oleg567 Jun 27 '13 at 3:50
    
@Harold The sequence is ultimately periodic, but that doesn't mean that 1 9 8 2 necessarily repeats - that requires more work. –  Mark Bennet Jun 27 '13 at 4:43

3 Answers 3

up vote 1 down vote accepted

Just of fill out the comment I made.

Note first that the sequence is generated by a recurrence modulo $10$ so we have $$a_{n+4}=a_{n+3}+a_{n+2}+a_{n+1}+a_n \mod 10$$

We therefore also have $$a_{n}=a_{n+4}-a_{n+3}-a_{n+2}-a_{n+1} \mod 10$$

So any four consecutive numbers define the whole sequence backwards and forwards. We can use $1982$ or $3044$ as a seed and see if the other emerges. Since there are a finite number of possible sequences of $4$ decimal digits, each will eventually recur. As it happens, starting with $3044$ works immediately.

Since we know that the modulo $2$ pattern has period $5$, the mod $10$ must have period divisible by $5$.

There are $10,000$ possible 4-digit sequences. The ones which can occur in the sequence fall into one of five patterns (mod $2$) out of $16$ possibles. This leaves a possible $3125$ sequences of four digits. This is just over twice the period of $1560$ found by direct calculation.

The sequence seeded by $5500$ takes five of the mod $2$ possibles, leaving $3120$ - exactly twice the period found by calculation.

share|improve this answer

$\ldots, \color{red}{3,0,4,4}, \color{green}{1,9,8,2}, \ldots$

share|improve this answer

Indexing beginning with $0$ (so $a_0 = 1$, etc.), the subsequence $$ 3, 0, 4, 4 $$ occurs at indices $1556, 1557, 1558, 1559$.

I found this by brute force. (It took less than one second.) Here's a snippet of Python code that I used to discover it:

L = [1, 9, 8, 2]
while L[-4:] != [3, 0, 4, 4]:
    L.append(sum(L[-4:])%10)
len(L)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.