Project Euler Problem 970

Solution

Answer: 44754029

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

Condition on the first hop $U\sim \mathrm{Uniform}(0,1)$:

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

with $H(x)=0$ for $x<0$.

Taking Laplace transforms,

$$\mathcal L{H}(s) = \frac{1}{s-1+e^{-s}}.$$

The poles are given by

$$s-1+e^{-s}=0.$$

At $s=0$ there is a double pole, producing the main term

$$H(x)=2x+\frac23+\text{(exponentially tiny corrections)}.$$

The remaining poles are

$$s_k = 1 + W_k(-e^{-1}),$$

where $W_k$ is the Lambert $W$-function.

The dominant correction comes from the conjugate pair

$$s \approx -2.0888430156130439 \pm 7.4614892856542546,i.$$

Using residues,

$$H(n) = 2n+\frac23 + 2\Re!\left(\frac{e^{sn}}{s}\right) + O!\left(e^{-2.664,n}\right).$$

For $n=10^6$,

$$2\Re!\left(\frac{e^{sn}}{s}\right) \approx -2.019126374261300197\ldots \times 10^{-907174}.$$

Hence

$$H(10^6) = 2000000.6666\ldots - 2.019126374261300197\ldots \times 10^{-907174}.$$

So after a huge run of $6$'s, the decimal expansion locally looks like

$$\cdots 666664647540292405\ldots$$

Removing all $6$'s and taking the first eight remaining digits gives

$$44754029.$$

Answer: 44754029