Maneira mais rápida de filtrar a sequência A010784

Question

A sequência A010784 no OEIS é a sequência que contém apenas números com dígitos distintos. Este é um valor finito.

O que venho tentando fazer é encontrar vários números nesta sequência com determinados atributos.
Por exemplo: 6 é um número distinto de magnitude 10. Isso pode ser encontrado da seguinte forma:

• 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 (dois seis; não são dois dígitos distintos.)

Agora estou tentando os números mais altos disponíveis para várias magnitudes de ordem.
Digamos que todos os pedidos de 1 a 20.

No momento, estou fazendo um loop desde o maior número distinto possível, que é 9.876.543.210 e o maior número exclusivo de magnitude 1, até um número muito baixo.
Este método parece extremamente ineficiente. Pelo menos para mim sim.

Tenho certeza de que estou perdendo algumas coisas sobre fatoração que devem tornar as coisas muito mais 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

Claro que existe uma maneira melhor. Você deve construir os números de baixo para cima, ou seja, se um número a1 ... ak (estes são k dígitos) não for de magnitude N, de modo que um dígito apareça duas vezes dentro dos primeiros k dígitos do resultado para qualquer multiplicando 2..N então nem é qualquer número b1 ... bm a1 ... ak. Isso fornece um procedimento de enumeração recursiva categoricamente mais rápido porque elimina uma quantidade exponencial de espaço de pesquisa. Detalhes deixados como um exercício para o OP.

Explicação mais longa:

Suponha que haja um procedimento

 magnitude(number_str)

que calcula a magnitude do número number_str representado na base 10, de modo que o procedimento retorne 0 se number_str contiver pelo menos uma ocorrência dupla de um dígito, 1 se number_str tiver cada dígito distinto, mas multiplicar o número por dois resulta em um dígito ocorrendo várias vezes, etc.

Este procedimento pode ser implementado em termos de outro

 unique_digits(number_str)

que retorna verdadeiro se todos os dígitos em number_str forem únicos; caso contrário, é falso.

Agora, magnitude pode ser implementado 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

Agora, este procedimento magnitude pode ser alterado para um nocarry_magnitude que altera a verificação 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 procedimento verifica os dígitos que ocorrem várias vezes apenas nos dígitos mais à direita (dígitos de ordem mais baixa) do produto no loop, pois havia dígitos na entrada original. Um parâmetro limite é necessário para garantir que o procedimento termine, pois é possível que o procedimento seja executado em um loop infinito de outra forma. Claramente, para qualquer string s, ele mantém que

 magnitude(s) <= nocarry_magnitude(s, M) for large M

Por exemplo, pegue o 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

O que escrevi acima na breve descrição é que se

 nocarry_magnitude(s, x) == k     for x > k

então, para qualquer string obtida por postfixing s (denote isso por x + s abaixo), ele mantém que

 x : string of digits
 magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
 when m >= magnitude(x + s)

A primeira desigualdade vem da afirmação acima e a segunda é óbvia da definição de nocarry_magnitude. Observe que magnitude (x + s) <= magnitude (s) é um não-teorema em geral, conforme exemplificado por

 magnitude( "56")  = 1  // 56 * 2 = 112
 magnitude("256")  = 12 // the first duplicate occurs at 3328

que é causado pelo transporte. nocarry_magnitude ignora o transporte, e é por isso que o sufixo de uma string tem sempre a magnitude de nocarry tão grande quanto qualquer extensão dela (para a esquerda, ou seja, dígitos de ordem superior).

Agora você pode escrever um procedimento recursivo significativamente mais rápido como este para pesquisar números com magnitude pelo 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("")

Aqui está uma implementação Python completa (pesquisando magnitude 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("")

E aqui está uma corrida que leva menos de um segundo; isso encontra a resposta '27', que parece ser o número único que fornece a magnitude recorde de 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

Isso não é apenas um problema de permutação?Para uma dada magnitude, M, você faz 10cM.

Por exemplo, de magnitude 2, quantas maneiras existem para escolher 2 dígitos de 0 a 9?(Na verdade, deve ser um de 1 a 9 e um de 0 a 9, onde o segundo dígito não corresponde ao primeiro.)

Você certamente não precisa passar por todos eles e verificá-los.Basta configurar um conjunto e escolher um, depois escolher outro.Melhor ainda, basta criá-los do zero.Primeiro faça tudo que começa com 1 (10, 12, 13, 14, etc), depois tudo que começa com 2, etc.

Answer 3

Você tem dois problemas:

1) Iterando sobre a sequência A010784.

Use itertools.permutations para gerar números possíveis sucessivos.

2) Calculando a magnitude de um número.

Você pode determinar se um número tem apenas dígitos únicos com este snippet de código:

def unique_num(x):
    return len(str(x)) == len(set(str(x))

Answer 4

Você pode cortar alguns galhos se estiver apenas procurando os números mais altos.Com 6 x 11 = 66, você também sabe que a magnitude de 11 é no máximo 5. Depois de saber um número maior com uma magnitude>= 5, você pode pular 11.