Detailed mathematical approach

Problem Summary

We must count integers in the half-open range \(1 \le x < N\) with \(N=10^{16}\) such that \(x\) is divisible by at least four distinct primes below \(100\). Multiplicity does not matter: a prime like \(2\) contributes only once, whether \(x\) is divisible by \(2\) or by \(2^{20}\).

The C++ program exposes the bound as --limit=<N>, so the same method works for any \(N\ge 1\).

Mathematical Approach

1. The Relevant Prime Set

Let

$\mathcal P=\{p \text{ prime}: p<100\}.$

There are \(25\) such primes. For a subset \(S\subseteq\mathcal P\), define its squarefree product

$q_S=\prod_{p\in S}p.$

An integer \(x\) is divisible by every prime in \(S\) exactly when \(q_S\mid x\). Therefore the number of integers \(x<N\) divisible by all primes of \(S\) is

$\left\lfloor\frac{N-1}{q_S}\right\rfloor.$

The code uses \(N-1\) because the searched range is \(1\le x<N\), not \(1\le x\le N\).

2. Grouping by Subset Size

For each \(k\ge4\), define

$T_k=\sum_{|S|=k}\left\lfloor\frac{N-1}{q_S}\right\rfloor.$

So \(T_k\) counts, with multiplicity, how many numbers are divisible by every prime in some \(k\)-element subset of \(\mathcal P\).

If a number \(x\) has exactly \(r\) distinct prime divisors from \(\mathcal P\), then:

1. it appears in \(T_k\) exactly \(\binom{r}{k}\) times, because we may choose any \(k\) of those \(r\) primes,

2. it contributes nothing to \(T_k\) when \(k>r\).

So the whole problem is to find coefficients \(a_k\) such that

$\sum_{k=4}^{r} a_k\binom{r}{k}= \begin{cases} 0,&r<4,\\ 1,&r\ge4. \end{cases}$

3. The Correct Inclusion-Exclusion Weights

The program uses

$a_k=(-1)^{k-4}\binom{k-1}{3}.$

Thus the final answer is

$\sum_{k=4}^{25} a_kT_k =\sum_{k=4}^{25}(-1)^{k-4}\binom{k-1}{3}T_k.$

The first few coefficients are

$a_4=1,\qquad a_5=-4,\qquad a_6=10,\qquad a_7=-20,\dots$

So the formula starts as

$T_4-4T_5+10T_6-20T_7+\cdots.$

4. Why Those Weights Give “At Least Four”

Take a number with exactly \(r\) eligible prime factors. Its total weight becomes

$w(r)=\sum_{k=4}^{r}(-1)^{k-4}\binom{k-1}{3}\binom{r}{k}.$

For \(r<4\), this sum is empty, so \(w(r)=0\), exactly as required.

For \(r\ge4\), there is a neat closed-form evaluation. First use

$\binom{r}{k}\binom{k-1}{3}=\binom{r}{4}\binom{r-4}{k-4}\frac{4}{k}.$

Now write \(j=k-4\). Then

$w(r)=4\binom{r}{4}\sum_{j=0}^{r-4}(-1)^j\binom{r-4}{j}\frac{1}{j+4}.$

Using \(\frac{1}{j+4}=\int_0^1 x^{j+3}\,dx\), we get

$w(r)=4\binom{r}{4}\int_0^1 x^3(1-x)^{r-4}\,dx.$

This is a beta integral:

$\int_0^1 x^3(1-x)^{r-4}\,dx=\frac{3!(r-4)!}{r!}.$

Therefore

$w(r)=4\cdot\frac{r!}{4!(r-4)!}\cdot\frac{3!(r-4)!}{r!}=1.$

So every number with at least four distinct eligible primes contributes exactly once, and every number with fewer than four contributes zero.

5. A Concrete Overcount Example

The number \(2310=2\cdot3\cdot5\cdot7\cdot11\) has \(r=5\) eligible prime factors.

It appears in \(T_4\) exactly \(\binom54=5\) times, once for each choice of four of its five primes. It appears in \(T_5\) exactly \(\binom55=1\) time. It appears in no \(T_k\) with \(k\ge6\).

Its final weighted contribution is therefore

$1\cdot5+(-4)\cdot1=1.$

This is the simplest way to see why the coefficients correct the heavy overcount from \(T_4\).

6. DFS Enumeration and Pruning

The program never enumerates all \(2^{25}\) subsets explicitly. Instead it performs a depth-first search over increasing prime indices.

At a DFS state, the code knows:

1. the next prime index it may use,

2. how many primes have already been taken,

3. the current squarefree product \(q_S\).

If taken >= 4, the code immediately adds

$\left\lfloor\frac{N-1}{q_S}\right\rfloor$

to subset_sums[taken].

Before multiplying by a new prime \(p\), it checks

$q_S \le \frac{N-1}{p},$

implemented as product > max_value / p. This avoids overflow and prunes any branch whose product already exceeds \(N-1\).

7. Small Checkpoints

The first checkpoint is

$\texttt{solve}(1000)=23.$

Indeed, the numbers below \(1000\) with at least four distinct primes below \(100\) are exactly \(23\) in number; examples include \(210,330,390,462,\dots,990\).

The second checkpoint compares

$\texttt{solve}(100000)$

against a brute-force routine that explicitly counts distinct prime divisors for every \(x<100000\). This confirms that the weighted subset formula and the DFS implementation match the direct definition.

How the Code Works

primes_below_100() generates the 25 primes less than \(100\) with a small linear sieve.

solve(limit) sets max_value = limit - 1, runs the DFS, stores all \(T_k\)-type totals in subset_sums, then forms the weighted sum with coefficients \((-1)^{k-4}\binom{k-1}{3}\).

binom is only used for those small coefficients, so 64-bit signed integers are sufficient.

The command-line interface accepts --limit=<N> and --skip-checkpoints.

Complexity Analysis

The theoretical subset space has size \(2^{25}\), but in practice most branches are cut immediately once the squarefree product becomes too large. The main cost is therefore the number of valid subset products \(q_S\le N-1\), not the full power set.

The final weighted sum over \(k=4,\dots,25\) is tiny compared with the DFS itself, and memory usage is \(O(25)\) beyond the recursion stack because only the prime list and the 26-element accumulator array are stored.

Further Reading

1. Problem page: https://projecteuler.net/problem=268
2. Inclusion-exclusion principle: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
3. Binomial identities: https://en.wikipedia.org/wiki/Binomial_coefficient