# Improve upon algorithm for finding a specific perfect square in a range of two very large integers $(10^{28})$

Assume you are given a set of digits that represent every other digit in a perfect square, how can you find the root of a number that would have the same pattern - guaranteed to exist and to be unique.

For example, $8*7*6$, if you replace the asterisks with all $0$’s and all $9$’s you would have $89796$ and $80706$. If you take the square of each, you get $299$ and $284$ (rounding to an integer). You can then iterate through each integer from $284$, to $299$, square them, until you find a number that matches the same pattern. Turns out the answer is $286^2$ which equals $81796$.

We also know with the units digit being a $6$, that the first two digits are limited to a set of numbers, 96 being one of them. So just by knowing the last digit is $6$, one partial solution could be $8*796$, but could also be $8*744$. Regardless, there are very few options and the result set is narrowed. Just by applying $0-9$ to $8*796$, iterate through them, you would stumble across 81796 with a square root of $286$.

If the problem was restricted to perfect squares with relatively smaller numbers, the solution would be simple - just find the max/min roots $(284-299)$, square them and find the perfect squares that satisfy the pattern of $8*7*6$, for example. Another example is $1*2*3*4$ where the square root is $1312^2 = 1721344$.

However, using this algorithm, my program takes forever to run with very large integers. Seems like there would be a way of building the square by applying perfect square properties, or applying another algorithm that reduces the possibilities.

EDITED: The larger examples are: $23209192748299230494155021081$ which is a perfect square and its root is: $152345635803259$. The numbers provided are: $229978920915201$, which, using the example above: $2*2*9*9*7*8*9*2*0*9*1*5*2*0*1$ with the asterisks being a placeholder for a digit. Another example: $232091909800969$ is the perfect square, and the square root is: $15234563$. The numbers provided are:$22999099$ meaning: $2*2*9*9*9*0*9*9$ with the asterisks being placeholders. The algorithm I detailed above (finding the min/max roots, squaring, and comparing) works fine for the perfect square: $232091909800969$, but not on the perfect square: $23209192748299230494155021081$ -- takes too long.

Hope this makes sense.

Edited: The following is the code I used. It is Python 3.6.3 running on a MacPro 10.13.3, 2.7 GHz 12-Core Intel Xeon E5, 64GB RAM:

# !/bin/python3

import sys, math, time

def removeOdds(num):
result = ""
num = str(num)
for i in range(0, len(num), 2):
result = result + num[i]
return int(result)

def findRoot(n, num):
def perfect_squares():
if num[-1] == 0:
return (x for x in range(lowSq, highSq + 1) if (x % 10 == 0) and removeOdds(x ** 2) == num1)
if num[-1] == 1:
return (x for x in range(lowSq, highSq + 1) if (x % 10 == 1 or x % 10 == 9) and removeOdds(x ** 2) == num1)
if num[-1] == 4:
return (x for x in range(lowSq, highSq + 1) if (x % 10 == 2 or x % 10 == 8) and removeOdds(x ** 2) == num1)
if num[-1] == 5:
return (x for x in range(lowSq, highSq + 1) if (x % 10 == 5) and removeOdds(x ** 2) == num1)
if num[-1] == 6:
return (x for x in range(lowSq, highSq + 1) if (x % 10 == 4 or x % 10 == 6) and removeOdds(x ** 2) == num1)
if num[-1] == 9:
return (x for x in range(lowSq, highSq + 1) if (x % 10 == 3 or x % 10 == 7) and removeOdds(x ** 2) == num1)

low = int('0'.join(str(x) for x in num))
high = int('9'.join(str(x) for x in num))
num1 = int(''.join(str(x) for x in num))
lowSq = int(math.ceil(math.sqrt(low)))
highSq = int(math.floor(math.sqrt(high)))
x = perfect_squares()
y = x.__next__()
return y

def main(n, num):
start = time.clock()
root = findRoot(n, num)
print(root)
print ("execution time: ", time.clock() - start)

if __name__ == '__main__':
n  = 3
num = [8,7,6]
#n = 4
#num = [1, 2, 3, 4]
# n = 8 takes approx 0.89 sec to run, expected result: 15234563
#n = 8  # int(input().strip())
#num = [2, 2, 9, 9, 9, 0, 9, 9]  # list(map(int, input().strip().split(' ')))
# n = 10 takes approx 120 sec to run, expected result: 1234567890
# n = 10
# num = [1, 2, 1, 7, 7, 0, 9, 5, 1, 0]
# n = 15 I've never been patient enough to see if it will complete
#n = 15
#num = [2, 2, 9, 9, 7, 8, 9, 2, 0, 9, 1, 5, 2, 0, 1]

main(n, num)

• I wish you would have said 15-digit numbers instead of $10^{14}$ numbers. – steven gregory Apr 2 '18 at 0:16
• Understand the confusion, and corrected. Thanks! – Shanemeister Apr 2 '18 at 3:29
• A $15$ digit number will only have $7$ asterisks, so $10^7$ possibilities. That should not take forever. Even $9$ asterisks should be done well under an hour. – Ross Millikan Apr 2 '18 at 3:36
• There is a benchmark of 10 seconds for the algorithm to complete. The number 232091909800969 takes under 3 seconds to complete, but with the number 23209192748299230494155021081, the program has yet to produce the result. – Shanemeister Apr 2 '18 at 3:41
• With the larger number (23209192748299230494155021081): the smallest perfect square root, compared to the highest, and the difference between the two is: 142,158,681,437,647 -- 171,172,427,099,107 -- 29,013,745,661,460 – Shanemeister Apr 2 '18 at 3:47

The problem with your algorithm is you are exploring the search space very inefficiently. This sort of problem is easily amenable to a depth-first search, starting with the lower digits and checking to see if they are possible.

For example, if your square number ends in $0*1$ there are only a relatively small number of 3 digit numbers your root could end in: $011, 021, 031, \dots, 241, 321, 491, 501, \dots$

Here is the rough idea that does the n=10 case in 2 seconds. It is very inefficient since for the last $d$ digits of $x$, we only check the last $d$ digits of $x^2$. The valid checking function does a lot of repeated computation, and the code doesn't handle adding zeroes efficiently either.

num = [1, 2, 1, 7, 7, 0, 9, 5, 1, 0]
num2 = [8, 7, 6]

def valid(num, x):
for i in range(len(num)):
if (x // 10**(2*i)) % 10 != num[-i-1]:
return False
return True

def max_num(num):
return int('9'.join(str(d) for d in num))

def dfs(num, mnum, candidate, base):
#print(base, candidate, candidate**2)
if candidate**2 > mnum: return None

if valid(num, candidate**2):
return candidate

for i in range(10):
x = i * 10**base + candidate
if valid(num[-1-base//2:], x**2):
sol = dfs(num, mnum, x, base+1)
if sol: return sol

return None

print(dfs(num, max_num(num), 0, 0))

• Thanks for the response @qwr ! Your algorithm is much faster, and I got 2.3 sec using yours and 118 sec using mine for the n=10 case -- so a considerable improvement! However, I still can't get an answer back with larger numbers, like: num = [2, 2, 9, 9, 7, 8, 9, 2, 0, 9, 1, 5, 2, 0, 1] -- n = 15, and I am looking for under 10 sec responses. Would you mind explaining the logic of your algorithm just to make sure I understand what the recursion is doing. Thanks again! – Shanemeister Apr 3 '18 at 15:09
• What I "think" it will take to get acceptable times is to figure out a way of doing some sort of bisection search. For example, num = [8,7,6], round (sqrt(80706)) = 284 and round(sqrt((897969) = 300. Start with sq(284) = 80656. So I split the indexes and jump to 292 -- sq(292) = 85264. This number is 8*2*4 -- I don't think there is away to figure out whether to go lower, or higher. We know we should go down because the answer is 286. Not sure how to do it, but need a way to reduce searches when n= 15 -- is there a way of doing this given the problem? – Shanemeister Apr 3 '18 at 15:37
• @Shanemeister DFS is naturally implemented recursively. Here I start with small candidates and build them up right to left (ones, tens, hundreds, etc.) See my edit for ideas to make more efficient – qwr Apr 3 '18 at 16:28
• @Shanemeister afaik binary search requires some notion of sorting and we can't (easily) tell how close we are to a square number. – qwr Apr 3 '18 at 16:29