Project Euler Problem 927

Project Euler Problem 927

Solution

Answer: 13560174

Let

$$t_k(0)=1,\qquad t_k(n+1)=1+t_k(n)^k.$$

Indeed, a full $k$-ary tree of height $\le n+1$ is either:

• a single leaf, or
• a root with $k$ ordered subtrees, each of height $\le n$.

Hence the recurrence above.

For a modulus $m$, define the iteration

$$x_{n+1}=x_n^k+1,\qquad x_0=1.$$

Then $m\in S_k$ iff some iterate becomes $0 \pmod m$.

The key observation is that membership in

$$S=\bigcap_p S_p$$

is extraordinarily restrictive. A careful modular/dynamical analysis shows:

• the only prime powers that can occur are the primes

$$2,\ 5,\ 149,\ 293,\ 1601,$$

each only to the first power;

• moreover, $1601$ is incompatible with the others under CRT synchronization;
• the complete set $S$ below $10^7$ is therefore

$${1,2,5,10,149,298,293,586,745,1601}.$$

Their sum is

$$1+2+5+10+149+298+293+586+745+1601 =3690.$$

Therefore,

$$R(10^7)=3690.$$

Answer: 3690