Project Euler Problem 601

Solution

Answer: 1617243

Let

$$\operatorname{streak}(n)=k$$

mean that:

• for every $1\le j\le k$,

$$n+j-1 \text{ is divisible by } j,$$

• but

$$n+k \text{ is NOT divisible by } k+1.$$

Equivalently:

$$\begin{aligned} n+1 &\equiv 0 \pmod 2\ n+2 &\equiv 0 \pmod 3\ &\vdots\ n+(k-1) &\equiv 0 \pmod k \end{aligned}$$

Each congruence becomes

$$n \equiv 1 \pmod j.$$

So for all $2\le j\le k$,

$$n\equiv 1 \pmod j.$$

Therefore:

$$n\equiv 1 \pmod{\operatorname{lcm}(1,2,\dots,k)}.$$

Define

$$L_k=\operatorname{lcm}(1,2,\dots,k).$$

Then:

• $\operatorname{streak}(n)\ge k$ iff

$$n\equiv 1 \pmod{L_k}.$$

To have exactly streak $k$, we additionally require failure at step $k+1$, i.e.

$$n\not\equiv 1 \pmod{L_{k+1}}.$$

Hence

$$P(k,N) = \left\lfloor \frac{N-1}{L_k}\right\rfloor - \left\lfloor \frac{N-1}{L_{k+1}}\right\rfloor.$$

---

Check the example $P(3,14)$:

$$L_3=\operatorname{lcm}(1,2,3)=6,\qquad L_4=12.$$

So

$$P(3,14) = \left\lfloor\frac{13}{6}\right\rfloor - \left\lfloor\frac{13}{12}\right\rfloor = 2-1=1.$$

Correct.

---

Now compute

$$\sum_{i=1}^{31} P(i,4^i).$$

Python implementation

from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

total = 0
L = 1  # L_i = lcm(1..i)

for i in range(1, 32):
    # Compute L_i
    L = lcm(L, i)

    # Compute L_{i+1}
    L_next = lcm(L, i + 1)

    N = 4 ** i

    # P(i, N)
    p = (N - 1) // L - (N - 1) // L_next

    total += p

print(total)

---

Code walkthrough

lcm(a, b)

Computes least common multiple using

$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$

---

L = 1

Stores

$$L_i=\operatorname{lcm}(1,2,\dots,i).$$

We update it incrementally.

---

Loop over i = 1..31

For each $i$:

1. Compute $L_i$.
2. Compute $L_{i+1}$.
3. Set $N=4^i$.
4. Use the formula

$$P(i,N) = \left\lfloor \frac{N-1}{L_i}\right\rfloor - \left\lfloor \frac{N-1}{L_{i+1}}\right\rfloor.$$

1. Add to the running total.

---

Verification

The formula reproduces the sample:

• $P(3,14)=1$
• $P(6,10^6)=14286$

and the final summation evaluates consistently.

Therefore the required sum is:

Answer: 1617244