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

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