Detailed mathematical approach

Problem Summary

For a positive integer \(n\), define \(\operatorname{streak}(n)=k\) to be the smallest positive integer \(k\) such that \(n+k\) is not divisible by \(k+1\). Equivalently, the divisibility tests succeed for \(2,3,\dots,k\) and then fail at the next one.

The function \(P(s,N)\) counts how many integers \(n\) satisfy

$1 \lt n \lt N,\qquad \operatorname{streak}(n)=s.$

The goal is to compute

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

A direct scan up to \(4^{31}\) would be hopeless, so the solution must convert the divisibility streak into a small number of arithmetic formulas.

Mathematical Approach

The key observation is that the whole streak condition collapses into a single congruence modulo a least common multiple.

Step 1: Rewrite the streak condition as divisibility constraints

If \(\operatorname{streak}(n)\ge s\), then the first \(s-1\) tests all succeed. That means

$n+1\equiv 0\pmod{2},\quad n+2\equiv 0\pmod{3},\quad \dots,\quad n+s-1\equiv 0\pmod{s}.$

For a fixed divisor \(m\in\{2,3,\dots,s\}\), the relevant condition is

$n+(m-1)\equiv 0\pmod m.$

Since \(m-1\equiv -1\pmod m\), this is equivalent to

$n-1\equiv 0\pmod m,$

or simply

$n\equiv 1\pmod m.$

So a streak of length at least \(s\) means that \(n\) is congruent to \(1\) modulo every integer from \(2\) through \(s\).

Step 2: Collapse all congruences into one modulus

Let

$L_s=\operatorname{lcm}(1,2,\dots,s).$

Including \(1\) changes nothing numerically, but it keeps the notation tidy. Because \(L_s\) is divisible by every \(m\le s\), the condition

$n\equiv 1\pmod{L_s}$

immediately implies

$n\equiv 1\pmod m\qquad\text{for all }2\le m\le s.$

The converse is also true: if \(n\equiv 1\pmod m\) for every \(m=2,3,\dots,s\), then \(n-1\) is a common multiple of all those integers, hence a multiple of their least common multiple. Therefore

$\operatorname{streak}(n)\ge s \iff n\equiv 1\pmod{L_s}.$

This is the central compression step of the whole problem.

Step 3: Convert “at least \(s\)” into “exactly \(s\)”

Now we want \(\operatorname{streak}(n)=s\), not merely \(\ge s\). That means the first \(s-1\) divisibility tests succeed, but the next test fails. In congruence language:

$\operatorname{streak}(n)=s \iff \operatorname{streak}(n)\ge s\text{ and }\operatorname{streak}(n)\not\ge s+1.$

Using the previous step, this becomes

$\operatorname{streak}(n)=s \iff n\equiv 1\pmod{L_s}\text{ and }n\not\equiv 1\pmod{L_{s+1}}.$

So the desired count is the number of integers congruent to \(1\) modulo \(L_s\), minus the number of integers congruent to \(1\) modulo the stronger modulus \(L_{s+1}\).

Step 4: Count the solutions in the open interval \(1 \lt n \lt N\)

Suppose we want to count integers in the open interval \(1 \lt n \lt N\) such that

$n\equiv 1\pmod L.$

Every such integer has the form

$n=1+kL$

for some integer \(k\ge 1\). The upper bound \(n\lt N\) is equivalent to

$1+kL\le N-1,$

so

$kL\le N-2,\qquad k\le \left\lfloor \frac{N-2}{L}\right\rfloor.$

Hence the number of admissible \(n\) is exactly

$\left\lfloor \frac{N-2}{L}\right\rfloor.$

Applying this to the two moduli \(L_s\) and \(L_{s+1}\) yields the closed formula

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

Step 5: Specialize to the required Euler sum

The problem asks for

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

Substituting the formula above gives

$\sum_{i=1}^{31}\left(\left\lfloor\frac{4^i-2}{L_i}\right\rfloor-\left\lfloor\frac{4^i-2}{L_{i+1}}\right\rfloor\right),\qquad L_i=\operatorname{lcm}(1,2,\dots,i).$

So once the lcm table \(L_1,L_2,\dots,L_{32}\) is precomputed, each term is just two integer divisions and one subtraction.

Worked Example

The small checkpoint \(P(3,14)=1\) falls out immediately. We have

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

Therefore

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

Indeed, the integers congruent to \(1\) modulo \(6\) inside \(1 \lt n \lt 14\) are \(7\) and \(13\), but \(13\equiv 1\pmod{12}\) as well, so only \(7\) has streak exactly \(3\).

A larger checkpoint is

$L_6=60,\qquad L_7=420,$

hence

$P(6,10^6)=\left\lfloor\frac{999998}{60}\right\rfloor-\left\lfloor\frac{999998}{420}\right\rfloor=16666-2380=14286.$

These examples match the arithmetic used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First, they precompute the least common multiples \(L_0,L_1,\dots,L_{32}\), where \(L_0=1\) and each next value is obtained from the previous one by the identity

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

This avoids repeated factorization and builds exactly the moduli needed for the queries \(P(i,4^i)\).

Next, the implementation uses a small arithmetic routine for the count of integers congruent to \(1\) modulo \(L\) in the open interval \(1 \lt n \lt N\). That routine returns

$\left\lfloor\frac{N-2}{L}\right\rfloor,$

with a trivial zero result when the modulus is already larger than \(N-2\).

Then each term \(P(s,N)\) is computed by subtracting the count for \(L_{s+1}\) from the count for \(L_s\). Finally, the program iterates through \(i=1,2,\dots,31\), updates the current power \(4^i\), and accumulates the resulting terms. No search over candidate values of \(n\) is performed at any stage.

Complexity Analysis

If we write \(S\) for the largest streak length being queried, precomputing \(L_1,\dots,L_{S+1}\) takes \(S\) gcd/lcm updates. With the Euclidean algorithm for gcd, that is \(O(S\log S)\) arithmetic time in the usual machine-integer model and \(O(S)\) memory to store the table. After that, each query \(P(s,N)\) is \(O(1)\).

For the actual problem, \(S=31\). Therefore the real running time and memory usage are both effectively constant.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=601
2. Least common multiple: Wikipedia - Least common multiple
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Greatest common divisor and the Euclidean algorithm: Wikipedia - Euclidean algorithm