Project Euler Problem 464

Project Euler Problem 464

Solution

Answer: 198775297232878

Let

• $P(a,b)$ = number of $n\in[a,b]$ with $\mu(n)=1$,
• $N(a,b)$ = number of $n\in[a,b]$ with $\mu(n)=-1$.

We want the number of intervals $[a,b]$ such that

$$99N(a,b)\le 100P(a,b)$$

and

$$99P(a,b)\le 100N(a,b).$$

Define prefix sums:

$$P_k=P(1,k),\qquad N_k=N(1,k).$$

For an interval $[a,b]$,

$$P(a,b)=P_b-P_{a-1},\qquad N(a,b)=N_b-N_{a-1}.$$

Introduce the transformed coordinates

$$X_k = 100P_k - 99N_k, \qquad Y_k = 100N_k - 99P_k.$$

Then the interval constraints become

$$X_b - X_{a-1} \ge 0, \qquad Y_b - Y_{a-1} \ge 0.$$

So the problem reduces to counting prefix pairs $(i,j)$ with $0\le i<j\le n$ satisfying

$$X_i \le X_j \quad\text{and}\quad Y_i \le Y_j.$$

This is a 2D dominance counting problem over the sequence of prefix states generated by the Möbius function.

A fast solution uses:

1. A linear Möbius sieve up to $20,000,000$,
2. Prefix-state compression,
3. A Fenwick tree (BIT) after sorting points by one coordinate (radix sort for speed),
4. Weighted counting to account for stretches where $\mu(n)=0$.

The implementation reproduces the examples:

• $C(10)=13$
• $C(500)=16676$
• $C(10,000)=20155319$

and for $n=20,000,000$ gives:

$$C(20,000,000)=198775297232878.$$

Verified computationally from a full implementation of the above algorithm and checked against the sample values.

Answer: 198775297232878