Project Euler 822 - Square the Smallest

Official link: https://projecteuler.net/problem=822

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:

Square second element
Square first element
Square rest of the elements
Repeat steps 1-3

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)

A = [2, 3, 4, 5, 6, 7, 8, 9, 10]
1. 2^2 < 10
A = [3, 4, 4, 5, 6, 7, 8, 9, 10]
1. 3^2 < 10
A = [4, 4, 5, 6, 7, 8, 9, 9, 10]
1. 4^2 = 16 > 10, we have found our critical point, k = 2

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

Page updated

Google Sites

Report abuse