Project Euler Problem 643

Project Euler Problem 643

Solution

Answer: 968274154

Let

$$f(n)=#{(p,q):1\le p<q\le n,\ \gcd(p,q)=2^t,\ t>0}.$$

We need $f(10^{11}) \bmod 1,000,000,007$.

1. Mathematical analysis

If $\gcd(p,q)=2^t$ with $t>0$, write

$$p=2^t a,\qquad q=2^t b,$$

where $\gcd(a,b)=1$.

Since $p<q\le n$,

$$1\le a<b\le \left\lfloor \frac{n}{2^t}\right\rfloor.$$

Thus for each $t\ge 1$, the number of valid pairs equals the number of coprime pairs $(a,b)$ with $a<b\le m$, where

$$m=\left\lfloor \frac{n}{2^t}\right\rfloor.$$

Counting coprime pairs

For fixed $b$, the number of $a<b$ with $\gcd(a,b)=1$ is Euler’s totient:

$$\varphi(b).$$

Hence

$$C(m)=\sum_{b=2}^{m}\varphi(b).$$

Define the totient summatory function

$$\Phi(m)=\sum_{k=1}^{m}\varphi(k).$$

Then

$$C(m)=\Phi(m)-1.$$

Therefore,

$$f(n) = \sum_{t\ge 1} \left( \Phi!\left(\left\lfloor \frac{n}{2^t}\right\rfloor\right)-1 \right).$$

Since $2^t>n$ eventually, only $O(\log n)$ terms exist.

---

Fast computation of $\Phi(n)$

Use the classical identity

$$\sum_{d\le n}\varphi(d)\left\lfloor \frac{n}{d}\right\rfloor = \frac{n(n+1)}{2}.$$

Rearranging:

$$\Phi(n) = \frac{n(n+1)}{2} - \sum_{d=2}^{n} \Phi!\left(\left\lfloor \frac{n}{d}\right\rfloor\right).$$

The key optimization is grouping equal values of $\lfloor n/d\rfloor$:

if

$$v=\left\lfloor \frac{n}{d}\right\rfloor,$$

then all $d\in[l,r]$ share the same $v$, where

$$r=\left\lfloor \frac{n}{v}\right\rfloor.$$

This reduces complexity to roughly $O(n^{2/3})$-style memoized divide-and-conquer, fast enough for $10^{11}$.

---

2. Python implementation

MOD = 1_000_000_007
LIMIT = 5_000_000

# Sieve Euler phi up to LIMIT
phi = list(range(LIMIT + 1))

for i in range(2, LIMIT + 1):
    if phi[i] == i:  # i is prime
        for j in range(i, LIMIT + 1, i):
            phi[j] -= phi[j] // i

# Prefix sums of phi
phi_prefix = [0] * (LIMIT + 1)

running = 0
for i in range(LIMIT + 1):
    running += phi[i]
    phi_prefix[i] = running

# Memoized summatory totient
memo = {0: 0}

def Phi(n):
    """Return sum_{k<=n} phi(k)."""
    if n <= LIMIT:
        return phi_prefix[n]

    if n in memo:
        return memo[n]

    result = n * (n + 1) // 2

    l = 2
    while l <= n:
        v = n // l
        r = n // v

        result -= (r - l + 1) * Phi(v)
        l = r + 1

    memo[n] = result
    return result

def f(n):
    total = 0
    t = 1

    while True:
        m = n >> t  # floor(n / 2^t)

        if m == 0:
            break

        total += Phi(m) - 1
        total %= MOD

        t += 1

    return total

print(f(10**11))

---

3. Code walkthrough

Step 1: Totient sieve

We compute all $\varphi(k)$ up to a cutoff (LIMIT = 5_000_000) using the standard Euler sieve.

Step 2: Prefix sums

We build

$$\Phi(n)=\sum_{k\le n}\varphi(k)$$

for all small $n$.

Step 3: Recursive summatory totient

For large $n$, we use

$$\Phi(n) = \frac{n(n+1)}{2} - \sum_{d=2}^{n} \Phi!\left(\left\lfloor \frac{n}{d}\right\rfloor\right),$$

grouping identical quotients to make it efficient.

Step 4: Compute $f(n)$

We sum

$$\Phi!\left(\left\lfloor n/2^t\right\rfloor\right)-1$$

for $t=1,2,\dots$.

---

Verification on given examples

For $n=100$:

$$f(100)=1031,$$

matching the statement.

For $n=10^6$:

$$f(10^6)\equiv 321418433 \pmod{1,000,000,007},$$

also matching the statement.

So the derivation and implementation are consistent.

---

The computation for $n=10^{11}$ gives:

Answer: 968274154