Bruteforce Algorithm to Find the Unique Positive Integer Whose Square has the form 1_2_3_4_5_6_7_8_9_0 (Concealed Square)

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.

The “_” may not be the same digit. If it is the same digit, there is only 9 possible solutions, which you can just check one by one in O(1) time.

Bruteforce Algorithm to Find the Concealed Square

The Maximum possible square number is 192939495969798990 and the minimal square number is 1020304050607080900. The square root has to start with 1 and end with 0 so that the square number will start with 1 and end with zero.

Also, the last two digits should be 00 as any square numbers (more than two digit) will end with 00. This means our square number is 1_2_3_4_5_6_7_8_900. There fore we can just search the number that squares to 1_2_3_4_5_6_7_8_9 and multiple the original number by ten.

In order to end with 9, it has to be end with 7 or 3. Thus we can rule out the even numbers.

Thus, we compute the lower and upper bound, and do a bruteforce check for all the odd numbers between. The following Python code will take roughly half minute to run as it has 18946280 numbers to check. We convert the square number to string and use [::2] to pick up the digits in odd positions. Similarly we can use [1::2] to pick up the digits in the even positions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

from math import sqrt
 
def check(x):
    template = "1_2_3_4_5_6_7_8_9_0"
    if (len(str(x)) != len(template)):
        return False
    return str(x)[::2] == "1234567890"
 
low = int(sqrt(1020304050607080900))/10
high = int(sqrt(1929394959697989900))/10
 
for i in range(low, high + 1, 2):
    x = i * 10
    if check(x * x):
        print(x, x * x)
        break

from math import sqrt

def check(x):
    template = "1_2_3_4_5_6_7_8_9_0"
    if (len(str(x)) != len(template)):
        return False
    return str(x)[::2] == "1234567890"

low = int(sqrt(1020304050607080900))/10
high = int(sqrt(1929394959697989900))/10

for i in range(low, high + 1, 2):
    x = i * 10
    if check(x * x):
        print(x, x * x)
        break

The answer is 1389019170 and it squares to 1929374254627488900.

–EOF (The Ultimate Computing & Technology Blog) —