Problem 333: Special Partitions

Project Euler Problem 333 Solution

EulerSolve provides an optimized solution for Project Euler Problem 333, Special Partitions, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

Call a positive integer admissible when it has the form $2^i3^j$ with $i,j\ge0$. A partition of $n$ into admissible parts is valid only when no part divides another. For $n=17$ the splitting $2+6+9$ is rejected because $2$ divides $6$, and $16+1$ because $1$ divides $16$; only $8+9$ survives. Writing $P(n)$ for the number of valid partitions of $n$, the statement gives $P(17)=1$ and $P(11)=2$, from $11=2+9$ and $11=8+3$, noting that $11$ is the first integer with two. We must add up the primes $q\lt10^6$ with $P(q)=1$; as a checkpoint, the primes $q\lt100$ with $P(q)=1$ sum to $233$. ^[1]

The whole solution in one sentence: one admissible part divides another exactly when both of its exponents are at most the other's, so a valid partition is a staircase in which the power of two climbs while the power of three falls, and one sweep over all staircases with total below a million fills a table of $P(n)$, from which a prime sieve picks the primes whose entry is $1$.

Mathematical Approach

1. The parts we are allowed to use

The admissible numbers are the 3-smooth numbers, the integers with no prime factor beyond $3$. ^[5] Up to $50$ there are fifteen of them,

$$1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,$$

and below $10^6$ exactly $142$, so the search runs over $142$ building blocks instead of a million integers. Lay them out in rows indexed by the exponent of $2$, so that row $a$ is the increasing list

$$2^a,\;2^a\cdot3,\;2^a\cdot3^2,\;\ldots$$

of the admissible numbers below the limit divisible by $2^a$ but not by $2^{a+1}$. As $2^{19}=524288$ fits below $10^6$ and $2^{20}$ does not, there are $20$ rows. Their lengths are $13,12,12,11,11$, then $10,9,9,8,7$, then $7,6,6,5,4$, and finally $4,3,2,2,1$, adding up to $142$. Equivalently the parts below $x$ are the lattice points $(a,b)$ with $a,b\ge0$ and $a\log2+b\log3\le\log x$; their triangle has area $\tfrac12\log_2x\cdot\log_3x$, here $125$, which is the leading term of the count, ^[7] the boundary rows and columns supplying the remaining $17$.

2. When does one part divide another

If one admissible number divides another, say $y=x\cdot m$, then comparing the exponents of $2$ and of $3$ in the unique prime factorisations ^[3] of the two sides gives the criterion

$$2^{a_1}3^{b_1}\mid2^{a_2}3^{b_2}\iff a_1\le a_2,\ b_1\le b_2.$$

The right-hand side is the product order on exponent pairs: one pair lies below another when it does so in both coordinates. ^[4] A set of pairwise incomparable elements is an antichain, so a valid partition is a finite antichain of exponent pairs whose parts add up to $n$. Two consequences come for free: the parts are distinct, since a repeated part would divide itself, and at most one part comes from each row, since two parts of one row share the exponent $a$, which makes their exponents of $3$ comparable.

3. Valid partitions are staircases

List the parts of a valid partition in order of increasing $a$, say $2^{a_1}3^{b_1},\ldots,2^{a_k}3^{b_k}$. For $s\lt t$ we have $a_s\lt a_t$, so the criterion of Section 2 forbids $b_s\le b_t$; therefore

$$a_1\lt a_2\lt\cdots\lt a_k,\qquad b_1\gt b_2\gt\cdots\gt b_k.$$

Conversely such a set is an antichain, since any two of its pairs disagree in direction. The conditions are equivalent: a valid partition is a staircase of exponent pairs, descending in one coordinate while it rises in the other.

Nine sets of distinct admissible numbers add up to $17$; the staircase rule kills eight:

$1+2+6+8$, $1+3+4+9$, $1+4+12$ and $1+16$ contain $1=2^03^0$, which divides everything;
$2+3+4+8$ has $2\mid4$, $2+3+12$ has $2\mid12$, $2+6+9$ has $2\mid6$ (the statement's own example) and $3+6+8$ has $3\mid6$;
$8+9=2^33^0+2^03^2$ has the pairs $(0,2)$ and $(3,0)$: the exponent of $2$ rises from $0$ to $3$ while that of $3$ falls from $2$ to $0$.

Exactly one staircase survives, so $P(17)=1$.

4. A worked example with three partitions

The smallest integer with three valid partitions is $49$, and all three are easy to check by hand:

$49=27+18+4$, pairs $(0,3),(1,2),(2,0)$;
$49=27+6+16$, pairs $(0,3),(1,1),(4,0)$;
$49=9+24+16$, pairs $(0,2),(3,1),(4,0)$.

In each line the first coordinates increase while the second decrease, and no other staircase adds up to $49$. Likewise $23=9+6+8$ has the pairs $(0,2),(1,1),(3,0)$ and no other valid partition, so $23$ is one of the ten primes behind the checkpoint $233$.

5. How long can a staircase be

The $a_t$ are distinct non-negative integers in increasing order, so $a_t\ge t-1$; the $b_t$ are distinct non-negative integers in decreasing order, so $b_t\ge k-t$. A staircase with $k$ parts therefore has

$$\sum_{t=1}^{k}2^{a_t}3^{b_t}\ge\sum_{t=1}^{k}2^{t-1}3^{k-t}=3^k-2^k,$$

the last step by telescoping, since each term equals $3^{k-t+1}2^{t-1}-3^{k-t}2^{t}$. Equality holds for $a_t=t-1$ and $b_t=k-t$, so $3^k-2^k$ is the exact minimum. For $k=12$ the bound is $3^{12}-2^{12}=527345$, below $10^6$, and for $k=13$ it is $1586131$, above it: no integer below $10^6$ has a valid partition with more than $12$ parts. The exponents are capped the same way, since $3^{12}=531441$ fits below the limit and $3^{13}$ does not.

6. Every integer has at least one valid partition

The statement opens by saying that every positive integer splits into admissible parts, which is immediate — take $n$ copies of $1$. That every integer has a valid partition is the first problem of the 2005 Putnam competition, whose own example is $23=9+8+6$. ^[2] It follows by induction on $m$ from a stronger claim: for every $B\ge0$ and every $m$ with $0\le m\lt3^B$ there is a valid partition of $m$ whose exponents of $3$ all lie below $B$, the empty one serving for $m=0$.

If $m$ is even, double every part of such a partition of $m/2$: that raises each exponent of $2$ by one and leaves those of $3$ alone, so the staircase survives. If $m$ is odd, let $3^b$ be the largest power of $3$ with $3^b\le m$. Then $b\lt B$, and maximality of $b$ gives

$$m'=\frac{m-3^b}{2}\lt\frac{3^{b+1}-3^b}{2}=3^b,$$

an integer because $m$ and $3^b$ are both odd. Doubling the parts of a partition of $m'$ with exponents of $3$ below $b$ and adding $3^b$ leaves the new part as the only odd one and the one with the largest exponent of $3$: a staircase again. Taking $B$ large enough gives $P(n)\ge1$ for every $n\ge1$. The construction is greedy — strip the factors of two, subtract the largest power of three, repeat — and at the top of the range it yields

$$999999=3^{12}+2\cdot3^{11}+2^3 3^8+2^4 3^7+2^5 3^6+2^7 3^3,$$

in ordinary integers

$$\begin{aligned}999999&=531441+354294+52488\\&\quad+34992+23328+3456.\end{aligned}$$

7. Even numbers, and why the prime $2$ counts

Only parts with $a=0$ are odd, and they are powers of $3$, so by Section 2 a valid partition has at most one odd part. An even $n$ can have none, since one odd part would make the total odd. Halving every part is then a bijection between the valid partitions of $2m$ and those of $m$, whence

$$P(2m)=P(m)\qquad(m\ge1),$$

so $P(n)$ depends only on the odd part of $n$. In particular $P(2)=P(1)=1$, and the even prime does belong to the sum we are asked for. The identity is a useful check on any implementation: it holds for every $m\le499999$ in the computed table.

8. Sweeping over all staircases

Sections 3 and 5 turn the counting into a small depth-first search over the $20$ rows. Write $R_i$ for row $i$, its columns numbered from $0$. The state is a triple $(i,j_{\max},s)$: rows $0,\ldots,i-1$ are decided, the parts chosen so far add up to $s$, and every column index still to be chosen must be smaller than $j_{\max}$. Two moves leave such a state:

skip row $i$ and continue with $(i+1,j_{\max},s)$;
take entry $j$ of row $i$, for any $j\lt\min(j_{\max},|R_i|)$ with $s+2^i3^j\le10^6-1$, and continue with $(i+1,j,s+2^i3^j)$.

The second move lowers the bound to $j$, the strict decrease of the exponents of $3$, while advancing to row $i+1$ enforces the strict increase of those of $2$. At row $20$ the selection is complete, and if $s\gt0$ the counter of $s$ rises by one.

Every valid partition of every $n\le10^6-1$ is reached exactly once. Given one, Section 2 puts at most one part in each row and Section 3 makes the chosen column indices fall as the row index grows; that is one path of the search, and no other path picks the same parts. All parts are positive, so no partial sum on that path exceeds $n$ and the sum test cannot prune it. Conversely the parts along a completed path have strictly increasing $a$ and strictly decreasing $b$, so by Section 3 they form a valid partition of $s$. The search therefore computes $P(n)$ exactly, and as each row is stored in increasing order the loop over $j$ may stop at the first entry with $s+2^i3^j$ above the limit — the standard pruning of a backtracking search. ^[9]

A trace makes this concrete. Lower the limit to $17$, leaving the five rows $[1,3,9]$, $[2,6]$, $[4,12]$, $[8]$, $[16]$. From $(0,1000,0)$ take column $2$ of row $0$, the part $9$, reaching $(1,2,9)$; skip rows $1$ and $2$; take column $0$ of row $3$, the part $8$, reaching $(4,0,17)$. Nothing further fits, as the next column index would have to be below $0$; skipping row $4$ ends in $(5,0,17)$ and raises the counter of $17$ once — the partition $8+9$ of Section 3.

9. From the table to the requested sum

What remains is a sieve of Eratosthenes up to $10^6$ ^[8] and one pass adding the primes $q$ with $P(q)=1$. The condition is severe: only $3129$ of the $999999$ integers below $10^6$ have $P(n)=1$, and only $42$ of the $78498$ primes below $10^6$ qualify. Partial sums make good checkpoints — $233$ for $q\lt100$ as in the statement, $4600$ for $q\lt1000$, $24853$ for $q\lt10^4$ — and the first is built into the program.

How the Code Works

The C++ program ^[10] takes --prime-limit=, digits only and at least $3$, and --skip-checkpoints in parse_arguments. build_terms builds Section 1: for each power of two p2 it appends p2, 3*p2, 9*p2, … and leaves the row once the value exceeds limit/3, so the next multiplication cannot pass the limit.

partition_counts allocates one 32-bit counter per integer up to the limit and runs the search of Section 8 as a recursive lambda dfs(i, j_limit, sum): the skipping call first, then a loop over j up to upper = min(j_limit, rows[i].size()) that breaks at the first part pushing sum above the limit. The initial j_limit is $1000$, far above the longest row's $13$ entries, so the first part may come from any column; by Section 5 none above $12$ is reachable. A completed selection with sum > 0 increments count[sum], which leaves out the empty one.

solve(prime_limit) passes limit = prime_limit - 1, so only integers strictly below the bound are tabulated, sieves by crossing out from $p\cdot p$ while $p\cdot p$ stays below prime_limit, and adds up the primes with counts[q] == 1. Unless --skip-checkpoints is given, run_checkpoints first checks the statement's data: solve(100) must return $233$, and in partition_counts(100) the entries for $11$ and $17$ must be $2$ and $1$.

The Python version packs the algorithm into one solve(): rows built inline, dfs a closure with the same parameters, a bytearray sieve cleared by the slice assignment is_prime[p*p::p], the total returned as a string. Its sys.setrecursionlimit(100000) is generous: the $20$ row decisions and the terminal call need at most $21$ nested frames. The Java port passes the shared state explicitly — dfs is a static method taking rows, count and limit, where C++ uses a lambda and Python a closure — and sievePrimeFlags returns a boolean[]. Both ports fix the bound at $10^6$, take no options and run no checkpoints.

The integer types are sufficient at the fixed bound. No counter exceeds $196$, the largest $P(n)$ below $10^6$, so 32-bit counters suffice, and the requested sum stays below $42\cdot10^6$, yet C++ accumulates it in u64, Java in long, Python in unbounded integers. The $64$-bit loop variables of build_terms and buildTerms let p2 double past the limit and end the loop cleanly, which an int would not for limits near $2^{31}$ — though parse_int_after_prefix adds digits without a range check, so such a limit cannot safely be asked for anyway.

Complexity and Verification

Let $T$ count the completed selections for a sum limit $L$ — the staircases with total at most $L$, the empty one included — so that $T=1+\sum_{n\le L}P(n)$. Skipping all remaining rows sends every recursive call to one completed selection, and each selection receives at most the $21$ nodes of its own path, so the calls number between $T$ and $21T$: at the full limit $183872640$ against $T=40549126$, a factor of $4.5$. A call does constant work beyond its children and the single failed sum test that breaks its loop, so the search takes at most $21T=O(T\log L)$ steps, and the sieve adds $O(L\log\log L)$. ^[8] Why $T$ is so small: in the box of $20$ exponents of $2$ and $13$ of $3$, a staircase with $k$ parts is fixed by its set of first and its set of second coordinates, the pairing being forced, so the box holds

$$\sum_{k\ge0}\binom{20}{k}\binom{13}{k}=\binom{33}{13}=573166440$$

staircases by Vandermonde's identity, ^[6] and the bound on the total keeps $7\%$ of them. Most have middling length: $12303612$ have seven parts, only $2169$ the maximum of $12$. Still $T$ grows faster than $L$: the non-empty selections number $144$, $2679$, $60428$, $1512608$ and $40549125$ at $L=10^d-1$ for $d=2,\ldots,6$, a factor per decade rising from $19$ to $27$ — measurements over that range, not an asymptotic law. Memory is linear in $L$: the C++ arrays hold $4$ MB of 32-bit counters and $1$ MB of byte flags, Java the same counters in an int[] beside a boolean[] whose layout the runtime chooses, Python a list of a million references, about $8$ MB on a 64-bit build, beside its $1$ MB bytearray. On one desktop machine the C++ search takes about $0.3$ seconds and the identical Python recursion about $20$; the $183.9$ million calls dominate both.

Independent checks back these numbers. Enumerating every subset of the admissible parts at most $n$ — the singleton $\{n\}$ matters when $n$ is itself admissible — keeping those of sum $n$ and testing each pair for divisibility reproduces $P(n)$ for $1\le n\le400$ without the staircase criterion; that validates Section 3. A second method agrees for $1\le n\le20000$. Let $N(m,B)$ count the valid partitions of $m$ whose exponents of $3$ lie below $B$, so $N(0,B)=1$ and $N(m,0)=0$ for $m\ge1$. Section 7 gives $N(2m,B)=N(m,B)$; for odd $m$ the unique odd part is some $3^b$, every other part having a smaller exponent of $3$, so removing it and halving the rest gives

$$N(m,B)=\sum_{b\lt B,\;3^b\le m}N\left(\tfrac{m-3^b}{2},b\right),$$

with $P(n)=N(n,B)$ once $3^B\gt n$. The table agrees with all $100$ published terms of $P(n)$ and with the published first integers attaining each value, $1,11,49,103,179,313,\ldots$ ^[6] The greedy construction of Section 6 gave a genuine valid partition for every $n\le200000$, and the minimum $3^k-2^k$ was confirmed by exhaustive search over exponent windows up to $k=14$. The C++ checkpoints $233$, $P(11)=2$ and $P(17)=1$ hold, and at the full limit this independent table reproduces the official answer.

Footnotes and References

The references below supply the background facts used above. The divisibility criterion, the staircase characterisation, the bound $3^k-2^k$, the identity $P(2m)=P(m)$ and the proof that the search counts every partition once are derived explicitly here; the state and length counts are measured by instrumenting the search.

Project Euler 333 — Special Partitions. The statement admits only parts 2^i × 3^j, calls a partition valid when no term divides another, rejects 2 + 6 + 9 and 16 + 1 for 17 while accepting 8 + 9, gives both valid partitions of 11, defines P(n) as their number and asks for the sum of the primes below one million with P(q) = 1; over q < 100 that sum is 233.
66th William Lowell Putnam Mathematical Competition (2005), Problem A1, in K. S. Kedlaya's Putnam archive. It asks for a proof that every positive integer is a sum of numbers 2^r 3^s with no summand dividing another, with 23 = 9 + 8 + 6 as its example.
Wikipedia — Fundamental theorem of arithmetic states that every integer above one is a product of primes in exactly one way up to order, and gives the greatest common divisor through the minimum of corresponding exponents; comparing exponents there yields the criterion of Section 2.
Wikipedia — Product order defines the componentwise order, in which one pair precedes another only when it does so in both coordinates. Wikipedia — Antichain defines an antichain as a subset whose distinct elements are pairwise incomparable — what a valid partition is.
OEIS A003586 lists the 3-smooth numbers, "numbers of the form 2^i*3^j with i, j >= 0", beginning 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, and counts its terms up to n by the single sum over i from 0 to floor(log_2(n)) of floor(log_3(n/2^i) + 1), the row-by-row count of Section 1.
OEIS A355915 is the P(n) of this problem, the number of ways to write n as a sum of numbers 2^r 3^s with r, s >= 0 and no summand dividing another; its 100 published terms begin 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, and 11 is noted as the first with two. OEIS A356792 gives the smallest integer with exactly n of them, 1, 11, 49, 103, 179, 313, … . Wikipedia — Vandermonde's identity states that C(m + n, r) is the sum over k of C(m, k) C(n, r − k); with r = n it counts the staircases in the exponent box.
Wikipedia — Smooth number defines a B-smooth number as one whose prime factors are at most B and gives, for small fixed B, the estimate Ψ(x, B) ≈ (1/π(B)!) ∏ log x / log p over the primes p ≤ B, which for B = 3 is the triangle area of Section 1.
Wikipedia — Sieve of Eratosthenes crosses out the multiples of each prime p from p² on, stops once p² exceeds n and states the cost as O(n log log n) — the loop bounds and the sieve cost of all three programs.
Wikipedia — Backtracking describes a depth-first search that abandons a partial candidate as soon as it cannot be completed, skipping the whole subtree below a hopeless node; the break of Section 8 is that pruning.
C++ — Euler333.cpp. The linked immutable revision contains build_terms, partition_counts with its recursive dfs, solve and run_checkpoints, and accepts --prime-limit= and --skip-checkpoints. It is the implementation record for this article.

Problem 333 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int prime_limit = 1000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--prime-limit=", options.prime_limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.prime_limit >= 3;
}

std::vector<std::vector<int>> build_terms(const int limit) {
    std::vector<std::vector<int>> rows;
    for (u64 p2 = 1ULL; p2 <= static_cast<u64>(limit); p2 <<= 1ULL) {
        std::vector<int> row;
        for (u64 value = p2; value <= static_cast<u64>(limit); value *= 3ULL) {
            row.push_back(static_cast<int>(value));
            if (value > static_cast<u64>(limit) / 3ULL) {
                break;
            }
        }
        rows.push_back(std::move(row));
    }
    return rows;
}

std::vector<std::uint32_t> partition_counts(const int limit) {
    const std::vector<std::vector<int>> rows = build_terms(limit);
    std::vector<std::uint32_t> count(static_cast<std::size_t>(limit + 1), 0U);

    const auto dfs = [&](auto&& self, const int i, const int j_limit, const int sum) -> void {
        if (i == static_cast<int>(rows.size())) {
            if (sum > 0) {
                ++count[static_cast<std::size_t>(sum)];
            }
            return;
        }

        self(self, i + 1, j_limit, sum);  // Skip this 2^i layer.

        const int upper = std::min(j_limit, static_cast<int>(rows[static_cast<std::size_t>(i)].size()));
        for (int j = 0; j < upper; ++j) {
            const int value = rows[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)];
            if (sum + value > limit) {
                break;
            }
            self(self, i + 1, j, sum + value);
        }
    };
    dfs(dfs, 0, 1000, 0);
    return count;
}

u64 solve(const int prime_limit) {
    const int limit = prime_limit - 1;
    const std::vector<std::uint32_t> counts = partition_counts(limit);

    std::vector<std::uint8_t> is_prime(static_cast<std::size_t>(prime_limit), 1U);
    is_prime[0] = 0U;
    is_prime[1] = 0U;
    for (int p = 2; static_cast<long long>(p) * p < prime_limit; ++p) {
        if (is_prime[static_cast<std::size_t>(p)] == 0U) {
            continue;
        }
        for (int q = p * p; q < prime_limit; q += p) {
            is_prime[static_cast<std::size_t>(q)] = 0U;
        }
    }

    u64 sum = 0ULL;
    for (int q = 2; q < prime_limit; ++q) {
        if (is_prime[static_cast<std::size_t>(q)] != 0U &&
            counts[static_cast<std::size_t>(q)] == 1U) {
            sum += static_cast<u64>(q);
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (solve(100) != 233ULL) {
        std::cerr << "Checkpoint failed for stated sample q<100" << '\n';
        return false;
    }
    const auto counts = partition_counts(100);
    if (counts[11] != 2U || counts[17] != 1U) {
        std::cerr << "Checkpoint failed for P(11)=2 and P(17)=1 examples" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.prime_limit) << '\n';
    return 0;
}

Python

def solve():
    prime_limit = 1000000
    limit = prime_limit - 1

    # Build terms: rows of 2^a * 3^b values
    rows = []
    p2 = 1
    while p2 <= limit:
        row = []
        v = p2
        while v <= limit:
            row.append(v)
            if v > limit // 3:
                break
            v *= 3
        rows.append(row)
        p2 <<= 1

    # DFS partition counting
    count = [0] * (limit + 1)

    def dfs(i, j_limit, s):
        if i == len(rows):
            if s > 0:
                count[s] += 1
            return
        dfs(i + 1, j_limit, s)
        upper = min(j_limit, len(rows[i]))
        for j in range(upper):
            val = rows[i][j]
            if s + val > limit:
                break
            dfs(i + 1, j, s + val)

    import sys
    sys.setrecursionlimit(100000)
    dfs(0, 1000, 0)

    # Sieve primes
    is_prime = bytearray(b'\x01' * prime_limit)
    is_prime[0] = 0
    is_prime[1] = 0
    p = 2
    while p * p < prime_limit:
        if is_prime[p]:
            is_prime[p*p::p] = bytearray(len(is_prime[p*p::p]))
        p += 1

    total = 0
    for q in range(2, prime_limit):
        if is_prime[q] and count[q] == 1:
            total += q

    return str(total)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler333 {

    static boolean[] sievePrimeFlags(int limit) {
        boolean[] isPrime = new boolean[limit];
        Arrays.fill(isPrime, true);
        if (limit > 0)
            isPrime[0] = false;
        if (limit > 1)
            isPrime[1] = false;
        for (int p = 2; p * p < limit; p++) {
            if (isPrime[p]) {
                for (int q = p * p; q < limit; q += p) {
                    isPrime[q] = false;
                }
            }
        }
        return isPrime;
    }

    static List<List<Integer>> buildTerms(int limit) {
        List<List<Integer>> rows = new ArrayList<>();
        for (long p2 = 1; p2 <= limit; p2 *= 2) {
            List<Integer> row = new ArrayList<>();
            for (long val = p2; val <= limit; val *= 3) {
                row.add((int) val);
                if (val > (limit / 3)) {
                    break;
                }
            }
            rows.add(row);
        }
        return rows;
    }

    static void dfs(int i, int j_limit, int sum, List<List<Integer>> rows, int[] count, int limit) {
        if (i == rows.size()) {
            if (sum > 0)
                count[sum]++;
            return;
        }

        dfs(i + 1, j_limit, sum, rows, count, limit);

        int upper = Math.min(j_limit, rows.get(i).size());
        for (int j = 0; j < upper; j++) {
            int val = rows.get(i).get(j);
            if (sum + val > limit)
                break;
            dfs(i + 1, j, sum + val, rows, count, limit);
        }
    }

    static int[] partitionCounts(int limit) {
        List<List<Integer>> rows = buildTerms(limit);
        int[] count = new int[limit + 1];
        dfs(0, 1000, 0, rows, count, limit);
        return count;
    }

    public static String solve() {
        int primeLimit = 1000000;
        int limit = primeLimit - 1;
        int[] counts = partitionCounts(limit);
        boolean[] isPrime = sievePrimeFlags(primeLimit);

        long sum = 0;
        for (int q = 2; q < primeLimit; q++) {
            if (isPrime[q] && counts[q] == 1) {
                sum += q;
            }
        }
        return String.valueOf(sum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}