Numbers in a sequence

Question

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.

Answer 1

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.

Answer 2

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)

Answer 3

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