Detailed mathematical approach

Problem Summary

For each integer \(n \ge 2\), let \(\operatorname{fsf}(n)\) denote the number of unordered factorizations of \(n\) into squarefree factors greater than 1. Repeated factors are allowed as long as each factor itself is squarefree. The Project Euler quantity is

$S(N)=\sum_{n=2}^{N}\operatorname{fsf}(n),\qquad N=10^{10}.$

As a small example, \(12=2^2\cdot 3\) has exactly two valid factorizations:

$12=2\cdot 2\cdot 3=2\cdot 6,$

so \(\operatorname{fsf}(12)=2\). A direct scan up to \(10^{10}\) is impossible, so the implementation groups integers by their exponent pattern and counts entire families at once.

Mathematical Approach

Write the prime factorization of \(n\) as

$n=\prod_{i=1}^{r} p_i^{e_i},\qquad e_i\ge 1.$

The multiset of exponents \((e_1,\dots,e_r)\) is the only part that matters for the squarefree-factor count.

Step 1: Replace Unordered Factorizations by a System on Subsets

Every squarefree factor of \(n\) is obtained by choosing a nonempty subset \(J\subseteq\{1,\dots,r\}\) and taking

$f_J=\prod_{i\in J} p_i.$

Because the factorization is unordered, all we need is the multiplicity \(x_J\in\mathbb{Z}_{\ge 0}\) of each subset type. Prime \(p_i\) must appear exactly \(e_i\) times across all chosen factors, hence

$\sum_{J\ni i} x_J=e_i\qquad (1\le i\le r).$

So \(\operatorname{fsf}(n)\) is precisely the number of nonnegative integer solutions of this linear system. In particular, it depends only on the exponent signature, not on the actual prime values. If \(\sigma=(e_1,\dots,e_r)\), we may therefore write \(F(\sigma)\) for this common value.

Step 2: Count \(F(\sigma)\) with Memoized DFS

The C++ and Java implementations build all nonempty bitmasks \(J\), sort them by decreasing size, and recurse on a vector of remaining exponents. At one mask \(J\), the multiplicity \(x_J\) can be any value from \(0\) up to

$\min_{i\in J} \operatorname{remaining}_i.$

For each choice, the code subtracts that amount from every coordinate in \(J\) and continues with the next mask. The base case returns 1 if all remaining exponents are zero and 0 otherwise. Memoization uses the pair

$\bigl(\text{mask position},\text{remaining exponent vector}\bigr)$

as the state key. This is exactly what fsf_from_signature and its DFS helper implement.

Step 3: Worked Signature Example

For \(12=2^2\cdot 3\), the signature is \((2,1)\). There are three subset types: \(\{1\}\), \(\{2\}\), and \(\{1,2\}\). Writing their multiplicities as \(x_1,x_2,x_{12}\), the constraints become

$x_1+x_{12}=2,\qquad x_2+x_{12}=1,\qquad x_1,x_2,x_{12}\ge 0.$

The two solutions are

$ (x_1,x_2,x_{12})=(2,1,0)\quad\text{and}\quad (1,0,1), $

corresponding to \(2\cdot 2\cdot 3\) and \(2\cdot 6\). Hence \(F(2,1)=2\). Every integer with exponent multiset \(\{2,1\}\) has the same squarefree-factor count.

Step 4: Enumerate Only Feasible Exponent Signatures

To sum over all \(n\le N\), the program does not iterate over integers. Instead it enumerates exponent signatures \(\sigma=(e_1,\dots,e_r)\) in nonincreasing order

$e_1\ge e_2\ge \dots\ge e_r\ge 1.$

For such a signature, the smallest integer realizing it is obtained by pairing the largest exponent with the smallest prime:

$m_{\min}(\sigma)=2^{e_1}3^{e_2}5^{e_3}\cdots p_r^{e_r}.$

If \(m_{\min}(\sigma)>N\), then no integer up to \(N\) can have that signature. If \(m_{\min}(\sigma)\le N\), then the signature is feasible. This is exactly why generate_signatures_dfs grows signatures along the seed primes \(2,3,5,\dots\) while forcing exponents to stay nonincreasing.

Step 5: Count Integers for One Ordered Exponent Tuple

A signature is an unordered multiset of exponents, but actual integers assign those exponents to increasing primes. For one ordered tuple \(a=(a_1,\dots,a_r)\), define

$C(a,N)=\left|\left\{(q_1,\dots,q_r): q_1\lt q_2\lt \dots\lt q_r,\ \prod_{i=1}^{r} q_i^{a_i}\le N\right\}\right|.$

The recursion in OrderedPrimeTupleCounter chooses the primes left to right. If

$T_k=a_k+a_{k+1}+\dots+a_r$

is the remaining exponent sum at depth \(k\), then the current prime must satisfy

$q_k\le \left\lfloor R^{1/T_k}\right\rfloor,$

where \(R\) is the remaining limit after previous prime choices. This bound is sharp because every later prime is at least \(q_k\). On the last position there is no deeper recursion; the number of valid choices is obtained directly from the prime-counting function:

$\pi\!\left(\left\lfloor R^{1/a_r}\right\rfloor\right)-\text{startIndex}.$

If some exponents repeat, the same ordered tuple would arise many times, so the code generates only unique permutations of the signature.

Step 6: A Concrete Family Below 100

The signature \((2,1)\) illustrates the split between \(F(\sigma)\) and \(C(a,N)\). We already know \(F(2,1)=2\). For \(N=100\), the ordered tuple \((2,1)\) counts integers of the form \(p^2q\) with \(p\lt q\), while \((1,2)\) counts integers of the form \(pq^2\).

For \((2,1)\): \(2^2q\le 100\) gives 8 possibilities for \(q\), and \(3^2q\le 100\) gives 3 more, so

$C((2,1),100)=11.$

For \((1,2)\): \(2q^2\le 100\) gives 3 possibilities and \(3q^2\le 100\) gives 1 more, so

$C((1,2),100)=4.$

Therefore this entire signature family contributes

$F(2,1)\bigl(C((2,1),100)+C((1,2),100)\bigr)=2(11+4)=30$

to \(S(100)\). This is exactly the logic used for every signature.

Step 7: Prime Counting and the Final Sum

The last remaining ingredient is a fast \(\pi(x)\). The implementation builds a sieve up to \(\sqrt{N}\), stores the prime list and the small values of \(\pi(x)\), and for larger arguments uses a Lehmer-style prime counter with cached

$\phi(x,s)=\left|\left\{1\le m\le x:\ p_1,\dots,p_s\nmid m\right\}\right|.$

This makes the many root-bound queries inside the tuple recursion fast enough. If \(\Sigma(N)\) is the set of feasible signatures and \(\mathcal{U}(\sigma)\) is the set of unique permutations of \(\sigma\), then the program computes

$\boxed{S(N)=\sum_{\sigma\in\Sigma(N)} F(\sigma)\sum_{a\in\mathcal{U}(\sigma)} C(a,N).}$

How the Code Works

The C++ file contains the full optimized solver. PrimeTable builds the sieve and small \(\pi(x)\) table, PrimeCounter provides the Lehmer-style prime-counting routine, fsf_from_signature counts squarefree factorizations for one signature, generate_signatures enumerates feasible exponent patterns, generate_unique_permutations expands repeated exponents into distinct orderings, and OrderedPrimeTupleCounter::count_for_exponents counts the prime tuples for one ordered exponent vector.

The Java solution mirrors the same mathematics and almost the same function decomposition in a single-threaded implementation. The Python file is intentionally thin: it recompiles and runs the C++ source when necessary, then parses the final numeric output. In other words, the mathematical source of truth is the shared C++/Java algorithm, while Python is just a bridge.

The C++ program also validates the logic with internal checkpoints: it verifies the known value \(S(100)=193\), compares fast and brute-force computations on a small limit, and checks that single-threaded and multi-threaded runs agree.

Complexity Analysis

The sieve and small prime table up to \(\sqrt{N}\) cost \(O(\sqrt{N}\log\log \sqrt{N})\) time and \(O(\sqrt{N})\) memory. For \(N=10^{10}\), that preprocessing size is only \(10^5\).

The rest of the runtime is dominated by the signature tasks. There is no simple single closed form, because the DFS state counts depend on the exponent pattern and on the distribution of root-bound prime queries. However, the key compression is dramatic: the algorithm works on signatures, permutations, and memoized prime-tuple states rather than on all integers up to \(N\).

In this problem, the number of distinct prime factors is automatically small: the product of the first ten primes is \(6469693230\), while including the eleventh prime already exceeds \(10^{10}\). Hence every signature has length at most 10, which keeps the subset DFS, the permutation generation, and the tuple recursion practical. Memory is dominated by the memo tables for the factorization DFS and the prime-counting cache.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=362
2. Squarefree integers: Wikipedia — Square-free integer
3. Prime-counting function: Wikipedia — Prime-counting function
4. Meissel-Lehmer prime counting: Wikipedia — Meissel-Lehmer algorithm