La forma más rápida de filtrar la secuencia A010784
Pregunta
La secuencia A010784 en OEIS es la secuencia que contiene solo números con dígitos distintos.Esta es una cantidad finita.
Lo que he estado intentando hacer es encontrar varios números en esta secuencia con ciertos atributos.
P.ej:6 es un número distinto de magnitud 10.Esto se puede encontrar de la siguiente manera:
- 6 x 1 = 6
- 6 x 2 = 12
- 6 x 3 = 18
- 6 x 4 = 24
- 6 x 5 = 30
- 6 x 6 = 36
- 6 x 7 = 42
- 6 x 8 = 48
- 6 x 9 = 54
- 6 x 10 = 60
- 6 x 11 = 66 (Dos seises;ambos no son dígitos distintos.)
Ahora estoy probando los números más altos disponibles para varias magnitudes de orden.
Digamos todos los pedidos del 1 al 20.
Lo que estoy haciendo actualmente es recorrer desde el número distinto más alto posible, que es 9.876.543.210 y el número único más alto de magnitud 1, hasta un número muy bajo.
Este método se siente extremadamente ineficiente.Al menos, para mí lo es.
Estoy bastante seguro de que me faltan algunas cosas sobre factorización que deberían poder hacer las cosas mucho más rápidas.
def unique_num(num):
# Check whether number is unique.
return Boolean
def unique_num_magnitude(num):
# Check of which magnitude the unique number is
return Integer
# Dictionary with the current highest values
# for each magnitude.
values = {1: 987654321...}
# Set limits
upper_limit = 9876543210
lower_limit = 1
for numbers in range(upper_limit, lower_limit, -1):
unique = unique_num(num) # Boolean
if (unique):
magnitude = unique_num_magnitude(num)
if (values[magnitude] < num):
values[magnitude] = num
Solución
Seguro que hay una mejor manera.Debes construir los números de abajo hacia arriba, es decir.si un número a1...ak (estos son k dígitos) no es de magnitud N, de modo que un dígito aparece dos veces dentro de los primeros k dígitos del resultado para cualquier multiplicando 2..N, entonces tampoco lo es ningún número b1...bm. a1...ak.Esto proporciona un procedimiento de enumeración recursivo categóricamente más rápido porque reduce una cantidad exponencial de espacio de búsqueda.Los detalles se dejan como ejercicio para OP.
Explicación más larga:
Supongamos que existe un procedimiento
magnitude(number_str)
que calcula la magnitud del número number_str
representado en base 10, de modo que el procedimiento devuelve 0 si number_str
contiene al menos una aparición doble de un dígito, 1 si number_str
tiene cada dígito distinto, pero multiplicar el número por dos da como resultado un dígito que aparece varias veces, etc.
Este procedimiento puede implementarse en términos de otro
unique_digits(number_str)
que devuelve verdadero si todos los dígitos en number_str
son únicos, de lo contrario falsos.
Ahora bien magnitude
se puede implementar como
magnitude(number_str):
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(int_to_str(k))):
k = k + n
i = i + 1
return i
Ahora esto magnitude
El procedimiento se puede cambiar a un nocarry_magnitude
que cambia el cheque sutilmente:
nocarry_magnitude(number_str, limit):
l = length(number_str)
assert (l > 0)
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(right_substring(int_to_str(k), l))):
k = k + n
i = i + 1
if (i == limit):
break
return i
Este procedimiento comprueba los dígitos que aparecen varias veces solo en tantos dígitos situados más a la derecha (dígitos de orden más bajo) del producto en el bucle como dígitos había en la entrada original.Se necesita un parámetro de límite para garantizar que el procedimiento finalice, ya que de lo contrario es posible que el procedimiento se ejecute en un bucle infinito.Claramente para cualquier cuerda s
sostiene que
magnitude(s) <= nocarry_magnitude(s, M) for large M
Por ejemplo, tomemos el número 19:
19 * 1 = 19
19 * 2 = 38
19 * 3 = 57
19 * 4 = 76
19 * 5 = 95
19 * 6 = 114 // magnitude("19") = 5
19 * 7 = 133 // nocarry_magnitude("19", 100) = 6
Lo que escribí arriba en la breve descripción es que si
nocarry_magnitude(s, x) == k for x > k
luego, para cualquier cadena que se obtenga mediante postfijación s
(denota esto por x + s
abajo), sostiene que
x : string of digits
magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
when m >= magnitude(x + s)
La primera desigualdad proviene de la afirmación anterior y la segunda es obvia de la definición de nocarry_magnitude
.Tenga en cuenta que magnitud (x + s) <= magnitud (s) no es un teorema en general, como lo ejemplifica
magnitude( "56") = 1 // 56 * 2 = 112
magnitude("256") = 12 // the first duplicate occurs at 3328
que es causado por el acarreo. nocarry_magnitude
ignora el acarreo, razón por la cual el sufijo de una cadena siempre tiene una magnitud de no acarreo tan grande como cualquier extensión de la misma (hacia la izquierda, es decir.dígitos de orden superior).
Ahora puedes escribir un procedimiento recursivo significativamente más rápido como este para buscar números con magnitud al menos M:
search(str):
if (str != ""):
int n = nocarry_magnitude(str, M)
if (n < M):
return # the optimization
int k = magnitude(str)
if (k >= M):
store_answer(str)
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + str)
search("")
Aquí hay una implementación completa de Python (buscando magnitud 36):
def unique_digits(s):
r = (len(list(s)) == len(set(s)))
return r
def magnitude(s):
n = int(s)
k = n
assert n > 0
i = 0
while (unique_digits(str(k))):
k = k + n
i = i + 1
return i
def nocarry_magnitude(s, limit):
l = len(s)
assert l > 0
n = int(s)
assert n > 0
k = n
i = 0
while (unique_digits(str(k)[-l:])):
k = k + n
i = i + 1
if (i >= limit):
break
return i
M = 36
def search(s):
if (not(s == "")):
n = nocarry_magnitude(s, M)
if (n < M):
return
k = magnitude(s)
if (k >= M):
print "Answer: %s |" % s,
i = int(s)
k = i
n = 1
while (n <= M):
print k,
k = k + i
n = n + 1
print
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + s)
search("")
Y aquí hay una carrera que dura menos de un segundo;esto encuentra la respuesta '27', que parece ser el único número que proporciona el récord de magnitud 36:
Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
432 459 486 513 540 567 594 621 648 675 702 729 756 783
810 837 864 891 918 945 972
Otros consejos
¿No es esto sólo un problema de permutación?Para una magnitud dada M
¿Haces 10cM?
Por ejemplo, de magnitud 2, ¿cuántas formas hay de elegir 2 dígitos del 0 al 9?(En realidad, debería ser uno de 1..9 y otro de 0..9 donde el segundo dígito no coincide con el primero).
Ciertamente no es necesario que los revise todos y los revise.Simplemente configure un conjunto y elija uno, luego elija otro.Mejor aún, simplemente créelos desde cero.Primero haz todo lo que empiece con 1 (10, 12, 13, 14, etc) luego todo lo que empiece con 2, etc.
Tiene dos problemas:
1) Iterando sobre la secuencia A010784.
Utilice itertools.permutations para generar números posibles sucesivos.
2) Calcular la magnitud de un número.
Puede determinar si un número solo tiene dígitos únicos con este fragmento de código:
def unique_num(x):
return len(str(x)) == len(set(str(x))
Puede cortar algunas ramas si solo busca los números más altos.De 6 x 11 = 66
también sabe que la magnitud de 11 es como máximo 5. Una vez que sepa un número más alto con una magnitud>= 5, puede omitir 11.