Project Euler Problem 347

Solution

Answer: 11109800204052

We need to compute

$$S(N)=\sum_{\substack{p<q\ p,q\text{ primes}}} M(p,q,N),$$

where $M(p,q,N)$ is the largest integer $\le N$ whose prime divisors are exactly $p$ and $q$.

For example,

$$M(2,3,100)=96=2^5\cdot 3,$$

$$M(3,5,100)=75=3\cdot 5^2.$$

We are asked for

$$S(10^7).$$

---

Mathematical analysis

A number counted by $M(p,q,N)$ has the form

$$p^a q^b,$$

with

$$a\ge1,\qquad b\ge1,$$

and no other prime factors.

So for fixed distinct primes $p,q$,

$$M(p,q,N)=\max {p^a q^b \le N}.$$

If no such number exists, then $M=0$.

---

Key observation

Suppose $p q > N$.

Then even the smallest number divisible by both $p$ and $q$ exceeds $N$, so

$$M(p,q,N)=0.$$

Therefore we only need prime pairs satisfying

$$pq \le N.$$

For $N=10^7$, this is manageable.

---

Efficient computation of $M(p,q,N)$

For fixed $p,q$, we want

$$\max p^a q^b \le N.$$

A brute force over all exponents is fast enough because powers grow exponentially.

Algorithm:

• Generate all powers of $p$:

$$p,p^2,p^3,\dots$$

up to $N$.

• Generate all powers of $q$:

$$q,q^2,q^3,\dots$$

up to $N$.

• Check every product $p^a q^b\le N$, keeping the maximum.

The number of powers is tiny:

$$\log_2(10^7)\approx 23.$$

So each pair costs only a few hundred operations.

---

Number of prime pairs

We need all primes up to $N$, but only pairs with

$$pq\le N.$$

For each prime $p$, valid $q$ satisfy

$$q\le \frac{N}{p}.$$

This leads to roughly a few hundred thousand pairs — entirely feasible.

---

Python implementation

from math import isqrt

N = 10_000_000

# ------------------------------------------------------------
# Sieve of Eratosthenes
# ------------------------------------------------------------
def prime_sieve(limit):
    sieve = bytearray(b"\x01") * (limit + 1)
    sieve[0:2] = b"\x00\x00"

    for i in range(2, isqrt(limit) + 1):
        if sieve[i]:
            step = i
            start = i * i
            sieve[start:limit + 1:step] = b"\x00" * (((limit - start) // step) + 1)

    return [i for i in range(limit + 1) if sieve[i]]

primes = prime_sieve(N // 2)

# ------------------------------------------------------------
# Compute M(p,q,N)
# ------------------------------------------------------------
def M(p, q, N):
    best = 0

    # Generate powers of p
    pp = p
    p_powers = []
    while pp <= N:
        p_powers.append(pp)
        pp *= p

    # Generate powers of q
    qq = q
    q_powers = []
    while qq <= N:
        q_powers.append(qq)
        qq *= q

    # Try all products
    for a in p_powers:
        for b in q_powers:
            val = a * b
            if val <= N:
                if val > best:
                    best = val

    return best

# ------------------------------------------------------------
# Compute S(N)
# ------------------------------------------------------------
total = 0

L = len(primes)

for i in range(L):
    p = primes[i]

    if p * p > N:
        break

    for j in range(i + 1, L):
        q = primes[j]

        if p * q > N:
            break

        total += M(p, q, N)

print(total)

---

Code walkthrough

Prime sieve

primes = prime_sieve(N // 2)

We only need primes up to $N/2$, because if $p>N/2$, then for any distinct prime $q\ge2$,

$$pq>N.$$

The sieve efficiently generates all such primes.

---

Function M(p,q,N)

We first build all powers of $p$:

pp = p
while pp <= N:
    p_powers.append(pp)
    pp *= p

Similarly for $q$.

Then we test every product:

val = a * b

If it satisfies

$$val \le N,$$

we maximize it.

---

Main summation loop

For every prime pair:

if p * q > N:
    break

we stop immediately because larger $q$ only increase the product.

Each valid pair contributes exactly one value $M(p,q,N)$.

---

Verification on the small example

For $N=100$:

• $M(2,3,100)=96$
• $M(3,5,100)=75$
• $M(2,73,100)=0$

The program reproduces

$$S(100)=2262.$$

So the method is correct.

---

Final computation

Running the program for

$$N=10^7$$

gives

$$11109800204052.$$

This magnitude is reasonable:

• there are many contributing prime pairs,
• each contributes at most $10^7$,
• total is around $10^{13}$, which fits expectations.

---

Answer: 11109800204052