Detailed mathematical approach

Problem Summary

Let \(Q(N)\) denote the number of squarefree positive integers not exceeding \(N\). Problem 193 asks for \(Q(2^{50})\), where an integer is squarefree if no prime square divides it.

The implementations compute this count by turning the condition “has no square prime factor” into an exact divisor sum. This also matches the original wording “below \(2^{50}\)”, because \(2^{50}\) itself is divisible by \(4\) and therefore is not squarefree.

Mathematical Approach

A direct approach would test each integer separately and look for a square divisor. The real solution reverses that viewpoint: instead of scanning numbers one by one, it counts how many integers are multiples of each square and combines those counts with Möbius signs.

Detecting square factors with the Möbius function

Write \(\mu(d)\) for the Möbius function. For a fixed integer \(n\), consider

$\sum_{d^2\mid n}\mu(d).$

Only squarefree values of \(d\) can contribute, because \(\mu(d)=0\) whenever \(d\) contains a repeated prime factor. If \(S(n)\) is the set of primes whose squares divide \(n\), then every contributing \(d\) is the product of a subset of \(S(n)\). Therefore

$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$

If no prime square divides \(n\), then \(S(n)\) is empty and the sum is \(1\). Otherwise the sum is \(0\). So we obtain the exact indicator

$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$

This is inclusion-exclusion in a compact number-theoretic form: the squarefree condition is encoded by the square divisors \(d^2\).

From the indicator to a single counting formula

Summing the indicator over \(1\le n\le N\) gives

$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$

Now interchange the order of summation. For a fixed \(d\), the condition \(d^2\mid n\) means that \(n\) is a multiple of \(d^2\), and there are exactly \(\left\lfloor N/d^2\right\rfloor\) such multiples. Hence

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

The upper limit is \(\lfloor\sqrt N\rfloor\) because the floor term becomes zero as soon as \(d^2>N\). For Problem 193 this means the whole computation only needs

$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432$

Möbius values, not data up to \(2^{50}\).

Worked example: \(Q(100)=61\)

For \(N=100\), only \(d\le 10\) matter. The nonzero Möbius values in that range are

$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$

while \(\mu(4)=\mu(8)=\mu(9)=0\). Substituting into the formula gives

$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$

Numerically,

$Q(100)=100-25-11-4+2-2+1=61.$

This matches the first checkpoint in the reference implementation and shows exactly how the alternating inclusion-exclusion terms combine.

The Möbius recurrence used by the sieve

Once the counting formula is known, the remaining task is to compute \(\mu(d)\) for every \(d\le \lfloor\sqrt N\rfloor\). The implementations do this with a linear sieve that maintains a prime list and a composite marker array.

The recurrence follows directly from the definition of \(\mu\):

$\mu(1)=1.$

If \(i\) is newly discovered to be prime, then \(\mu(i)=-1\). For each prime \(p\) and each current \(i\), form \(v=ip\). If \(p\mid i\), then \(p^2\mid v\), so \(\mu(v)=0\) and the inner loop stops for that \(i\). If \(p\nmid i\), then \(v\) gains one new distinct prime factor, so

$\mu(v)=-\mu(i).$

Because every composite number is generated once through its smallest prime factor, the Möbius table is filled in linear time up to \(\lfloor\sqrt N\rfloor\).

How the Code Works

The C++, Python, and Java implementations all follow the same two-phase structure. First they set the target limit \(N\), compute \(M=\lfloor\sqrt N\rfloor\), and build the Möbius table \(\mu(1),\mu(2),\dots,\mu(M)\) with the linear-sieve recurrence above. The C++ version also supports a custom limit and can run built-in checkpoints at \(N=100\) and \(N=1024\).

After the sieve is complete, the implementations evaluate the exact formula

$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$

Terms with \(\mu(k)=0\) are skipped immediately, so only squarefree \(k\) contribute. The running total is accumulated in 64-bit integer arithmetic, which is sufficient here because \(k^2\le N=2^{50}\) and the final count is safely inside that range.

No implementation tests every integer up to \(N\) for square divisibility, and no implementation factors numbers near \(2^{50}\). All of the work is concentrated in the Möbius table up to \(2^{25}\) and the final divisor-sum pass.

Complexity Analysis

Let \(M=\lfloor\sqrt N\rfloor\). The linear sieve runs in \(O(M)\) time, and the final summation over \(k=1,\dots,M\) is another \(O(M)\) pass. Therefore the total running time is

$O(\sqrt N).$

The memory usage is also \(O(M)\), coming from the Möbius array, the composite-marker array, and the prime list. For Problem 193 this means \(O(2^{25})\) storage rather than anything proportional to \(2^{50}\), which is exactly what makes the computation practical.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=193
2. Square-free integer: Wikipedia - Square-free integer
3. Möbius function: Wikipedia - Möbius function
4. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
5. Linear sieve: cp-algorithms - Linear Sieve