Project Euler problem 910

projecteuler.net/problem=910

A(x) = x + 1
Z(u)(v) = v
S(u)(v)(w) = v(u(v)(w))

Let's resolve the second example ourselves:

S
  (S)
  (S(S))
  (S(Z))
(A)
(0)

S
(S)
(
  S
  (S(S))
  (S(Z))
)
(A)
(0)

S
(S(S))
(S(Z))
(
  S
  (
    S
    (S(S))
    (S(Z))
  )
  (A)
)
(0)

S
(Z)
(
  S(S)
  (S(Z))
  (
    S
    (
      S
      (S(S))
      (S(Z))
    )
    (A)
  )
)
(0)

S(S)
(S(Z))
(
  S
  (
    S
    (S(S))
    (S(Z))
  )
  (A)
)
(
  Z
  (
    S(S)
    (S(Z))
    (
      S
      (
        S
        (S(S))
        (S(Z))
      )
      (A)
    )
  )
  (0)
)

S
(S)
(S(Z))
(
  S
  (
    S
    (S(S))
    (S(Z))
  )
  (A)
)
(0)

TODO: how long would this be?

So we see that all of these rules resolve quite quickly and do not go into each other. S however offers some problems, in that:

C_0 = Z
C_i = S(C_{i-1})
D_i = C_i(S)(S)

So we see that D_i goes somewhat simply into C_i, and C_i is recursive giving:

S^i(Z)

Calculate the nine first digits of:

D_a(D_b)(D_c)(C_d)(A)(e)

Removing D_a:

S^i(Z)S)(S)(D_b)(D_c)(C_d)(A)(e)

Project Euler problem 910

 Ancestors (12)