Mejorar el algoritmo para encontrar un cuadrado perfecto específico en un rango de dos enteros muy grandes $(10^{28})$

Question

Supongamos que nos dan un conjunto de dígitos que representan cada uno de los otros dígitos de un cuadrado perfecto, ¿cómo podemos encontrar la raíz de un número que tenga el mismo patrón, cuya existencia está garantizada y es única?

Por ejemplo, $8*7*6$ si se sustituyen los asteriscos por todos $0$ 's y todos $9$ 's usted tendría $89796$ y $80706$ . Si se toma el cuadrado de cada uno, se obtiene $299$ y $284$ (redondeando a un número entero). A continuación, puede iterar a través de cada número entero de $284$ , a $299$ , cuadrarlos, hasta encontrar un número que coincida con el mismo patrón. Resulta que la respuesta es $286^2$ que es igual a $81796$ .

También sabemos que con el dígito de las unidades es un $6$ que los dos primeros dígitos se limitan a un conjunto de números, siendo 96 uno de ellos. Así que sólo con saber que el último dígito es $6$ una solución parcial podría ser $8*796$ pero también podría ser $8*744$ . En cualquier caso, hay muy pocas opciones y el conjunto de resultados se reduce. Sólo con aplicar $0-9$ a $8*796$ Si se itera a través de ellos, se tropezará con 81796 con una raíz cuadrada de $286$ .

Si el problema se limitara a cuadrados perfectos con números relativamente pequeños, la solución sería sencilla: basta con encontrar las raíces máximas y mínimas $(284-299)$ y encontrar los cuadrados perfectos que satisfagan el patrón de $8*7*6$ por ejemplo. Otro ejemplo es $1*2*3*4$ donde la raíz cuadrada es $1312^2 = 1721344$ .

Sin embargo, utilizando este algoritmo, mi programa tarda una eternidad en ejecutarse con números enteros muy grandes. Parece que habría una forma de construir el cuadrado aplicando las propiedades del cuadrado perfecto, o aplicando otro algoritmo que reduzca las posibilidades.

EDITADO: Los ejemplos más grandes son: $23209192748299230494155021081$ que es un cuadrado perfecto y su raíz es: $152345635803259$ . Los números proporcionados son: $229978920915201$ que, utilizando el ejemplo anterior: $2*2*9*9*7*8*9*2*0*9*1*5*2*0*1$ con los asteriscos como marcador de un dígito. Otro ejemplo: $232091909800969$ es el cuadrado perfecto, y la raíz cuadrada es: $15234563$ . Los números proporcionados son: $22999099$ significado: $2*2*9*9*9*0*9*9$ con los asteriscos como marcadores de posición. El algoritmo que detallé anteriormente (encontrar las raíces mínimas y máximas, elevar al cuadrado y comparar) funciona bien para el cuadrado perfecto: $232091909800969$ pero no en el cuadrado perfecto: $23209192748299230494155021081$ -- tarda demasiado.

Espero que esto tenga sentido.

Editado: El siguiente es el código que he utilizado. Es Python 3.6.3 corriendo en un 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

El problema con su algoritmo es que está explorando el espacio de búsqueda de manera muy ineficiente. Este tipo de problema es fácilmente susceptible de una búsqueda en profundidad, empezando por los dígitos más bajos y comprobando si son posibles.

Por ejemplo, si su número cuadrado termina en $0*1$ sólo hay un número relativamente pequeño de números de 3 dígitos en los que puede terminar tu raíz: $011, 021, 031, \dots, 241, 321, 491, 501, \dots$

Esta es la idea aproximada que hace el n=10 caso en 2 segundos. Es muy ineficiente ya que para el último $d$ dígitos de $x$ sólo comprobamos el último $d$ dígitos de $x^2$ . La función de comprobación de validez realiza muchos cálculos repetidos, y el código tampoco maneja la adición de ceros de forma eficiente.

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