Concealed Squares

This is my solution to Project Euler problem number 206. Although a brute force solution can be easily derived, this approach makes use of mathematical analysis to find the answer in less time. The problem statement follows.

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit.

It can be shown that the answer lies in the range R.

R = [floor(sqrt(1020304...00)), ceiling(sqrt(192939..90))] = [1010101010, 1389026624]

R has 378,925,614 integers, which is a lot to test quickly. Fortunately, one can reduce it by noticing that the square of the integer is divisible by 10, which implies that the integer too is divisible by 10. This leaves us with the possible solution set P.

P = {1010101010, 1010101020, ..., 1389026620}

The largest possible number is 19293949596979899990, which requires 65 bits to be represented as an unsigned integer.

However, because we know that the answer is a multiple of 10, we also know that the square of the answer is a multiple of 100. And, therefore, that it ends with zeros. This allows for another optimization: divide all numbers in P by 10 and find the one whose square is of the form 1_2_3_4_5_6_7_8_9. These numbers fit into 64-bit words, so arithmetic with them will not be specially expensive.

P has 37,892,561 elements, but we do not need to check all of them. If x² ends in 9, x ends in 3 or 7, which reduces by 80% the number of values we have to test.

Using Clang with the O3 flag, my C++ implementation of the algorithm finishes after 120 ms, which is a good enough solution for this problem.