La forma más rápida de filtrar la secuencia A010784

Question

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

Answer 1

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

Answer 2

¿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.

Answer 3

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

Answer 4

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.