Creative Numbers

Alice plays the following game, she starts with a list of integers $L$ and on each step she can either:
remove two elements $a$ and $b$ from $L$ and add $a^b$ to $L$
or conversely remove an element $c$ from $L$ that can be written as $a^b$, with $a$ and $b$ being two integers such that $a, b > 1$, and add both $a$ and $b$ to $L$
For example starting from the list $L=\{8\}$, Alice can remove $8$ and add $2$ and $3$ resulting in $L=\{2,3\}$ in a first step. Then she can obtain $L=\{9\}$ in a second step.
Note that the same integer is allowed to appear multiple times in the list.
An integer $n>1$ is said to be creative if for any integer $m \gt 1$ Alice can obtain a list that contains $m$ starting from $L=\{n\}$.

Find the sum of all creative integers less than or equal to $10^{12}$.

The problem can be approached by considering the definition of creative number: A number, say ‘n’, will be creative only if, starting from ‘n’, it can transform into any number ‘m’.

1. Firstly, consider ‘n’. To be able to transform into any number ‘m’, ‘n’ must be expressed as ‘a^b’, where ‘a’ and ‘b’ are greater than 1. We know that ‘n’ is less than or equal to 10^12, therefore, for any pair {a, b}, the maximum number of possibilities will be when ‘a’ equals to 2. This is because for any pair {a, b} equal to n, n = a^b is maximum when a is minimum and b is maximum (Note: a,b > 1). If ‘a’ is minimum (2), then ‘b’ is ln(10^12)/ln(2) <= 40 (We used log properties to switch base to base 'e', ln means natural logarithm). 2. From point 1, we found that 'b' can take integer value from 2 to 40. This gives us some 'n' values. Remembering that the same number can appear multiple times in list 'L', we can add 'n' = 'a' = 2 into our list. Now we have b-1 copies of '2' in list 'L'. Any 'm' which is less than or equal to 'b' can now be obtained by adding pairs {2,2} from list 'L'. For 'm' > ‘b’, it can be obtained by firstly using operation 2 on any element in list ‘L’ so as to get a copy of ‘2’ and a copy of ‘3’. Now, using operation 1, we can then combine ‘b’ copies of ‘2’ to get ‘b’ * 2 = 2b. We would have transformed ‘n’ into ‘m’ using Alice’s operations. Thus, ‘n’ is creative.

Just to reiterate, the above steps have shown us that: Any ‘n’ which can be represented as 2^b, where 2 <= b <= 40, is creative. 3. Adding all the creative numbers, the required sum would be the sum of all 2^b for 2<=b<=40. So the sum is 2^2 + 2^3 + 2^4 ... +2^40 = 4 + 8 + 16 + ....+ 2^40 = 2^41 - 4 (Using formula of sum of geometric progression). So, the sum of all creative integers less than or equal to $10^{12}$ is $2^{41} - 4$.

More Answers: