Detailed mathematical approach

Problem Summary

We study partitions of an integer \(n\) into terms of the form \(2^a3^b\) with \(a,b \ge 0\), under the extra restriction that no chosen term may divide any other chosen term. If \(P(n)\) denotes the number of such valid partitions, the target is

$\sum_{\substack{q \lt 10^6 \\ q\text{ prime} \\ P(q)=1}} q.$

Mathematical Approach

Let \(L = 10^6 - 1\). The solution does not test all partitions of all integers up to \(L\). Instead, it converts the validity rule into a strict order constraint on the exponent pairs \((a,b)\).

Admissible Terms

Every allowed part has the form \(2^a3^b\). For each fixed exponent \(a\), define the row

$R_a = \{2^a3^b \le L : b \ge 0\}.$

The code stores these rows as rows[a][b], so row \(a\) is the increasing list

$2^a,\;2^a3,\;2^a3^2,\;\dots.$

This already compresses the search space into a small rectangular grid of exponent pairs instead of all integers below \(L\).

Divisibility Criterion

For two admissible terms \(x = 2^{a_1}3^{b_1}\) and \(y = 2^{a_2}3^{b_2}\), unique prime factorization gives

$x \mid y \iff a_1 \le a_2 \text{ and } b_1 \le b_2.$

So a valid partition is exactly a finite set of lattice points \((a,b)\) that forms an antichain in the product order on exponent pairs.

This has two immediate consequences:

First, a valid partition can contain at most one term from any fixed row \(a\), because inside one row the smaller \(b\)-index always divides the larger one.

Second, if rows are processed in increasing \(a\), then the chosen \(b\)-indices must be strictly decreasing. Indeed, if \(a_1 < a_2\) and \(b_1 \le b_2\), then \(2^{a_1}3^{b_1}\mid 2^{a_2}3^{b_2}\), which is forbidden.

DFS State and Invariant

After this reduction, the counting problem becomes a row-by-row depth-first search. The state

$\mathrm{DFS}(i, j_{\max}, s)$

means that rows \(0,1,\dots,i-1\) have already been processed, the current partial sum is \(s\), and every future chosen column index \(j\) must satisfy \(j < j_{\max}\). This invariant encodes the strict decrease of the \(3\)-exponents.

From a state \((i,j_{\max},s)\), the code has exactly two kinds of transitions:

Skip row \(i\):

$\mathrm{DFS}(i+1, j_{\max}, s).$

Choose the \(j\)-th term of row \(i\), where \(0 \le j < \min(j_{\max}, |R_i|)\) and \(s + 2^i3^j \le L\):

$\mathrm{DFS}(i+1, j, s + 2^i3^j).$

The parameter j_limit in the source is exactly this \(j_{\max}\).

Why This Counts Each Valid Partition Exactly Once

Every valid partition has a unique description when its terms are ordered by increasing \(a\). In each row we either take nothing or choose exactly one column index \(b\). Therefore each valid partition corresponds to one unique DFS path.

Conversely, every DFS leaf represents a set of terms with strictly decreasing \(b\)-indices, hence no term can divide another. Therefore the leaf update

$P(s) \leftarrow P(s) + 1$

records the exact number of valid partitions of \(s\), not an approximation.

Worked Examples: \(P(11)=2\) and \(P(17)=1\)

The code checkpoints match the examples from the statement. For 11, the two valid partitions are

$11 = 2 + 9 = 2^1 3^0 + 2^0 3^2,$

$11 = 8 + 3 = 2^3 3^0 + 2^0 3^1,$

so \(P(11)=2\).

For 17, the partition \(17 = 8 + 9\) is valid, but \(17 = 2 + 6 + 9\) is invalid because \(2 \mid 6\), and \(17 = 16 + 1\) is invalid because \(1 \mid 16\). Hence

$P(17)=1.$

Prime Filter and Final Sum

Once the array \(P(s)\) has been filled for all \(s \le L\), the rest is straightforward. A sieve of Eratosthenes marks the primes, and the code returns

$\sum_{\substack{q \lt 10^6 \\ q\text{ prime} \\ P(q)=1}} q.$

The published sample

$\sum_{\substack{q \lt 100 \\ q\text{ prime} \\ P(q)=1}} q = 233$

is used as a correctness checkpoint.

How the Code Works

build_terms(limit) constructs the rows \(R_a\). Then partition_counts(limit) runs the DFS described above and fills count[s] with the exact value \(P(s)\). Finally solve(prime_limit) computes a prime sieve and sums precisely those primes \(q\) for which count[q] == 1. The C++, Python, and Java implementations are the same algorithm in three syntaxes.

Complexity Analysis

The count array and prime sieve require \(O(L)\) memory. The recursion depth is \(O(\log_2 L)\), because there is one DFS level per power of 2. The row table itself is tiny, of size only \(O(\log L \cdot \log L)\).

The running time is output-sensitive: the DFS does not examine all subsets of all admissible terms, but only row-compatible selections with strictly decreasing \(b\)-indices, while also pruning any branch whose partial sum already exceeds \(L\). In practice, the cost is governed by the number of reachable valid states, which is far smaller than a naive subset search.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=333
2. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
3. Backtracking: Wikipedia — Backtracking
4. Antichains and partial orders: Wikipedia — Antichain