Problem 333: Special Partitions

Mathematical Foundation

Definition. Let $T = \{2^a \cdot 3^b : a \ge 0,\; b \ge 0\} = \{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, \ldots\}$ be the set of all 3-smooth powers.

Lemma 1 (Finiteness of $T$ below $N$). The number of elements of $T$ not exceeding $N$ is $|T \cap [1, N]| = O(\log^2 N)$.

Proof. Each element $2^a \cdot 3^b \le N$ requires $a \le \log_2 N$ and $b \le \log_3 N$. The number of valid pairs $(a,b)$ is at most $(\lfloor \log_2 N \rfloor + 1)(\lfloor \log_3 N \rfloor + 1) = O(\log^2 N)$. $\square$

For $N = 10^6$: $\log_2(10^6) \approx 19.93$ and $\log_3(10^6) \approx 12.58$, giving at most $20 \times 13 = 260$ terms.

Theorem 1 (0-1 Knapsack Reduction). The number of ways to write $n$ as a sum of distinct elements of $T \cap [1, N]$ equals the coefficient of $x^n$ in the product

Proof. Expanding the product, each monomial $x^{t_{i_1} + t_{i_2} + \cdots + t_{i_k}}$ corresponds to choosing a distinct subset $\{t_{i_1}, \ldots, t_{i_k}\} \subseteq T$. The coefficient of $x^n$ counts the number of such subsets summing to $n$. $\square$

Lemma 2 (DP Correctness). Processing items in any order and updating in reverse (standard 0-1 knapsack), the array $\mathrm{dp}[s]$ correctly counts the number of representations of $s$ as a sum of distinct elements of $T$.

Proof. By induction on the number of items processed. After processing item $t_k$, for each sum $s$, $\mathrm{dp}[s]$ equals the number of subsets of $\{t_1, \ldots, t_k\}$ summing to $s$. The reverse-order update ensures each item is used at most once, since when computing $\mathrm{dp}[s + t_k]$, the value $\mathrm{dp}[s]$ has not yet been modified in the current pass. $\square$

Theorem 2 (Characterization of Special Primes). A prime $p < 10^6$ is special if and only if $\mathrm{dp}[p] = 1$ after the full knapsack computation. The answer is $\sum_{p \text{ special}} p$.

Proof. By definition, $p$ is special if and only if it admits exactly one partition into distinct 3-smooth powers, which is precisely $\mathrm{dp}[p] = 1$. $\square$

Editorial

Approach: 1. Generate all numbers 2^a * 3^b < 10^6. 2. 0-1 knapsack DP to count representations (capped at 2). 3. Sieve primes, sum those with exactly 1 representation. We generate 3-smooth powers up to N. We then 0-1 knapsack DP (count representations, cap at 2). Finally, iterate over t in T.

Pseudocode

Generate 3-smooth powers up to N
0-1 knapsack DP (count representations, cap at 2)
for t in T
for s from N-1 down to t
Sieve primes up to N
Sum special primes
for p from 2 to N-1

Complexity Analysis

• Time: Generating $T$ takes $O(\log^2 N)$. The knapsack DP runs in $O(|T| \cdot N) = O(N \log^2 N)$. The prime sieve takes $O(N \log \log N)$. Total: $O(N \log^2 N)$.
• Space: $O(N)$ for the DP array and the prime sieve.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 333: Special Partitions
 *
 * Find the sum of all primes < 10^6 that can be written in exactly one way
 * as a sum of distinct terms of the form 2^a * 3^b.
 *
 * Approach:
 * 1. Generate all numbers 2^a * 3^b < 10^6.
 * 2. 0-1 knapsack DP to count representations (capped at 2).
 * 3. Sieve primes, sum those with exactly 1 representation.
 *
 * Answer: 3053105
 */

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    const int LIMIT = 1000000;

    // Generate all 2^a * 3^b < LIMIT
    vector<int> terms;
    for (long long b3 = 1; b3 < LIMIT; b3 *= 3) {
        for (long long val = b3; val < LIMIT; val *= 2) {
            terms.push_back((int)val);
        }
    }
    sort(terms.begin(), terms.end());

    cout << "Number of terms: " << terms.size() << endl;

    // 0-1 knapsack: count representations, cap at 2
    // dp[s] = number of ways to represent s (capped at 2)
    vector<unsigned char> dp(LIMIT, 0);
    dp[0] = 1;

    for (int t : terms) {
        // Process in reverse for 0-1 knapsack
        for (int s = LIMIT - 1 - t; s >= 0; s--) {
            if (dp[s] > 0 && dp[s + t] < 2) {
                dp[s + t] = min(2, (int)dp[s + t] + (int)dp[s]);
            }
        }
    }

    // Sieve of Eratosthenes
    vector<bool> is_prime(LIMIT, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < LIMIT; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < LIMIT; j += i)
                is_prime[j] = false;
        }
    }

    // Sum primes with exactly 1 representation
    long long answer = 0;
    int count = 0;
    for (int p = 2; p < LIMIT; p++) {
        if (is_prime[p] && dp[p] == 1) {
            answer += p;
            count++;
        }
    }

    cout << "Number of special primes: " << count << endl;
    cout << "Answer: " << answer << endl;

    return 0;
}

"""
Problem 333: Special Partitions

Find the sum of all primes < 10^6 that can be written in exactly one way
as a sum of distinct terms of the form 2^a * 3^b.

Approach:
1. Generate all numbers 2^a * 3^b < 10^6.
2. 0-1 knapsack DP to count representations (capped at 2).
3. Sieve primes, sum those with exactly 1 representation.

Answer: 3053105
"""

def sieve_of_eratosthenes(limit):
    """Return a boolean array where is_prime[i] indicates if i is prime."""
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit, i):
                is_prime[j] = False
    return is_prime

def solve():
    LIMIT = 1_000_000

    # Generate all 2^a * 3^b < LIMIT
    terms = []
    b3 = 1
    while b3 < LIMIT:
        val = b3
        while val < LIMIT:
            terms.append(val)
            val *= 2
        b3 *= 3
    terms.sort()
    print(f"Number of terms: {len(terms)}")

    # 0-1 knapsack: count representations (cap at 2)
    dp = bytearray(LIMIT)  # dp[s] = number of ways, capped at 2
    dp[0] = 1

    for t in terms:
        for s in range(LIMIT - 1 - t, -1, -1):
            if dp[s] > 0 and dp[s + t] < 2:
                dp[s + t] = min(2, dp[s + t] + dp[s])

    # Sieve for primes
    is_prime = sieve_of_eratosthenes(LIMIT)

    # Sum primes with exactly 1 representation
    answer = 0
    count = 0
    for p in range(2, LIMIT):
        if is_prime[p] and dp[p] == 1:
            answer += p
            count += 1

    print(f"Number of special primes: {count}")
    print(f"Answer: {answer}")
    return answer

if __name__ == "__main__":
    solve()