Project Euler Problem 340

Project Euler Problem 340

Solution

Answer: 291504964

Let

$$F(n)= \begin{cases} n-c & n>b\[4pt] F(a+F(a+F(a+F(a+n)))) & n\le b \end{cases}$$

and

$$S(a,b,c)=\sum_{n=0}^{b}F(n).$$

We need:

$$S(21^7,7^{21},12^7)$$

modulo $10^9$.

1. Mathematical analysis

Define

$$d=a-c.$$

Since $a>c$, we have $d>0$.

For $n>b$,

$$F(n)=n-c=n-d-a+a.$$

The key is to understand what happens for $n\le b$.

Step 1: Partition $n$ into blocks

Let

$$k=\left\lfloor \frac{b-n}{a}\right\rfloor.$$

This means $n$ lies in the $k$-th block from the top:

$$b-(k+1)a < n \le b-ka.$$

We claim:

$$F(n)=n+D_k$$

for a block-dependent constant $D_k$.

---

Step 2: Base case ($k=0$)

If $b-a<n\le b$, then $a+n>b$, so:

$$F(a+n)=a+n-c=n+d.$$

Then every remaining nested argument is already $>b$, so each outer application subtracts another $c$:

$$F(n) = n+d+d+d+d = n+4(a-c).$$

Thus

$$D_0=4a-4c.$$

---

Step 3: Recurrence for $D_k$

Suppose $n$ is in block $k\ge1$. Then $a+n$ lies in block $k-1$, so by induction:

$$F(a+n) = (a+n)+D_{k-1}.$$

After that, the remaining three outer applications are all in the $>b$ regime, each contributing $+d$. Hence:

$$D_k = a+D_{k-1}+3d.$$

Since $d=a-c$,

$$D_k = D_{k-1}+4a-3c.$$

With

$$D_0=4a-4c,$$

this solves to:

$$D_k = (k+1)(4a-3c)-c.$$

Therefore:

$$\boxed{ F(n) = n+(k+1)(4a-3c)-c }$$

where

$$k=\left\lfloor \frac{b-n}{a}\right\rfloor.$$

---

Step 4: Summing

Let

$$b=qa+r, \qquad 0\le r<a.$$

Then:

• blocks $k=0,\dots,q-1$ each contain exactly $a$ values,
• block $k=q$ contains $r+1$ values.

Also,

$$\sum_{n=0}^{b} n = \frac{b(b+1)}{2}.$$

Let

$$T=4a-3c.$$

Since

$$D_k=(k+1)T-c,$$

the total offset is

$$a\sum_{k=0}^{q-1}\big((k+1)T-c\big) + (r+1)\big((q+1)T-c\big).$$

Using

$$\sum_{j=1}^{q}j=\frac{q(q+1)}{2},$$

we get

$$S(a,b,c) = \frac{b(b+1)}{2} + a\left( T\frac{q(q+1)}{2} -cq \right) + (r+1)\big((q+1)T-c\big).$$

---

2. Python implementation

def crazy_sum(a, b, c):
    # Divide b into full blocks of size a
    q, r = divmod(b, a)

    # Constant increment per block
    T = 4 * a - 3 * c

    # Sum of n from 0 to b
    total = b * (b + 1) // 2

    # Contribution from full blocks
    full_blocks = a * (
        T * q * (q + 1) // 2 - c * q
    )

    # Contribution from the final partial block
    final_block = (r + 1) * (
        (q + 1) * T - c
    )

    return total + full_blocks + final_block

# Example check
print(crazy_sum(50, 2000, 40))
# 5204240

# Required problem
a = 21 ** 7
b = 7 ** 21
c = 12 ** 7

answer = crazy_sum(a, b, c) % (10 ** 9)
print(answer)

---

3. Code walkthrough

divmod(b, a)

Splits $b$ into:

$$b=qa+r$$

so we know how many complete blocks of width $a$ exist.

T = 4*a - 3*c

This is the step size in the arithmetic progression of block offsets:

$$D_k=(k+1)T-c.$$

total

Adds the base contribution

$$\sum n=\frac{b(b+1)}{2}.$$

full_blocks

Sums offsets for all full blocks:

$$a\sum_{k=0}^{q-1}D_k.$$

final_block

Adds the leftover partial block of size $r+1$.

---

Verification on the sample

For

$$(a,b,c)=(50,2000,40)$$

the code returns:

$$5204240$$

which matches the problem statement exactly.

---

4. Final verification

We only need the last 9 digits, so we compute:

$$S(21^7,7^{21},12^7)\bmod 10^9.$$

The formula matches the sample exactly and avoids any recursion or brute force over the enormous range $0\le n\le 7^{21}$.

Answer: 291504964