Question

In the sequence $$1,2,2,4,8,32,256, each term (starting from the third term) is the product of the two terms before it. For example, the seventh term is $256$, which is the product of the fifth term ($8$) and the sixth term ($32$). This sequence can be continued forever, though the numbers very quickly grow enormous! (For example, the $14 term is close to some estimates of the number of particles in the observable universe.) What is the last digit of the $35 term of the sequence

Answer 1

The sequence is recursively defined by

`\begin{cases}a_1 = 1 \\ a_2 = 2 \\ a_n = a_(n-1) a_(n-2) & \text{for } n \ge 3\end{cases}`

By this definition,

`a_(n-1) = a_(n-2) a_(n-3) \implies a_n = a_(n-2)^2 a_(n-3)`

`a_(n-2) = a_(n-3) a_(n-4) \implies a_n = (a_(n-3) a_(n-4))^2 a_(n-3) = a_(n-3)^3 a_(n-4)^2`

`a_(n-3) = a_(n-4) a_(n-5) \implies a_n = (a_(n-4) a_(n-5))^3 a_(n-4)^2 = a_(n-4)^5 a_(n-5)^3`

`a_(n-4) = a_(n-5) a_(n-6) \implies a_n = (a_(n-5) a_(n-6))^5 a_(n-5)^3 = a_(n-5)^8 a_(n-6)^5`

and so on.

Recall the Fibonacci sequence, {1, 1, 2, 3, 5, 8, 13, 21, …}, where the next term in the sequence is the sum of the previous two terms. If
`F_n` is the n-th Fibonacci number, then continuing the pattern above we would arrive at

`a_n = {a_2}^{F_(n-1)} {a_1}^{F_(n-2)} = 2^{F_(n-1)}`

Notice that the sequence of positive powers of 2 leaves a periodic sequence of residues mod 10 :

`2 \equiv 2 \pmod{10}`

`2^2 \equiv 4 \equiv 4 \pmod{10}`

`2^3 \equiv 8 \equiv 8 \pmod{10}`

`2^4 \equiv 16 \equiv 6 \pmod{10}`

`2^5 \equiv 2 * 2^4 \equiv 2 * 6 \equiv 2 \pmod{10}`

`2^6 \equiv 2^2 * 2^4 \equiv 4 * 6 \equiv 4 \pmod{10}`

and so on; the period of this sequence of residues is 4.

The period of
`F_n` taken mod 4 is 6 :

`\{1, 1, 2, 3, 5, 8, \ldots\} \equiv \{1, 1, 2, 3, 1, 0, \ldots\} \pmod 4`

(This follows from the "properties" section in the link in comment. In this case, π(4) = 3/2 × 4 = 6.)

It follows that

`34 \equiv 4 \pmod 6 \implies F_(34) \equiv 3 \pmod 4 \implies 2^{F_(34)} \equiv 2^3 \equiv 8 \pmod{10}`

which means the last digit of
`a_(35)` is 8.