Project Euler 822 - Square the Smallest

Official link:

Thought Process

I continued the original problem to see if I could find some sort of patterns. I found that for the original array [2, 3, 4, 5] the following pattern worked. First we square the first element then:

But using this trick did not work for finding the solution to S(10, 100), after investigating more I realised it is because the array goes up to 10, crucially it includes 9. This means at some point Step 3 above fails, because we will square 3^2 instead of 9 first breaking the cycle.

At this point it is clear that the problem has something to do with finding the exact cycle with square numbers.

Knowing the above I deduce the following

Basically, this tells us that once we have a found a turn where the smallest element squared becomes the largest, we enter a cycle where we can simply square every element of the sorted array in order. I illustrate this with S(10, 100)

Notice that now we will square the first element every turn.

Since we have 98 turns left, and 98 = 9*10 + 8, we know we have the square every element in our final A, 10 times, then we square the first 8 elements again to get our final answer. Don't forget to use Euler's Theorem to do the squaring since conveniently 1234567891 is a prime.

Interactive Code

Input 2 integers separated by a space (a, b)

Code will output S(a, b) mod 1234567891