Competition problem — Algebra — Maths Olympiad Prep

Library / /333 of 860

Algebra Difficulty 5.1 AIME, harder Find the answer

For each positive integer $n$ and non-negative integer $k$ , define $W(n, k)$ recursively by $W(n, k)= \begin{cases}n^{n} & k=0 \\ W(W(n, k-1), k-1) & k>0\end{cases}$ Find the last three digits in the decimal representation of $W(555,2)$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

For any $n$ , we have $W(n, 1)=W(W(n, 0), 0)=\left(n^{n}\right)^{n^{n}}=n^{n^{n+1}}$ Thus, $W(555,1)=555^{555^{556}}$ Let $N=W(555,1)$ for brevity, and note that $N \equiv 0(\bmod 125)$ , and $N \equiv 3(\bmod 8)$ . Then, $W(555,2)=W(N, 1)=N^{N^{N+1}}$ is $0(\bmod 125)$ and $3(\bmod 8)$ . From this we can conclude (by the Chinese Remainder Theorem) that the answer is 875.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.