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

Project Euler Problem 200 Solution

EulerSolve provides an optimized solution for Project Euler Problem 200, Find the 200th Prime-proof Sqube Containing the Contiguous Sub-string "200", with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A sqube is a number of the form $$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ prime}.$$ The task is to find the 200th sqube whose decimal expansion contains the contiguous substring "200" and which is prime-proof , meaning that every valid one-digit change produces a composite number. The arithmetic form $p^2q^3$ is the main structural restriction, and the decimal pattern and prime-proof property are two additional filters applied to that sparse family. There is no closed formula for the 200th answer. The practical route is therefore to enumerate all squbes below a bound, sort them, and test each candidate with exact criteria that mirror the statement of the problem. Mathematical Approach The solution is best understood as a search over a highly structured set, not as a scan over all integers. The number-theoretic part identifies which values can even be candidates, and the decimal and primality parts then certify which of those candidates survive....

Detailed mathematical approach

Problem Summary

A sqube is a number of the form

$$n=p^2q^3,\qquad p\neq q,\qquad p,q\text{ prime}.$$

The task is to find the 200th sqube whose decimal expansion contains the contiguous substring "200" and which is prime-proof, meaning that every valid one-digit change produces a composite number. The arithmetic form $p^2q^3$ is the main structural restriction, and the decimal pattern and prime-proof property are two additional filters applied to that sparse family.

There is no closed formula for the 200th answer. The practical route is therefore to enumerate all squbes below a bound, sort them, and test each candidate with exact criteria that mirror the statement of the problem.

Mathematical Approach

The solution is best understood as a search over a highly structured set, not as a scan over all integers. The number-theoretic part identifies which values can even be candidates, and the decimal and primality parts then certify which of those candidates survive.

Bounding the sqube search space

For a fixed bound $L$, every relevant candidate lies in

$$\mathcal S(L)=\{p^2q^3: p,q\text{ prime},\ p\neq q,\ p^2q^3\le L\}.$$

Because the smallest possible cube prime is $2$, any such candidate satisfies

$$p^2\le \frac{L}{2^3}=\frac{L}{8},\qquad p\le \sqrt{L/8}.$$

Once $p$ is fixed, the cube prime must satisfy

$$q^3\le \frac{L}{p^2},\qquad q\le \left(\frac{L}{p^2}\right)^{1/3}.$$

So the search space is finite and can be generated by nested loops over primes with an early stop as soon as $p^2q^3$ exceeds the current bound.

A useful way to write the candidate count is

$$M(L)=\sum_{\substack{p\le \sqrt{L/8}\\ p\text{ prime}}}\#\left\{q\text{ prime}:q\neq p,\ q\le \left(\frac{L}{p^2}\right)^{1/3}\right\}.$$

This expression is not evaluated symbolically in the code, but it makes the geometry of the enumeration explicit.

Recognizing the decimal substring "200"

A positive integer $x$ contains the substring "200" if and only if there exists some offset $m\ge 0$ such that

$$\left\lfloor \frac{x}{10^m}\right\rfloor \equiv 200 \pmod{1000}.$$

That condition says exactly that some consecutive block of three decimal digits equals 200. Repeatedly checking $x\bmod 1000$ and then discarding the last digit by integer division by $10$ is therefore a sliding three-digit window through the decimal expansion. This is the arithmetic content behind the substring filter.

Prime-proof as a digit perturbation condition

Write the decimal expansion of a $d$-digit candidate as

$$x=\sum_{i=0}^{d-1} a_i10^i,\qquad 0\le a_i\le 9,\qquad a_{d-1}\neq 0.$$

If the digit at position $i$ is replaced by another digit $b$, the new number is

$$x'=x+(b-a_i)10^i.$$

All choices $b\neq a_i$ are allowed, except that the leading digit may not be replaced by $0$. The number $x$ is prime-proof exactly when every valid value of $x'$ is composite.

This reformulation explains the code directly. A $d$-digit sqube needs at most $9d$ primality tests, one for each alternative digit at each position, and the candidate is rejected immediately if any modified number is prime.

Why increasing the bound is mathematically safe

If $L_1\le L_2$, then $\mathcal S(L_1)\subseteq \mathcal S(L_2)$. After the substring filter and the prime-proof filter are applied, the same monotonicity still holds: every valid value found below $L_1$ remains present below $L_2$. Therefore, once a bound $L$ produces at least 200 valid squbes, the 200th element of the sorted list below $L$ is already the true answer.

This is why two different implementation styles are correct. One implementation starts from a moderate bound and doubles it until enough values are found. The other two choose a very large fixed bound from the beginning. Both rely on the same invariant: enlarging the bound can only add larger candidates, never invalidate smaller ones.

Worked Example: why $200$ itself qualifies

The number $200$ is already a sqube, because

$$200=5^2\cdot 2^3.$$

It obviously contains the substring "200". To show that it is prime-proof, inspect the three digit positions.

Changing the hundreds digit gives $100,300,400,\dots,900$, all composite. Changing the tens digit gives $210,220,\dots,290$, also all composite because they are even and larger than $2$. Changing the units digit gives $201,202,\dots,209$; the even values are composite, $201$ and $207$ are divisible by $3$, $205$ is divisible by $5$, $203=7\cdot 29$, and $209=11\cdot 19$.

So every valid one-digit change of $200$ is composite. This is the exact logical pattern used for every candidate in the final search.

How the Code Works

The C++, Python, and Java implementations all use the same pipeline: generate squbes below a bound, keep only those whose decimal expansion contains "200", and then verify prime-proofness by examining every allowed single-digit modification.

Generating and ordering the squbes

Each implementation begins by producing enough prime numbers with a sieve. It then loops over distinct prime pairs and forms products of the shape $p^2q^3$ until the current bound is exceeded. The resulting values are collected in a structure that removes duplicates and preserves sorted order after the generation phase.

Two implementations explicitly enumerate both exponent assignments $p^2q^3$ and $p^3q^2$, then deduplicate. The C++ implementation covers the same family by letting the squared prime and the cubed prime play ordered roles inside a single formula. The mathematical candidate set is identical in all three languages.

Applying the two filters

The substring test is implemented in decimal arithmetic or via the decimal string representation, but both versions test the same condition. Only values that pass this stage are sent to the prime-proof check.

For the prime-proof test, the C++ implementation mutates one digit arithmetically using powers of $10$, which is a direct realization of $x' = x + (b-a_i)10^i$. The Python and Java implementations rebuild the altered decimal string and convert it back to an integer. These are different surfaces for the same mathematical operation.

Primality testing and stopping

Every modified number produced by the prime-proof test must be checked for primality. The C++ implementation uses deterministic Miller-Rabin valid for 64-bit integers. The Python and Java implementations use trial division in the $6k\pm 1$ pattern. The logic is the same: if any modified value is prime, the original sqube is rejected.

After that, the valid squbes are counted in increasing order. The C++ implementation can grow the bound geometrically until the target count is reached and also includes sanity checks: the first squbes are $72,108,200,392,500$, and the second prime-proof sqube containing "200" is $1992008$. The Python and Java implementations instead start from a sufficiently large fixed bound and stop once the 200th valid value is encountered.

Complexity Analysis

Let $L$ be the final bound large enough to contain the 200th answer, and let $M(L)$ be the number of squbes generated below that bound. Prime generation by a sieve costs $O(B\log\log B)$, where $B$ is the largest sieved integer. In the adaptive version $B$ is essentially $\sqrt{L/8}$; in the fixed-bound versions it is chosen on the same square-root scale.

Building the candidate list costs $O(M(L))$ arithmetic operations before sorting, and ordering the resulting values costs $O(M(L)\log M(L))$. The substring filter is only linear in the number of decimal digits of each candidate and is comparatively cheap.

The expensive phase is the prime-proof certification. If $F(L)$ candidates survive the substring test and a candidate $x$ has $d(x)$ decimal digits, then the number of primality tests is at most

$$\sum_{x\in F(L)} 9\,d(x).$$

In C++, each of these calls is a fixed-base Miller-Rabin test, so for 64-bit inputs the primality step is effectively near-constant time per call. In Python and Java, trial division has worst-case cost $O(\sqrt{x})$ per call, but the number of tested neighbors stays manageable because the sqube family is sparse and the decimal filter removes most candidates first.

The memory usage is $O(M(L))$ for the stored squbes, plus the prime table. The key efficiency gain is structural: the search never scans all integers up to $L$; it explores only numbers of the specific form $p^2q^3$, which is a dramatically smaller set.

Footnotes and References

Project Euler problem page: https://projecteuler.net/problem=200
Prime number: Wikipedia - Prime number
Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes
Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test
Trial division: Wikipedia - Trial division
Positional notation: Wikipedia - Positional notation

Problem 200 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <functional>

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

struct Options {
    int target = 200;
    u64 initial_limit = 1000000000ULL;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--target=", options.target) ||
            parse_u64_after_prefix(arg, "--initial-limit=", options.initial_limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.target >= 1 && options.initial_limit >= 100;
}

u64 mul_mod(const u64 a, const u64 b, const u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * b) % mod);
}

u64 pow_mod(u64 base, u64 exp, const u64 mod) {
    u64 result = 1 % mod;
    base %= mod;

    while (exp > 0) {
        if (exp & 1ULL) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

bool is_prime(const u64 n) {
    if (n < 2) {
        return false;
    }
    for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        if (n == p) {
            return true;
        }
        if (n % p == 0) {
            return false;
        }
    }

    u64 d = n - 1;
    int s = 0;
    while ((d & 1ULL) == 0ULL) {
        d >>= 1;
        ++s;
    }

    constexpr u64 bases[] = {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL};
    for (u64 a : bases) {
        if (a % n == 0) {
            continue;
        }
        u64 x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) {
            continue;
        }

        bool witnessed = true;
        for (int r = 1; r < s; ++r) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                witnessed = false;
                break;
            }
        }
        if (witnessed) {
            return false;
        }
    }

    return true;
}

std::vector<int> primes_up_to(const int n) {
    std::vector<std::uint8_t> is_prime_small(static_cast<std::size_t>(n + 1), 1);
    is_prime_small[0] = 0;
    is_prime_small[1] = 0;

    for (int i = 2; i * i <= n; ++i) {
        if (!is_prime_small[static_cast<std::size_t>(i)]) {
            continue;
        }
        for (int j = i * i; j <= n; j += i) {
            is_prime_small[static_cast<std::size_t>(j)] = 0;
        }
    }

    std::vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime_small[static_cast<std::size_t>(i)]) {
            primes.push_back(i);
        }
    }
    return primes;
}

bool contains_200(u64 x) {
    while (x >= 200) {
        if (x % 1000ULL == 200ULL) {
            return true;
        }
        x /= 10ULL;
    }
    return false;
}

bool is_prime_proof(const u64 x) {
    u64 pow10 = 1;
    while (pow10 <= x) {
        const int digit = static_cast<int>((x / pow10) % 10ULL);
        const u64 base = x - static_cast<u64>(digit) * pow10;

        for (int repl = 0; repl <= 9; ++repl) {
            if (repl == digit) {
                continue;
            }
            if (pow10 * 10ULL > x && repl == 0) {
                continue;
            }

            const u64 candidate = base + static_cast<u64>(repl) * pow10;
            if (is_prime(candidate)) {
                return false;
            }
        }

        pow10 *= 10ULL;
    }

    return true;
}

std::vector<u64> generate_squbes(const u64 limit) {
    const u64 max_p = static_cast<u64>(std::sqrt(static_cast<long double>(limit / 8ULL))) + 5ULL;
    const std::vector<int> primes = primes_up_to(static_cast<int>(max_p));

    std::vector<u64> squbes;
    for (int p : primes) {
        const u128 p2 = static_cast<u128>(p) * static_cast<u128>(p);
        if (p2 * 8U > limit) {
            break;
        }

        for (int q : primes) {
            if (q == p) {
                continue;
            }

            const u128 q3 = static_cast<u128>(q) * q * q;
            const u128 value = p2 * q3;
            if (value > limit) {
                break;
            }

            squbes.push_back(static_cast<u64>(value));
        }
    }

    std::sort(squbes.begin(), squbes.end());
    squbes.erase(std::unique(squbes.begin(), squbes.end()), squbes.end());
    return squbes;
}

std::vector<u64> first_squbes(const std::size_t k) {
    u64 limit = 1000;
    while (true) {
        std::vector<u64> squbes = generate_squbes(limit);
        if (squbes.size() >= k) {
            squbes.resize(k);
            return squbes;
        }
        limit *= 2;
    }
}

u64 solve(const int target, u64 limit) {
    while (true) {
        const std::vector<u64> squbes = generate_squbes(limit);

        std::vector<u64> matches;
        matches.reserve(squbes.size() / 4);

        for (u64 x : squbes) {
            if (!contains_200(x)) {
                continue;
            }
            if (is_prime_proof(x)) {
                matches.push_back(x);
            }
        }

        if (static_cast<int>(matches.size()) >= target) {
            return matches[static_cast<std::size_t>(target - 1)];
        }

        limit *= 2ULL;
    }
}

bool run_checkpoints() {
    const std::vector<u64> first = first_squbes(5);
    const std::vector<u64> expected = {72ULL, 108ULL, 200ULL, 392ULL, 500ULL};
    if (first != expected) {
        std::cerr << "Checkpoint failed for first squbes" << '\n';
        return false;
    }

    if (solve(2, 2000000ULL) != 1992008ULL) {
        std::cerr << "Checkpoint failed for second prime-proof sqube containing 200" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.target, options.initial_limit) << '\n';
    return 0;
}

Python

# 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: replacing any digit doesn't produce a prime.

from math import isqrt

def solve():
    def sieve_primes(n):
        s = bytearray(b'\x01') * (n+1)
        s[0] = s[1] = 0
        for i in range(2, isqrt(n)+1):
            if s[i]:
                for j in range(i*i, n+1, i): s[j] = 0
        return [i for i in range(n+1) if s[i]]

    def is_prime(n):
        if n < 2: return False
        if n < 4: return True
        if n % 2 == 0 or n % 3 == 0: return False
        i = 5
        while i*i <= n:
            if n % i == 0 or n % (i+2) == 0: return False
            i += 6
        return True

    def contains_200(x):
        while x >= 200:
            if x % 1000 == 200: return True
            x //= 10
        return False

    def is_prime_proof(x):
        s = str(x)
        for i in range(len(s)):
            orig = int(s[i])
            for d in range(10):
                if d == orig: continue
                if i == 0 and d == 0: continue
                candidate = int(s[:i] + str(d) + s[i+1:])
                if is_prime(candidate): return False
        return True

    limit = 10**12
    primes = sieve_primes(isqrt(limit) + 10)
    squbes = set()
    for p in primes:
        p2 = p*p
        if p2 * 8 > limit: break
        for q in primes:
            if q == p: continue
            val = p2 * q * q * q
            if val > limit: break
            squbes.add(val)
    for p in primes:
        p3 = p*p*p
        if p3 * 4 > limit: break
        for q in primes:
            if q == p: continue
            val = p3 * q * q
            if val > limit: break
            squbes.add(val)

    squbes = sorted(squbes)
    count = 0
    for x in squbes:
        if not contains_200(x): continue
        if is_prime_proof(x):
            count += 1
            if count == 200:
                print(x)
                return

solve()

Java

import java.util.*;

public class Euler200 {
    static boolean isPrime(long n) {
        if (n < 2)
            return false;
        if (n < 4)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (long i = 5; i * i <= n; i += 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        return true;
    }

    static boolean contains200(long x) {
        while (x >= 200) {
            if (x % 1000 == 200)
                return true;
            x /= 10;
        }
        return false;
    }

    static boolean isPrimeProof(long x) {
        String s = Long.toString(x);
        for (int i = 0; i < s.length(); i++) {
            int orig = s.charAt(i) - '0';
            for (int d = 0; d <= 9; d++) {
                if (d == orig)
                    continue;
                if (i == 0 && d == 0)
                    continue;
                long c = Long.parseLong(s.substring(0, i) + d + s.substring(i + 1));
                if (isPrime(c))
                    return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        long limit = (long) 1e12;
        int maxP = (int) Math.sqrt(limit / 8.0) + 10;
        boolean[] sieve = new boolean[maxP + 1];
        Arrays.fill(sieve, true);
        sieve[0] = sieve[1] = false;
        for (int i = 2; i * i <= maxP; i++)
            if (sieve[i])
                for (int j = i * i; j <= maxP; j += i)
                    sieve[j] = false;
        int[] primes = new int[maxP];
        int pc = 0;
        for (int i = 2; i <= maxP; i++)
            if (sieve[i])
                primes[pc++] = i;
        TreeSet<Long> squbes = new TreeSet<>();
        for (int i = 0; i < pc; i++) {
            long p = primes[i];
            if (p * p * 8 > limit)
                break;
            for (int j = 0; j < pc; j++) {
                if (i == j)
                    continue;
                long q = primes[j];
                long v = p * p * q * q * q;
                if (v > limit)
                    break;
                squbes.add(v);
            }
        }
        for (int i = 0; i < pc; i++) {
            long p = primes[i];
            if (p * p * p * 4 > limit)
                break;
            for (int j = 0; j < pc; j++) {
                if (i == j)
                    continue;
                long q = primes[j];
                long v = p * p * p * q * q;
                if (v > limit)
                    break;
                squbes.add(v);
            }
        }
        int count = 0;
        for (long x : squbes) {
            if (!contains200(x))
                continue;
            if (isPrimeProof(x)) {
                count++;
                if (count == 200) {
                    System.out.println(x);
                    return;
                }
            }
        }
    }
}