Project Euler Problem 362

Project Euler Problem 362

Solution

Answer: 457895958010

Let a squarefree factorization of $n$ mean an unordered factorization into integers $>1$, where every factor is squarefree.

We define:

$$\operatorname{Fsf}(n)$$

as the number of such factorizations, and

$$S(N)=\sum_{k=2}^{N}\operatorname{Fsf}(k).$$

We are given:

$$S(100)=193.$$

We must compute:

$$S(10^{10}).$$

---

1. Mathematical analysis

Reinterpreting $S(N)$

Instead of summing over $n$, count all valid squarefree factorizations directly.

Each contribution to $\operatorname{Fsf}(n)$ is an unordered multiset of squarefree integers $>1$ whose product is $n$.

Therefore:

$$S(N)$$

is exactly the number of unordered multisets of squarefree integers $>1$ whose product is at most $N$.

---

Canonical ordering

To avoid overcounting, impose nondecreasing order on factors:

$$q_1 \le q_2 \le \cdots \le q_r,$$

where every $q_i$ is squarefree.

Define:

$$A(N,m)$$

to be the number of such factorizations with all factors at least $m$, and product $\le N$.

Then:

$$S(N)=A(N,2).$$

---

Recursive formula

Choose the smallest factor $q$, which must be squarefree and satisfy:

$$m \le q \le N.$$

After choosing $q$:

• we get one valid factorization consisting only of $q$,
• or we continue factoring the remaining bound $N/q$, keeping factors $\ge q$.

Thus:

$$A(N,m) = \sum_{\substack{q\ \text{squarefree}\ q\ge m\ q\le N}} \Bigl(1+A(\lfloor N/q\rfloor,q)\Bigr).$$

Now observe:

If

$$q>\sqrt N,$$

then

$$\lfloor N/q\rfloor<q,$$

so recursion is impossible.

Hence:

$$A(N,m) = Q(N)-Q(m-1) + \sum_{\substack{m\le q\le \sqrt N\ q\ \text{squarefree}}} A(\lfloor N/q\rfloor,q),$$

where $Q(x)$ counts squarefree integers $>1$ up to $x$.

---

Counting squarefree integers

Using Möbius inversion:

$$Q(x) = \sum_{d\le \sqrt x}\mu(d) \left\lfloor \frac{x}{d^2}\right\rfloor -1.$$

(The $-1$ excludes the number $1$.)

Since:

$$\sqrt{10^{10}}=100000,$$

we only need Möbius values up to $10^5$.

Memoizing the recursion makes the computation feasible.

---

2. Python implementation

from math import isqrt
from bisect import bisect_right
from functools import lru_cache

N = 10_000_000_000
LIMIT = isqrt(N)

# -------------------------------
# Möbius function (linear sieve)
# -------------------------------
mu = [0] * (LIMIT + 1)
mu[1] = 1

primes = []
composite = [False] * (LIMIT + 1)

for i in range(2, LIMIT + 1):
    if not composite[i]:
        primes.append(i)
        mu[i] = -1

    for p in primes:
        v = i * p
        if v > LIMIT:
            break

        composite[v] = True

        if i % p == 0:
            mu[v] = 0
            break
        else:
            mu[v] = -mu[i]

# --------------------------------
# List of squarefree numbers <= LIMIT
# --------------------------------
squarefree = [x for x in range(2, LIMIT + 1) if mu[x] != 0]

# Prefix count of squarefree numbers (>1)
prefix_sf = [0] * (LIMIT + 1)
count = 0

for i in range(LIMIT + 1):
    if i >= 2 and mu[i] != 0:
        count += 1
    prefix_sf[i] = count

# --------------------------------
# Count squarefree numbers <= x
# --------------------------------
@lru_cache(None)
def Q(x):
    if x <= LIMIT:
        return prefix_sf[x]

    r = isqrt(x)
    total = 0

    for d in range(1, r + 1):
        if mu[d] != 0:
            total += mu[d] * (x // (d * d))

    return total - 1   # exclude 1

# --------------------------------
# Recursive counting
# --------------------------------
@lru_cache(None)
def A(n, idx):
    """
    Count squarefree factorizations
    using factors >= squarefree[idx].
    """
    m = squarefree[idx]

    # Count one-factor factorizations
    total = Q(n) - Q(m - 1)

    # Recursive part only needed up to sqrt(n)
    limit = isqrt(n)
    end = bisect_right(squarefree, limit)

    for j in range(idx, end):
        q = squarefree[j]
        total += A(n // q, j)

    return total

answer = A(N, 0)
print(answer)

---

3. Code walkthrough

Step 1: Möbius sieve

We compute $\mu(n)$ up to $100000$ using a linear sieve.

This allows efficient evaluation of:

$$Q(x) = \sum \mu(d)\left\lfloor x/d^2\right\rfloor - 1.$$

---

Step 2: Generate squarefree numbers

A number is squarefree iff:

$$\mu(n)\neq 0.$$

We store all squarefree integers up to $100000$.

---

Step 3: Recursive counting

A(n, idx) counts all valid factorizations whose smallest factor is at least:

squarefree[idx]

The term:

Q(n) - Q(m - 1)

counts all single-factor choices.

Then we recurse only for:

$$q \le \sqrt n,$$

because larger $q$ cannot be followed by another factor.

Memoization avoids recomputation.

---

Verification on the sample

For $N=100$:

A(100, 0)

returns:

$$193$$

matching the problem statement.

---

4. Final verification

• The sample $S(100)=193$ matches exactly.
• The recursion is mathematically exact and avoids overcounting via sorted factors.
• Möbius squarefree counting is standard and efficient.
• Computation finishes comfortably for $10^{10}$.

Therefore:

Answer: 457895958010