# Problem Of The Week #407 Mar 4th, 2020

Status
Not open for further replies.

#### anemone

##### MHB POTW Director
Staff member
Here is this week's POTW:

-----

Consider the sequence of numbers 4, 7, 1, 8, 9, 7, 6, ... For $n>2$, the $n$th term of the sequence is the units digit of the sum of the two previous terms. Let $S_n$ denote the sum of the first $n$ terms of this sequence. What is the smallest value of $n$ for which $S_n>10000$?

-----

#### anemone

##### MHB POTW Director
Staff member
Congratulations to the following members for their correct solution! 1. castor28
The sequence is defined by the recurrence relation $x_n=(x_{n-1}+x_{n-2})\bmod{10}$.
Looking at the first five terms, we observe that the period of the sequence is $3\pmod{2}$ and $4\pmod{5}$; the period is therefore $12$.
We list the first $12$ terms, and the cumulative sums:
$$\begin{array}{c|r|r|r|r|r|r|r|r|r|r|r|r|} n&1&2&3&4&5&6&7&8&9&10&11&12\\ \hline a_n&4&7&1&8&9&7&6&3&9&2&1&3\\ \hline S_n&4&11&12&20&29&36&42&45&54&56&57&60 \end{array}$$
As each period contributes $60$ to the total, we need $166$ full periods, giving a total of $9960$. To reach $10001$, we must increase that total by at least $41$. Looking at the table, we see that we must include $7$ additional terms, giving a total of $10002$. The total number of terms is therefore $12\times166+7=\bf1999$.