Project Euler Forum

Problem 822 – Square the Smallest

This problem assumes the following operations:

1. compare numbers in a list to find the smallest
2. square the number
3. repeat 10¹⁶ times
4. sum numbers from the list

As multiple squaring of the numbers makes them soon very big, we are suggested (very wisely) to give the result modulo 1234567891.

My question is: are we expected to apply modulo 1234567891:

1. In the step 2 already? – So each calculated square is possibly made smaller before replacing it's predecessor in the list.
2. In the step 4 only? – While summing the list.

I found the trick to optimise high powers of numbers modulo 1234567891, but if in the step 1 I must compare original numbers (without modulo) I can not benefit from my optimization trick
Or am I missing something?

Thanks for your interest in this problem I hope you are enjoying it.

Use the modulus in step 4 only - so you can't use your optimising trick (or can you).

bruce_love wrote: Sun Mar 03, 2024 9:23 pm Use the modulus in step 4 only - so you can't use your optimising trick (or can you).

I could use my trick if all the list elements are either raised to the same power or I could predict their final powers. But the final powers of list elements are neither equal nor predictable, as the lower the value of the element list, the higher the power. So before the last (10¹⁶th) comparison, I could not predict the final power of each element, so I could not decide about using the trick (or could I).

I solved the problem.

zilet wrote: Mon Mar 04, 2024 7:34 am But the final powers of list elements are neither equal nor predictable, [...]

They are not equal, but they are predictable, of course!