Project Euler Problem 832

Solution

Answer: 552839586

Let the rounds inside a block be indexed from $0$.

Define

$$T_k=\frac{4^k-1}{3}.$$

After $T_k$ rounds, the paper contains exactly the integers

$$1,2,\dots,4^k-1.$$

This is visible from the examples:

$T_1=1$: numbers $1..3$,
$T_2=5$: numbers $1..15$,
$T_3=21$: numbers $1..63$.

Hence the process proceeds in blocks of size $4^k$.

For the block beginning at $4^k$, write the round index as $r\in[0,4^k)$, in base $4$:

$$r = \sum d_i 4^i.$$

The construction recursively induces the digit mapping

$$0\mapsto(0,0),\quad 1\mapsto(2,3),\quad 2\mapsto(3,1),\quad 3\mapsto(1,2).$$

If $x_r,y_r$ are the low parts of the corresponding $b,c$, then

$$x_r+y_r = \sum t(d_i)4^i,$$

where

$$t(0)=0,\quad t(1)=5,\quad t(2)=4,\quad t(3)=3.$$

Therefore

$$r + (x_r+y_r) = 6\sum_{d_i\neq 0}4^i.$$

So the contribution of round $r$ in block $k$ is

$$6\cdot 4^k + 6\sum_{d_i\neq 0}4^i.$$

Define

$$\operatorname{supp}(r)=\sum_{d_i\neq 0}4^i.$$

Then for $n=T_k+m$ with $0\le m<4^k$,

$$M(n) = \frac{4^k(4^k-1)}2 + 6m4^k + 6\sum_{r=0}^{m-1}\operatorname{supp}(r).$$

The remaining sum is computed recursively.

Python implementation used:

MOD = 10**9 + 7

from functools import lru_cache

@lru_cache(None)
def fullS(k):
    # Sum of supp(r) for 0 <= r < 4^k
    if k == 0:
        return 0
    p = 4 ** (k - 1)
    return 4 * fullS(k - 1) + 3 * p * p

def S(k, m):
    # Sum of supp(r) for 0 <= r < m, with r < 4^k
    if k == 0 or m == 0:
        return 0

    p = 4 ** (k - 1)
    a, b = divmod(m, p)

    return (
        a * fullS(k - 1)
        + max(0, a - 1) * p * p
        + (p * b if a else 0)
        + S(k - 1, b)
    )

def M(n):
    k = 0
    while (4 ** (k + 1) - 1) // 3 <= n:
        k += 1

    T = (4 ** k - 1) // 3
    m = n - T

    base = 4 ** k * (4 ** k - 1) // 2

    return base + 6 * m * 4 ** k + 6 * S(k, m)

ans = M(10**18) % MOD
print(ans)

Checks:

$M(10)=642$
$M(1000)=5432148$

both matching the statement.

Therefore,

Answer: 552839586