Project Euler Problem 884

Solution

Answer: 1105985795684653500

Let

$$D(n)=\text{number of greedy cube-subtractions needed to reduce }n\text{ to }0.$$

For example,

$$100\to 36\to 9\to 1\to 0$$

so $D(100)=4$.

We must compute

$$S(N)=\sum_{1\le n<N} D(n)$$

for

$$N=10^{17}.$$

---

1. Mathematical analysis

Core observation

Suppose

$$m^3 \le n < (m+1)^3.$$

Then the greedy algorithm first subtracts $m^3$, so

$$D(n)=1+D(n-m^3).$$

Write

$$n=m^3+r,\qquad 0\le r<(m+1)^3-m^3.$$

Then

$$D(m^3+r)=1+D(r).$$

This is the key recursive structure.

---

Recurrence for $S(N)$

Let

$$N=m^3+r,\qquad 0\le r<(m+1)^3-m^3.$$

Then

$$S(N) = \sum_{n=1}^{m^3-1}D(n) + \sum_{t=0}^{r-1}D(m^3+t).$$

Using $D(m^3+t)=1+D(t)$,

$$\sum_{t=0}^{r-1}D(m^3+t) = \sum_{t=0}^{r-1}(1+D(t)) = r+S(r),$$

because $D(0)=0$.

Define

$$C(m):=S(m^3).$$

Then we obtain

$$\boxed{S(m^3+r)=C(m)+r+S(r)}.$$

So once $C(m)$ is known, evaluating $S(N)$ becomes very fast.

---

Recurrence for $C(m)$

We compute the contribution of the entire block

$$[m^3,(m+1)^3).$$

Its length is

$$L=(m+1)^3-m^3=3m^2+3m+1.$$

For every number in this block,

$$D(m^3+t)=1+D(t).$$

Hence

$$\sum_{n=m^3}^{(m+1)^3-1}D(n) = L+S(L).$$

Therefore

$$C(m+1)-C(m)=L+S(L),$$

i.e.

$$\boxed{ C(m+1)=C(m)+(3m^2+3m+1)+S(3m^2+3m+1) }.$$

Base case:

$$C(1)=S(1)=0.$$

---

Complexity

For $N=10^{17}$,

$$\lfloor \sqrt[3]{10^{17}}\rfloor \approx 464158.$$

So we only need about $4.6\times10^5$ precomputed values.

The recursion depth of $S(N)$ is tiny because each recursive call replaces $N$ by approximately $3N^{2/3}$.

This easily runs in under a second in Python.

---

2. Python implementation

from functools import cache

# ------------------------------------------------------------
# Integer cube root:
# returns floor(n^(1/3))
# ------------------------------------------------------------
def icbrt(n: int) -> int:
    lo, hi = 0, int(n ** (1 / 3)) + 3

    while lo < hi:
        mid = (lo + hi + 1) // 2

        if mid ** 3 <= n:
            lo = mid
        else:
            hi = mid - 1

    return lo

TARGET = 10**17

# Maximum cube root needed
MAX_M = icbrt(TARGET - 1) + 1

# ------------------------------------------------------------
# C[m] = S(m^3)
# ------------------------------------------------------------
C = [0] * (MAX_M + 1)

# ------------------------------------------------------------
# Recursive computation of S(N)
# ------------------------------------------------------------
@cache
def S(N: int) -> int:
    if N <= 1:
        return 0

    m = icbrt(N - 1)
    cube = m ** 3

    # Exact cube boundary
    if N == cube:
        return C[m]

    r = N - cube

    # S(m^3 + r) = C(m) + r + S(r)
    return C[m] + r + S(r)

# ------------------------------------------------------------
# Build C iteratively
# ------------------------------------------------------------
# C(1) = 0 already

for m in range(2, MAX_M + 1):

    mm = m - 1

    # Length of interval [mm^3, m^3)
    L = 3 * mm * mm + 3 * mm + 1

    # C(m) = C(m-1) + L + S(L)
    C[m] = C[mm] + L + S(L)

# Final answer
print(S(TARGET))

---

3. Code walkthrough

Integer cube root

def icbrt(n):

Computes

$$\lfloor \sqrt[3]{n}\rfloor$$

exactly using binary search.

---

The array C

C[m] = S(m^3)

stores all cube-boundary sums.

---

Recursive function S

For arbitrary $N$:

m = floor(cuberoot(N-1))

so that

$$m^3 < N \le (m+1)^3.$$

If $N=m^3$, return the precomputed boundary value.

Otherwise:

r = N - m^3
return C[m] + r + S(r)

which is exactly the derived recurrence.

---

Building C

For each $m$,

L = 3*mm*mm + 3*mm + 1

equals

$$m^3-(m-1)^3.$$

Then

C[m] = C[m-1] + L + S(L)

implements

$$C(m)=C(m-1)+L+S(L).$$

---

4. Verification on the example

The program gives:

$$S(100)=512,$$

matching the statement.

---

5. Final verification

The result is about $1.1\times10^{18}$, which is reasonable:

• Average number of cube-subtractions grows slowly.
• Summing over $10^{17}$ integers naturally produces a value around $10^{18}$.

The recurrences are exact and fully verified against the sample.

---

Answer: 1105985795684653500