Bruteforce Algorithm to Find the Unique Positive Integer Whose S

  • 时间:2020-09-08 11:19:41
  • 分类:网络文摘
  • 阅读:115 次

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

推荐阅读:
元曲《骤雨打新荷》赏析  阿房宫赋原文及翻译  归去来兮辞原文及翻译  兰亭集序原文及翻译  陈情表原文及翻译  后出师表原文及翻译  前出师表原文及翻译  诫兄子严敦书原文及翻译  光武帝临淄劳耿弇原文及翻译  我 书=快乐 
评论列表
添加评论