Project Euler Problem 616
Alice plays the following game, she starts with a list of integers L and on each step she can either: - remove two eleme
Solution
Answer: 310884668312456458
The key observation is that a number is creative iff it is a perfect power, but not of the form $p^q$ with both $p$ and $q$ prime, with one special exception: $16$ is not creative despite being $2^4=4^2$. Thus the required sum is:
$$\sum(\text{perfect powers } \le 10^{12}) ;-; \sum(p^q \le 10^{12},\ p,q \text{ prime}) ;-;16$$
Enumerating all perfect powers up to $10^{12}$, removing all prime-to-prime powers, and subtracting the exceptional case $16$ gives:
Answer: 310884668312456458