Detailed mathematical approach

Problem Summary

Start with the one-element list \(\{n\}\). Alice may replace two list elements \(a,b>1\) by the single value \(a^b\), and she may replace one element \(c\) by two values \(a,b>1\) whenever \(c=a^b\). A number \(n>1\) is called creative if, for every target \(m>1\), there exists some sequence of such moves that leads to a list containing \(m\).

For Problem 616 we must compute

$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creative}}} n.$

The implementations do not explore the move graph directly. Instead they use a classification theorem for all creative numbers up to the required limit and then turn the problem into a finite enumeration.

Mathematical Approach

Let \(X=10^{12}\). Define the two sets

$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$

$\mathrm{PQ}(X)=\{p^q\le X : p\text{ prime},\ q\text{ prime}\}.$

The C++, Python, and Java implementations rely on the classification

$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$

where \(\mathcal{C}(X)\) denotes the set of creative numbers not exceeding \(X\). The remaining work is to understand why this description is natural and how to sum it efficiently.

Step 1: Only perfect powers can even enter the discussion

If \(n\) is not a perfect power, then the starting list \(\{n\}\) cannot be split at all, because there do not exist integers \(a,b>1\) with \(n=a^b\). Therefore the process is stuck immediately, and the only number ever present is \(n\) itself.

But a creative number must be able to reach every target \(m>1\), so a non-perfect power is impossible. Hence every creative \(n\le X\) must lie in \(\mathrm{PP}(X)\).

Step 2: Prime-base, prime-exponent powers are too rigid

Now consider

$n=p^q,$

with \(p\) prime and \(q\) prime. Splitting \(n\) yields the two-element list \(\{p,q\}\). Neither of those values can be split any further, because primes are not nontrivial perfect powers.

From \(\{p,q\}\), the only possible merges are \(p^q\) and \(q^p\). If \(p=q\), even that swap does nothing. So the reachable state space stays extremely small and cannot contain arbitrary targets.

Therefore every member of \(\mathrm{PQ}(X)\) must be removed from the creative set.

Step 3: Why \(16\) is a separate exceptional value

The number \(16\) is a perfect power, but it is not in \(\mathrm{PQ}(X)\), because its standard forms are

$16=2^4=4^2.$

Nevertheless it is still not creative. Every nontrivial split of \(16\) produces only powers of \(2\), and splitting those outputs again still produces only powers of \(2\).

This is stable under merging as well. If all current elements are powers of \(2\), say \(2^r\) and \(2^s\), then

$\left(2^r\right)^{2^s}=2^{r2^s},$

which is again a power of \(2\). So starting from \(16\), the process never leaves the world of powers of \(2\). In particular, a target such as \(3\) can never appear. That is why the implementations subtract \(16\) separately.

Step 4: The positive direction becomes a classification theorem

The difficult direction is the converse: apart from the excluded family \(\mathrm{PQ}(X)\) and the special case \(16\), every remaining perfect power up to \(10^{12}\) is creative. The implementations take exactly that theorem as their mathematical foundation.

Once this classification is accepted, the answer is no longer about searching for transformations. It is just the sum of all perfect powers up to \(X\), minus the sum of the prime-prime powers, minus the single exceptional value \(16\).

Step 5: Convert the theorem into a summation formula

Hence

$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$

with \(X=10^{12}\).

Two implementation details matter here:

First, \(\mathrm{PP}(X)\) must be deduplicated, because the same integer can appear from several exponent choices. For example,

$64=2^6=4^3=8^2.$

Second, \(\mathrm{PQ}(X)\) does not need deduplication. If \(p^q=r^s\) with \(p,r\) prime and \(q,s\) prime, unique prime factorization forces \(p=r\) and \(q=s\).

Worked Example: apply the rule to \(X=100\)

The perfect powers up to \(100\) are

$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$

The prime-prime powers among them are

$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$

Removing those values and then removing \(16\) leaves

$\mathcal{C}(100)=\{36,64,81,100\}.$

Therefore

$S(100)=36+64+81+100=281.$

This small example mirrors the full computation exactly: generate perfect powers, subtract the prime-prime family, and subtract the isolated exception \(16\).

How the Code Works

The implementations first determine the largest relevant exponent \(E\) with \(2^E\le X\). For \(X=10^{12}\), this gives \(E=39\), because \(2^{39}\le 10^{12} < 2^{40}\).

For each exponent \(e=2,3,\dots,E\), the implementation computes the largest base \(a\) satisfying \(a^e\le X\) by integer binary search. It then enumerates every value \(a^e\) in that range and stores all of them in a list or set. After sorting and deduplication, their total gives the sum over \(\mathrm{PP}(X)\).

Next, the implementation builds the subtraction term \(\mathrm{PQ}(X)\). Since \(p^q\le X\) and \(q\ge 2\), every prime base satisfies \(p\le \sqrt{X}=10^6\), so a sieve up to \(10^6\) is enough. The only relevant exponents are the primes between \(2\) and \(39\). Every valid value \(p^q\le X\) is added to the prime-prime sum.

Finally, the answer is computed as

$\text{sum of perfect powers}-\text{sum of prime-prime powers}-16.$

The implementations also contain short sanity checks: several included values such as \(36\), \(81\), \(100\), and \(216\) are shown to reach \(64\), while \(16\) fails a negative check because all reachable values remain powers of \(2\).

Complexity Analysis

Let

$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$

This is the number of raw perfect-power candidates generated before deduplication. The square case dominates, so \(M=O(X^{1/2})\). Sorting and deduplicating those candidates costs \(O(M\log M)\) time and \(O(M)\) memory.

The prime sieve up to \(10^6\) costs \(O(10^6\log\log 10^6)\) time and \(O(10^6)\) memory. The list of prime exponents is tiny because \(E=39\). Overall, the method is easily fast enough for \(X=10^{12}\) and avoids any attempt to search the full transformation graph.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=616
2. Perfect power: Wikipedia - Perfect power
3. Prime power: Wikipedia - Prime power
4. Exponentiation: Wikipedia - Exponentiation
5. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes