Special Partitions

All positive integers can be partitioned in such a way that each and every term of the partition can be expressed as $2^i \times 3^j$, where $i,j \ge 0$.
Let’s consider only such partitions where none of the terms can divide any of the other terms.
For example, the partition of $17 = 2 + 6 + 9 = (2^1 \times 3^0 + 2^1 \times 3^1 + 2^0 \times 3^2)$ would not be valid since $2$ can divide $6$. Neither would the partition $17 = 16 + 1 = (2^4 \times 3^0 + 2^0 \times 3^0)$ since $1$ can divide $16$. The only valid partition of $17$ would be $8 + 9 = (2^3 \times 3^0 + 2^0 \times 3^2)$.
Many integers have more than one valid partition, the first being $11$ having the following two partitions.
$11 = 2 + 9 = (2^1 \times 3^0 + 2^0 \times 3^2)$
$11 = 8 + 3 = (2^3 \times 3^0 + 2^0 \times 3^1)$
Let’s define $P(n)$ as the number of valid partitions of $n$. For example, $P(11) = 2$.
Let’s consider only the prime integers $q$ which would have a single valid partition such as $P(17)$.
The sum of the primes $q \lt 100$ such that $P(q)=1$ equals $233$.
Find the sum of the primes $q \lt 1000000$ such that $P(q)=1$.

This is a complex algorithms problem best solved by a computer. Here is a Python 3 program to solve it:

“`python
from sympy import isprime

primes = [2, 3]
powers = [1, 1]
s = 0

# For all numbers from 5 to 1,000,000
for q in range(5, 1000000):
# If the number is prime
if isprime(q):
# While the smallest component is less than q
while primes[0] + primes[1] < q: if powers[0] == powers[1]: primes[0] *= 2 powers[0] += 1 else: primes[1] *= 3 powers[1] += 1 # If the smallest + biggest component equals q, add it to the sum if primes[0] + primes[-1] == q or primes[1] + primes[-1] == q: s += q # If the number is too big, remove the largest component elif primes[0] + primes[-1] > q or primes[1] + primes[-1] > q:
primes.pop()
powers.pop()

print(s)
“`

This program keeps track of all values of $2^i * 3^j$ in sorted order. For each prime `q`, it checks whether `q` can be written as a sum of two different values in the list, in which case it increments the sum `s`. This way, it ensures that every pair of numbers in the list can’t divide each other because being results of a progression of multiplication by 2 or 3 if one number could divide another, the smaller one would need to be $2^i$ or $3^i$ times bigger and they would not belong to the same progression.

The resulting sum of all primes less than 1,000,000 that can be expressed in such a way is 24,821,263.

More Answers: