Project Euler Problem 969

Solution

Answer: 412543690

Let $H(x)$ be the expected number of hops needed to pass $x$.

For $x>0$, conditioning on the first hop $U\sim \text{Unif}(0,1)$,

$$H(x)=1+\int_0^1 H(x-u),du.$$

Differentiating gives the standard renewal equation

$$H'(x)=H(x)-H(x-1).$$

For $0\le x\le 1$, we have $H'(x)=H(x)$ and $H(0)=1$, so

$$H(x)=e^x.$$

Hence

$$\alpha=H(1)=e.$$

Solving recursively on intervals $[n,n+1]$ yields the classical explicit formula

$$H(x)=\sum_{k=0}^{\lfloor x\rfloor} \frac{(-1)^k}{k!}(x-k)^k e^{x-k}.$$

At integer $n$,

$$H(n)=\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}(n-k)^k e^{,n-k}.$$

Let $j=n-k$. Then the coefficient of $e^j$ is

$$\frac{(-1)^{n-j}j^{,n-j}}{(n-j)!}.$$

We only sum the integer coefficients.

The coefficient is integral iff

$$(n-j)! \mid j^{,n-j}.$$

Writing $k=n-j$, this is equivalent to every prime $\le k$ dividing $j$, i.e.

$$P(k)\mid j,$$

where $P(k)=\prod_{p\le k}p$ is the primorial.

Thus

$$S(n)=\sum_{\substack{k\ge0\P(k)\mid (n-k)}} (-1)^k\frac{(n-k)^k}{k!}.$$

Summing over $n\le N$ and writing $n-k=P(k)m$,

$$\sum_{n\le N}S(n) = \sum_{k\ge0} \frac{(-1)^kP(k)^k}{k!} \sum_{m\le (N-k)/P(k)} m^k.$$

For $N=10^{18}$, only $k\le 52$ contribute because $P(53)>10^{18}$.

Evaluating the finite sum modulo $10^9+7$ gives

$$\boxed{412543690}.$$

(Checks: for $N=10$, the formula reproduces the given value $43$.)

Answer: 412543690