1
$\begingroup$

I have a series that says $a_{n+1}=a_n^2+a_n$ and $a_1=3$ now I have to find $a_{1000} (\bmod{1000})$ now I calculated the remainder of numbers with respect to $1000$. thus $$a_1\equiv3(\bmod 1000)$$ $$a_2\equiv12(\bmod 1000)$$ $$a_3\equiv156(\bmod 1000)$$ $$a_4\equiv56^2+100\cdot56\cdot2+156(\bmod 1000)\equiv492(\bmod1000)$$ $$a_5\equiv92^2+2\cdot400\cdot92+492(\bmod 1000)\equiv556(\bmod1000)$$ $$a_6\equiv56^2+2\cdot500\cdot56+556(\bmod 1000)\equiv692(\bmod1000)$$ $$a_7\equiv92^2+2\cdot92\cdot600+692(\bmod 1000)\equiv556(\bmod1000)$$

now the sequence from $a_5$ to $a_{6}$ will keep on repeating thus we can calculate the remainder of $a_{1000}$ . now i am not particularly happy with my approach as this is brute force. is there any other approach to this question, which is more aesthetically pleasing, and is there a method to solve these type of questions in general.

$\endgroup$
1
$\begingroup$

Your approach is very probably the best available. However, your arithmetic is wrong: you can't drop the 100's digit when squaring each previous term.

If you do the arithmetic right, you find that $a_5 \equiv a_7 \equiv 556$ and $a_6 \equiv a_8 \equiv 692$ so the answer will be $692$.

$\endgroup$
  • $\begingroup$ yes you are right , i thought $10^4$ term appears so i took it off , but i forgot that $10^2$ term also appears . $\endgroup$ – avz2611 Mar 18 '15 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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