Project Euler

Find the 200th Prime-proof Sqube Containing "200"

A sqube is a number of the form p^2 q^3 or p^3 q^2 where p and q are distinct primes. A number is prime-proof if no single digit substitution (replacing exactly one digit with a different digit) pr...

Source sync Apr 19, 2026

Problem #0200

Level Level 09

Solved By 2,828

Languages C++, Python

Answer 229161792008

Length 398 words

number_theorymodular_arithmeticlinear_algebra

We shall define a sqube to be a number of the form, $p^2 q^3$, where $p$ and $q$ are distinct primes.

For example, $200 = 5^2 2^3$ or $120072949 = 23^2 61^3$.

The first five squbes are $72, 108, 200, 392$, and $500$.

Interestingly, $200$ is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "$200$" is $1992008$.

Find the $200$th prime-proof sqube containing the contiguous sub-string "$200$".

Problem 200: Find the 200th Prime-proof Sqube Containing “200”

Mathematical Foundation

Theorem 1. (Sqube Characterization.) A positive integer $n$ is a sqube if and only if $n = p^2 q^3$ for some pair of distinct primes $p, q$ . Note that $p^3 q^2 = q^2 p^3$ is also a sqube (with roles swapped), so every sqube has exactly the form $a^2 b^3$ for distinct primes $a, b$ .

Proof. By definition. The factorization $n = p^2 q^3$ determines $p$ and $q$ uniquely (up to the swap $p^2 q^3 \leftrightarrow q^3 p^2$ , which is the same number). The form $p^3 q^2$ is simply $q^2 p^3$ with $a = q, b = p$ . $\square$

Theorem 2. (Deterministic Primality via Miller-Rabin.) For $n < 3.2 \times 10^{14}$ , the Miller-Rabin test with witnesses $\{2, 3, 5, 7, 11, 13\}$ is deterministic (no pseudoprimes exist below this bound for this witness set).

Proof. This is a computational result. Jaeschke (1993) proved that the witnesses $\{2, 3, 5, 7, 11, 13\}$ suffice for $n < 3.2 \times 10^{14}$ . Since our squbes and their digit-substituted variants are below $10^{13}$ , this witness set provides a rigorous primality test. $\square$

Lemma 1. (Prime-Proof Condition.) A number $n$ with decimal digits $d_1 d_2 \cdots d_m$ is prime-proof if and only if for every position $i \in \{1, \ldots, m\}$ and every replacement digit $d' \in \{0, 1, \ldots, 9\} \setminus \{d_i\}$ (with $d' \neq 0$ when $i = 1$ ), the resulting number $n'$ is composite.

Proof. Direct from the definition: “replacing exactly one digit with a different digit” means choosing one position and one alternative digit. The leading-digit constraint $d' \neq 0$ when $i = 1$ ensures $n'$ has the same number of digits (no leading zeros). $\square$

Lemma 2. (Digit Substitution Count.) For a number with $m$ digits, the number of single-digit substitutions is at most $9m - 1$ (position 1 has 8 alternatives if $d_1 \neq 0$ , all other positions have 9 alternatives each; minus adjustments for the leading digit).

Proof. Position 1: $\{1, \ldots, 9\} \setminus \{d_1\}$ gives 8 choices. Positions $2, \ldots, m$ : $\{0, \ldots, 9\} \setminus \{d_i\}$ gives 9 choices each. Total: $8 + 9(m-1) = 9m - 1$ . $\square$

Editorial

A sqube is p^2q^3 or p^3q^2 for distinct primes p, q. Prime-proof means no single digit change produces a prime. We generate all squbes below B. We then note: p^3 * q^2 is generated as q^2 * p^3 with roles swapped. Finally, filter squbes containing “200”.

Pseudocode

Generate all squbes below B
Note: p^3 * q^2 is generated as q^2 * p^3 with roles swapped
Filter squbes containing "200"
Check prime-proof condition
for s in candidates
for i from 0 to m-1
for d from 0 to 9

Complexity Analysis

Time: Sqube generation: iterate over primes $q \leq B^{1/3}$ and for each, primes $p \leq \sqrt{B/q^3}$ . The number of squbes below $B$ is $O(B^{1/2}/\log B + B^{1/3}/\log B)$ by the prime counting function. Filtering for “200”: $O(S \log S)$ for sorting $S$ candidates. Prime-proof check: $O(m)$ substitutions per candidate, each requiring a Miller-Rabin test in $O(\log^2 n)$ . The dominant cost is the sorting and prime-proof checking.
Space: $O(S)$ to store all squbes containing “200”, where $S$ is their count.

Answer

\boxed{229161792008}

C++ project_euler/problem_200/solution.cpp

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

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

// Modular exponentiation for Miller-Rabin
ull mulmod(ull a, ull b, ull m) {
    return (__uint128_t)a * b % m;
}

ull powmod(ull a, ull b, ull m) {
    ull res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        b >>= 1;
    }
    return res;
}

bool miller_rabin(ull n, ull a) {
    if (n % a == 0) return n == a;
    ull d = n - 1;
    int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }
    ull x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(ull n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ull a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (!miller_rabin(n, a)) return false;
    }
    return true;
}

bool contains_200(ull n) {
    string s = to_string(n);
    return s.find("200") != string::npos;
}

bool is_prime_proof(ull n) {
    string s = to_string(n);
    int len = s.size();
    for (int i = 0; i < len; i++) {
        char orig = s[i];
        for (char d = '0'; d <= '9'; d++) {
            if (d == orig) continue;
            if (i == 0 && d == '0') continue; // no leading zero
            s[i] = d;
            ull val = stoull(s);
            if (is_prime(val)) {
                s[i] = orig;
                return false;
            }
        }
        s[i] = orig;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);

    // Generate squbes: p^2 * q^3 and p^3 * q^2 for distinct primes p, q
    // Need to find enough that contain "200" and are prime-proof
    // Answer is around 2.3e11, so search up to ~1e12

    const ull LIMIT = 1000000000000ULL; // 10^12

    // Sieve primes up to cbrt(LIMIT) ~ 10000 for q, and sqrt(LIMIT/8) for p
    // Actually we need primes up to sqrt(LIMIT) ~ 10^6
    int sieve_limit = 1000001;
    vector<bool> siv(sieve_limit, true);
    siv[0] = siv[1] = false;
    for (int i = 2; i * i < sieve_limit; i++)
        if (siv[i])
            for (int j = i * i; j < sieve_limit; j += i)
                siv[j] = false;

    vector<int> primes;
    for (int i = 2; i < sieve_limit; i++)
        if (siv[i]) primes.push_back(i);

    // Generate all squbes
    set<ull> sqube_set;

    // Form p^2 * q^3
    for (int i = 0; i < (int)primes.size(); i++) {
        ull p = primes[i];
        ull p2 = p * p;
        if (p2 > LIMIT / 8) break; // q >= 2, q^3 >= 8
        for (int j = 0; j < (int)primes.size(); j++) {
            if (i == j) continue;
            ull q = primes[j];
            ull q3 = q * q * q;
            if (q3 > LIMIT / p2) break;
            ull val = p2 * q3;
            if (val <= LIMIT && contains_200(val)) {
                sqube_set.insert(val);
            }
        }
    }

    // Form p^3 * q^2
    for (int i = 0; i < (int)primes.size(); i++) {
        ull p = primes[i];
        ull p3 = p * p * p;
        if (p3 > LIMIT / 4) break; // q >= 2, q^2 >= 4
        for (int j = 0; j < (int)primes.size(); j++) {
            if (i == j) continue;
            ull q = primes[j];
            ull q2 = q * q;
            if (q2 > LIMIT / p3) break;
            ull val = p3 * q2;
            if (val <= LIMIT && contains_200(val)) {
                sqube_set.insert(val);
            }
        }
    }

    vector<ull> candidates(sqube_set.begin(), sqube_set.end());
    sort(candidates.begin(), candidates.end());

    int count = 0;
    for (ull val : candidates) {
        if (is_prime_proof(val)) {
            count++;
            if (count == 200) {
                cout << val << endl;
                return 0;
            }
        }
    }

    cout << "Not found within limit" << endl;
    return 0;
}

Python project_euler/problem_200/solution.py

"""
Problem 200: Find the 200th Prime-proof Sqube Containing "200"

A sqube is p^2*q^3 or p^3*q^2 for distinct primes p, q.
Prime-proof means no single digit change produces a prime.
"""

def sieve_primes(limit):
    """Simple sieve of Eratosthenes."""
    is_prime = bytearray(b'\x01') * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = 0
    return [i for i in range(2, limit + 1) if is_prime[i]]

def is_prime_miller_rabin(n):
    """Deterministic Miller-Rabin for n < 3.3e24."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    # Small primes check
    for p in [5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n == p:
            return True
        if n % p == 0:
            return False

    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def contains_200(n):
    return "200" in str(n)

def is_prime_proof(n):
    s = list(str(n))
    length = len(s)
    for i in range(length):
        orig = s[i]
        for d in '0123456789':
            if d == orig:
                continue
            if i == 0 and d == '0':
                continue
            s[i] = d
            val = int(''.join(s))
            if is_prime_miller_rabin(val):
                s[i] = orig
                return False
        s[i] = orig
    return True

def main():
    LIMIT = 10**12
    primes = sieve_primes(1000000)

    squbes = set()

    # p^2 * q^3
    for p in primes:
        p2 = p * p
        if p2 * 8 > LIMIT:
            break
        for q in primes:
            if p == q:
                continue
            q3 = q * q * q
            val = p2 * q3
            if val > LIMIT:
                break
            if contains_200(val):
                squbes.add(val)

    # p^3 * q^2
    for p in primes:
        p3 = p * p * p
        if p3 * 4 > LIMIT:
            break
        for q in primes:
            if p == q:
                continue
            q2 = q * q
            val = p3 * q2
            if val > LIMIT:
                break
            if contains_200(val):
                squbes.add(val)

    candidates = sorted(squbes)

    count = 0
    for val in candidates:
        if is_prime_proof(val):
            count += 1
            if count == 200:
                print(val)
                return

    print("Not found within limit")

if __name__ == "__main__":
    main()