Bruteforce Algorithm to Find the Unique Positive Integer Whose S

  • Time:2020-09-08 11:19:41
  • Class:Weblog
  • Read:27

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) —

Recommend:
Switching to a Blogging Career: Can You Afford to Work from Home
4 Features that Will Enhance Your Blog
Amazon Surpasses Google: Should you Change your SEO Strategies?
How to Optimize WordPress Categories and Tags
Blogging Royalties: Michelle Obama Interviewing Barack on her Po
Content Marketing: Expectations Vs Reality
Blogger Skills: LinkedIn and Microsoft’s Digital Skill Programs
5 Tips for Creating a Content Strategy for Your eCommerce Websit
5 Tips You Can Use to Launch a Successful Property Management Bl
Blogging and Gaming Finally Recognized as Professions
Share:Facebook Twitter
Comment list
Comment add