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 May 21, 2026

Problem #0200

Level Level 09

Solved By 2,828

Languages C++, Python

Answer 229161792008

Length 466 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 Development

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

The search is only practical if we filter very early. A sqube is determined by two distinct primes, so the code first generates every value of the form p^2 q^3 or p^3 q^2 below a safe cutoff and immediately discards anything whose decimal expansion does not contain "200". That leaves a much smaller candidate list.

The prime-proof test is then local in the decimal representation. For each remaining sqube, we try every one-digit substitution, skipping the original digit and illegal leading zeros, and run a deterministic Miller-Rabin test on the modified number. If every such mutation is composite, the candidate survives. Sorting the survivors and taking the 200th one finishes the computation.

Pseudocode

Sieve primes up to a limit that is sufficient for all squbes below B.
Generate every distinct sqube of the forms p^2 q^3 and p^3 q^2 below B.
Keep only the squbes whose decimal expansion contains the substring "200".
Sort the filtered values.

Scan the sorted candidates in order:
    for each digit position,
    try every other replacement digit that keeps the number valid;
    if any replacement is prime, reject the candidate immediately.

Count the candidates that pass this test and return the 200th one.

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()