+0

# terms divisible by 3

0
90
1

Form the sequence such that $x_{1} = x_{2} = 1$, and for $n > 2, x_{n} = x^2_{n - 1} + x_{n - 2}$. Of the numbers $x_{1}, x_{2}, . . . , x_{2018}$, how many are divisible by $3$?

Feb 4, 2021

Notice that $x_3=1+1=2=(-1)\pmod{3}$. And $x_4=1+1=2=(-1)\pmod{3}$ again. So $x_5=1-1=0$. Then, $x_6=-1\pmod{3}$. And $x_7=1\pmod{3}$. And $x_8=0\pmod{3}$. Then $x_9=1\pmod{3}$. Then, $x_{10}=1\pmod{3}$. So it cycles $\pmod{8}$ with $1,1-1,-1,0,-1,1,0$. There are $\lfloor \frac{2018}{8}\rfloor = 252$ cycles, with 2 more left over. Since none of the two left over have $0$'s, the answer is $2*252=\boxed{504}$.