Dado un subconjunto de dígitos no vacío, ¿cómo puede calcular eficientemente los números cuyos cuadrados solo tienen dígitos en el subconjunto dado?

Answer 1

Parece mucho más rápido generar cuadrados y verificar si usan los dígitos especificados en lugar de generar números y ver si son cuadrados. Hay [matemáticas] 6 ^ N [/ matemáticas] números de 6 dígitos de su conjunto de N, pero solo [matemáticas] \ sqrt {1000000} = 1000 [/ matemáticas] cuadrados de hasta 6 dígitos.

Algunos trucos adicionales, para ayudar a filtrar qué cuadrados verificar, provienen de residuos cuadráticos. (Consulte ¿Qué son los residuos cuadráticos y por qué son importantes?)

Si tomamos cualquier mod cuadrado 10, entonces el resultado (el último dígito) será uno de 0, 1, 4, 5, 6 o 9. Pero obtenemos un poco más que eso: un valor particular de N mod 10 siempre se asigna al mismo mod cuadrado 10, es decir

0-> 0
1-> 1
2-> 4
3-> 9
4-> 6
5-> 5
6-> 6
7-> 9
8-> 4
9-> 1

Si su conjunto no incluye el número ‘6’, puede omitir la cuadratura de cualquier número que sea congruente con 4 o 6 mod 10, ¡una reducción del 20%! Lo mismo podría hacerse con los residuos cuadráticos mod 100 o mod 1000.

La forma de aprovechar esto es no recorrer los números y probar cada uno con el filtro de residuos cuadráticos. (Eso requeriría una operación de módulo para cada número en el rango, básicamente el mismo costo que calcular el primer dígito del resultado, y de todos modos se pueden eliminar muchos números en el primer o segundo dígito). En cambio, después de decidirse por una tabla de búsqueda tamaño, lo mejor es probablemente identificar los residuos válidos y recorrer en incrementos del tamaño de la tabla.

Por ejemplo, si tiene dígitos válidos {2,3,4,5}, utilizando la tabla anterior solo queremos probar números que sean congruentes con 2 o 5 mod 10. Cuente por 10 para obtener:

2
5 5
10 + 2
10 + 5
20 + 2
20 + 5

que es mucho más rápido que generar todos los números del 1 al 25 y tirar la mayoría de ellos. Cuadre cada uno de estos y verifique los dígitos (y tenga en cuenta que no tiene que verificar el dígito de uno ya que ya garantizó que era correcto).

Sin embargo, no he resuelto cuáles son las consideraciones sobre el mejor tamaño de tabla. Generar una nueva tabla para cada potencia de 10 parece que no sería una victoria (aunque podría serlo), y las tablas muy grandes no cabrían en el caché de primer nivel y podrían ralentizarlo demasiado en comparación con hacer más CPU -Sólo trabajo.