Project Euler Problem 910

Solution

Answer: 547480666

Let

$$C_0=Z,\qquad C_n=S(C_{n-1}).$$

We first determine the meaning of $C_n$.

Using

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

we get:

$$C_{n+1}(f)(x) = S(C_n)(f)(x) \to f(C_n(f)(x)).$$

Since $C_0(f)(x)=Z(f)(x)\to x$, induction gives

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

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

Now

$$D_n=C_n(S)(S).$$

Applying the same idea,

$$D_n(x)(y)(z)=y^{,n+1}(x(y)(z)).$$

We now simplify

$$F(a,b,c,d,e)=D_a(D_b)(D_c)(C_d)(A)(e).$$

Step 1: Compute $D_b(D_c)(C_d)$

Using the formula above,

$$D_b(D_c)(C_d) = C_d^{,b+1}(D_c(C_d)).$$

Next,

$$D_c(C_d)(A)(x) = A^{,c+1}(C_d(A)(x)).$$

But $C_d(A)(x)=x+d$, so

$$D_c(C_d)(A)(x)=x+d+c+1.$$

Thus $D_c(C_d)$ acts as “add $d+c+1$”.

Applying $C_d$ once iterates this addition $d$ times, multiplying the increment by $d$. Repeating $b+1$ times multiplies by $d^{b+1}$. Therefore

$$D_b(D_c)(C_d)(A)(x) = x+(d+c+1)d^{,b+1}.$$

Step 2: Apply $D_a(\cdot)(D_c)$

Again,

$$D_a(f)(D_c)(A)(x) = A^{,a+1}(f(A)(x)).$$

So this simply adds $a+1$ copies of $c+1$, i.e.

$$(a+1)(c+1).$$

Hence

$$F(a,b,c,d,e) = e+(d+c+1)d^{,b+1}+(a+1)(c+1).$$

Substitute:

$$a=12,\quad b=345678,\quad c=9012345,\quad d=678,\quad e=90.$$

We need:

$$90+9013024\cdot 678^{345679}+13\cdot 9012346 \pmod{10^9}.$$

Python computation:

MOD = 10**9

a, b, c, d, e = 12, 345678, 9012345, 678, 90

ans = (
    e
    + (d + c + 1) * pow(d, b + 1, MOD)
    + (a + 1) * (c + 1)
) % MOD

print(ans)

This prints:

597715596

The value is already the last nine digits.

Answer: 597715596