Il modo più veloce per filtrare la sequenza A010784

Question

La sequenza A010784 in OEIS è la sequenza contenente solo numeri con cifre distinte. Questa è una quantità finita.

Quello che ho cercato di fare è trovare diversi numeri in questa sequenza con determinati attributi.
Ad esempio: 6 è un numero distinto di magnitudine 10. Può essere trovato come segue:

• 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 (due sei; queste non sono entrambe cifre distinte)

Ora sto cercando i numeri più alti disponibili per diverse grandezze di ordine.
Diciamo tutti gli ordini da 1 a 20.

Quello che sto facendo attualmente è un ciclo dal numero distinto più alto possibile, che è 9.876.543.210 e il numero univoco più alto di magnitudine 1, fino a un numero molto basso.
Questo metodo sembra estremamente inefficiente. Almeno per me sì.

Sono abbastanza sicuro che mi mancano alcune cose sul factoring che dovrebbero essere in grado di rendere le cose molto più veloci.

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

Certo che c'è un modo migliore. Dovresti costruire i numeri dal basso verso l'alto, cioè se un numero a1 ... ak (queste sono k cifre) non è di grandezza N in modo che una cifra appaia due volte entro le prime k cifre del risultato per ogni moltiplicando 2..N allora nessuno dei due è un numero b1 ... bm a1 ... ak. Ciò fornisce una procedura di enumerazione ricorsiva categoricamente più veloce perché riduce una quantità esponenziale di spazio di ricerca. Dettagli lasciati come esercizio a OP.

Spiegazione più lunga:

Supponiamo che esista una procedura

 magnitude(number_str)

che calcola la grandezza per il numero number_str rappresentato in base 10, in modo che la procedura restituisca 0 se number_str contiene almeno una doppia occorrenza di una cifra, 1 se number_str ha ogni cifra distinta ma moltiplicando il numero per due si ottiene una cifra che ricorre più volte, ecc.

Questa procedura può essere implementata in termini di un'altra

 unique_digits(number_str)

che restituisce true se tutte le cifre in number_str sono univoche, altrimenti false.

Ora quindi magnitude può essere implementato come

 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

Ora questa procedura magnitude può essere modificata in un nocarry_magnitude che modifica sottilmente il controllo:

 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

Questa procedura controlla le cifre che ricorrono più volte solo nel numero di cifre più a destra (cifre dell'ordine più basso) del prodotto nel ciclo quante erano le cifre nell'input originale. È necessario un parametro limit per assicurarsi che la procedura termini poiché è possibile che la procedura venga eseguita in un ciclo infinito altrimenti. Chiaramente per ogni stringa s lo contiene

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

Ad esempio, prendi il numero 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

Quello che ho scritto sopra nella breve descrizione è che se

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

quindi per qualsiasi stringa ottenuta mediante postfixing s (denotalo con x + s di seguito), lo mantiene

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

La prima disuguaglianza deriva dall'affermazione di cui sopra e la seconda è evidente dalla definizione di nocarry_magnitude. Nota che magnitudo (x + s) <= magnitudo (s) è un non teorema in generale come esemplificato da

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

causato dal carry. nocarry_magnitude ignora il carry, motivo per cui il suffisso di una stringa ha sempre una grandezza nocarry grande quanto qualsiasi estensione di essa (verso sinistra, cioè cifre di ordine superiore).

Ora puoi scrivere una procedura ricorsiva significativamente più veloce come questa per cercare numeri con magnitudo almeno 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("")

Ecco un'implementazione completa di Python (cercando la magnitudine 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("")

Ed ecco una corsa che richiede meno di un secondo; questo trova la risposta "27" che sembra essere il numero univoco che fornisce la magnitudine record 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

Non è solo un problema di permutazione?Per una data grandezza M fai 10 cm.

Ad esempio, di magnitudine 2, quanti modi ci sono per scegliere 2 cifre da 0 a 9?(In realtà, dovrebbe essere uno da 1..9 e uno da 0..9 dove la seconda cifra non corrisponde alla prima.)

Certamente non è necessario esaminarli tutti e controllarli.Basta impostare un set e sceglierne uno, quindi sceglierne un altro.Meglio ancora, creali da zero.Prima fai tutto ciò che inizia con 1 (10, 12, 13, 14, ecc.) Poi tutto ciò che inizia con 2, ecc.

Answer 3

Hai due problemi:

1) Iterando sulla sequenza A010784.

Usa itertools.permutations per generare numeri possibili successivi.

2) Calcolo della grandezza di un numero.

Puoi determinare se un numero ha solo cifre univoche con questo snippet di codice:

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

Answer 4

Puoi tagliare alcuni rami se stai solo cercando i numeri più alti.Da 6 x 11 = 66 sai anche che la magnitudine 11 è al massimo 5. Una volta che conosci un numero più alto con una magnitudine>= 5 puoi saltare 11.