2021 JMPSC Accuracy Problems/Problem 15
Problem
For all positive integers define the function
to output
For example,
,
, and
Find the last three digits of
Solution
We can easily find that Thus, we claim
that
Now, we find we can easily find that
This will be a proof by induction.
Base Case:
I claim that
We can easily find that
Thus, since
as desired.
~pinkpig
Solution 2 (More Algebraic)
We only care about the last
digits, so we evaluate
. Note the expression is simply
, so factoring a
we have
. Now, we can divide by
to get
Evaluate the last
digits to get
~Geometry285