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

Question

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)

Answer 1

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