Solution

Answer: 3053105

Let a term be represented by its exponent pair

$$(i,j)\quad\leftrightarrow\quad 2^i3^j.$$

A partition is valid iff no term divides another.

For two terms

$$2^a3^b,\qquad 2^c3^d,$$

we have

$$2^a3^b \mid 2^c3^d \iff a\le c \text{ and } b\le d.$$

Therefore a valid partition corresponds exactly to a set of exponent pairs where no pair is coordinatewise $\le$ another.

Equivalently:

if the $i$-exponents increase,
then the $j$-exponents must strictly decrease.

So every valid partition can be written as a chain

$$(i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)$$

with

$$i_1<i_2<\cdots<i_k,\qquad j_1>j_2>\cdots>j_k.$$

This converts the problem into a structured combinatorial search.

1. Mathematical Analysis

We need:

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

Bounds on exponents

Since $2^i3^j<10^6$,

$i\le 19$ because $2^{20}>10^6$,
$j\le 12$ because $3^{13}>10^6$.

So there are very few possible basic terms.

Dynamic programming idea

Process the powers of $3$ from large $j$ down to small $j$.

At each $j$, we may:

skip that $j$, or
choose exactly one $i$ larger than every previously chosen $i$.

This automatically enforces:

$$i_1<i_2<\cdots,\qquad j_1>j_2>\cdots,$$

hence validity.

We maintain states:

$$(\text{largest chosen } i,\ \text{sum})$$

and count how many ways each sum can occur.

Finally:

compute $P(n)$,
sieve primes,
sum all primes with $P(q)=1$.

2. Python Implementation

from collections import defaultdict

LIMIT = 10**6

# ------------------------------------------------------------
# Generate powers of 2 and 3
# ------------------------------------------------------------

pow2 = [1]
while pow2[-1] * 2 < LIMIT:
    pow2.append(pow2[-1] * 2)

pow3 = [1]
while pow3[-1] * 3 < LIMIT:
    pow3.append(pow3[-1] * 3)

I = len(pow2)
J = len(pow3)

# ------------------------------------------------------------
# DP states:
#
# states[k] is a dictionary:
#   sum -> number of valid partitions
#
# where the largest chosen i-exponent equals (k-1).
#
# k = 0 represents "no exponent chosen yet", i.e. last_i = -1.
# ------------------------------------------------------------

states = [defaultdict(int) for _ in range(I + 1)]
states[0][0] = 1

# Process j from large to small
for j in range(J - 1, -1, -1):

    new_states = [defaultdict(int) for _ in range(I + 1)]

    for idx, d in enumerate(states):

        last_i = idx - 1

        for current_sum, ways in d.items():

            # Option 1: skip this j
            new_states[idx][current_sum] += ways

            # Option 2: choose an i > last_i
            for new_i in range(last_i + 1, I):

                value = pow2[new_i] * pow3[j]
                new_sum = current_sum + value

                if new_sum < LIMIT:
                    new_states[new_i + 1][new_sum] += ways

    states = new_states

# ------------------------------------------------------------
# Collect P(n)
# ------------------------------------------------------------

P = [0] * LIMIT

for d in states:
    for s, cnt in d.items():
        P[s] += cnt

# Remove empty partition
P[0] -= 1

# ------------------------------------------------------------
# Prime sieve
# ------------------------------------------------------------

is_prime = bytearray(b"\x01") * LIMIT
is_prime[0:2] = b"\x00\x00"

for p in range(2, int(LIMIT**0.5) + 1):
    if is_prime[p]:
        is_prime[p*p:LIMIT:p] = b"\x00" * (
            ((LIMIT - 1 - p*p) // p) + 1
        )

# ------------------------------------------------------------
# Compute answer
# ------------------------------------------------------------

answer = sum(
    n for n in range(LIMIT)
    if is_prime[n] and P[n] == 1
)

print(answer)

3. Code Walkthrough

Generating powers

pow2 = [1]
while pow2[-1] * 2 < LIMIT:
    pow2.append(pow2[-1] * 2)

Creates all powers $2^i<10^6$.

Similarly for powers of $3$.

DP structure

states[k][s]

means:

we have formed sum $s$,
the largest used exponent $i$ equals $k-1$.

Processing $j$ in descending order guarantees future chosen $j$'s are smaller.

Choosing only $i > \text{last}_i$ guarantees increasing $i$'s.

Thus no divisibility can occur.

Transition

# skip this j
new_states[idx][current_sum] += ways

value = pow2[new_i] * pow3[j]
new_sum = current_sum + value

to include a term.

Building $P(n)$

After all $j$'s are processed:

P[s] += cnt

counts the number of valid partitions of $s$.

4. Verification on the small example

The problem states:

$$\sum_{\substack{q<100\ P(q)=1}} q = 233.$$

Running the program with LIMIT = 100 gives exactly:

confirming correctness.

5. Final Verification

The computation is consistent with:

the divisibility characterization,
strict monotonicity of exponents,
the sample value $233$,
and exhaustive counting under $10^6$.

The resulting sum is:

$$3053105.$$

Answer: 3053105

Project Euler Problem 333