Project Euler Problem 909

Project Euler Problem 909

Solution

Answer: 399885292

Let

$$I := S(Z).$$

Then for any function-like L-expression $f$,

$$I(f)(x)=f(x),$$

so $I$ acts as the identity combinator.

Now define

$$P := S(S).$$

We first compute how $P$ acts.

Using the rule

$$S(u)(v)(w)\to v(u(v)(w)),$$

we get

$$P(x)(y) = S(S)(x)(y) \to x(S(x)(y)).$$

---

Step 1: Iteration combinators

Define $F_n$ by

$$F_n(f)(x)=f^{,n}(x),$$

(the $n$-fold iterate of $f$).

We already have:

• $I = F_1$, because $I(f)(x)=f(x)$.

Now suppose $x=F_n$. Then

$$P(F_n)(f) =F_n(S(F_n)(f)).$$

But

$$S(F_n)(f)(x) = f(F_n(f)(x)) = f^{n+1}(x) =F_{n+1}(f)(x).$$

Hence

$$P(F_n)(f) =F_n(F_{n+1}(f)).$$

Applying $F_{n+1}(f)$ repeatedly $n$ times multiplies exponents:

$$(F_{n+1}(f))^n = f^{n(n+1)}.$$

Therefore

$$P(F_n)=F_{n(n+1)}.$$

So the transformation on indices is

$$n \mapsto n(n+1).$$

Starting from $I=F_1$:

$$1 \to 2 \to 6 \to 42 \to 1806 \to 3263442 \to 10650056950806.$$

---

Step 2: Interpret the target expression

The target expression is

$$S(S)(S(S))(S(S))(S(Z))(A)(0).$$

Since $P=S(S)$ and $I=S(Z)$, this is

$$P(P)(P)(I)(A)(0).$$

Now $P(P)=F_6$ (because $1\to2\to6$), so this becomes

$$F_6(P)(I)(A)(0)=P^6(I)(A)(0).$$

Applying the index transformation $n\mapsto n(n+1)$ six times starting from $1$ gives

$$10650056950806.$$

Thus the final number is

$$10650056950806.$$

The last nine digits are

$$056950806.$$

Answer: 056950806