Homepage

196 E ALTRI NUMERI LYCHREL

Casuale Quota

Site Links

Benvenuti a p196.org!

Da uno dei messaggi di posta elettronica di Jason:

Sono molto curioso. Mi ricordo che ho letto da qualche parte che su tutti i numeri sotto 5.000 o qualcosa del genere, tutti i numeri cadde in uno dei 3 semi (suppongo uno di 196, 879, o 1997 - dai numeri sopra a questa e-mail), e non potrei 't credere. Avrei assunto ci sarebbe 100 di loro. E 'stato molto interessante il fatto che tutti caddero in 3. Si fa sembrare che ci sia qualcosa di molto speciale con i numeri - che tutti gli altri che non diventino palindromi rientrano in una di loro - se non, diventano palindromi! Si potrebbe contribuire a fornire dati per dimostrare, una volta per tutte, che 196 non potrà mai risolvere fuori!

Lychrel Numbers and Palindromes

Personalmente, sarei triste per trovare una prova che 196 non ha alcuna soluzione palindromo. Ho speso un sacco di tempo su quel numero, e... Bene... Ti capisco.

D'altra parte, mi piacerebbe trovare qualcosa di comune per i numeri che non hanno soluzione palindromo! Questo è il motivo per cui ho deciso che ci deve essere un elenco di loro da qualche parte. Così che la gente può guardare a loro, poke con un bastone, e in generale dare loro un po 'di pensiero. Esiste una comunanza tra di loro? Sappiamo che 196 è il più piccolo, quello che è il più grande che conosciamo? (Infinity non conta. Ho già deciso che Infinity stessa deve essere un palindromo. :-))

Jason, Istvan e ho parlato di questi numeri. I seguenti sono alcuni degli appunti che ho compilato dal dibattito, così come l'approccio migliore per probabile efficiente alla ricerca del prossimo grande Lychrel Numero... La prima metà dei lavori di seguito possono essere accreditate Jason Doucette. Istvan è colui che mi ha spiegato, ma credo che stava spiegando ciò che Jason aveva già fatto per la ricerca in modo efficiente nel suo lavoro ritardato Palindrome più lunga. Ho provato a riscrivere in modo semplice, in modo che persone come me poteva capire, con un piccolo pensiero. Penso che la maggior parte della seconda fase è il lavoro di Istvan e idee. (A volte è difficile da ricordare coloro che hanno contribuito cosa, e assicurare che siano riconosciuti!) Dubito che ho aggiunto molto alla discussione.... :-(

Sarebbe abbastanza facile cominciare con un elenco di ogni numero compreso tra due punti dati. Dire, 0-1,000,000.

Il primo passo ovvio per me, sarebbe quello di passare attraverso la lista e cancellare tutti i numeri che sono già palindromi. Ciò eliminerà una serie di numeri da subito.

Una delle prime cose che dobbiamo fare è trovare ed eliminare tutti i numeri che seguiranno lo stesso thread nel lungo periodo. Ad esempio, 196, 295, 394, 493, 592, 691 saranno tutti modulo 887 alla prima iterazione, e poi tutto dopo che sarà identico per tutti i 6 numeri. Diritto al largo della mazza, avremmo un sacco di ridondanza di tempo di calcolo, se non eliminare gli altri numeri di 196. Il risparmio di tempo sarebbe notevole!

Così avremmo eseguire 1 iterazione di ciascuno di questi numeri, scoprono di condurre tutti a 887, quindi eliminare 295, 394, 493, 592, e 691 dalla nostra lista.

Da questo punto di vista, dobbiamo esaminare le coppie di cifre, la prima e l'ultima, la seconda e l'ultima meno, il terzo ed ultimo meno 2 ecc Ogni volta che queste coppie numero di dare la stessa somma, il inversione / procedura Inoltre produrrà lo stesso risultato.

Ci sono 18 coppie esterno cifra che si tradurrà in somme diverse.

Primi dieci:
1xx0
1xx1
1xx2
...
1xx8
1xx9
E le seguenti otto:
2x... x9
3x... x9
4x... x9
5x... x9
6x... x9
7x... x9
8x... x9
9x... x9

a qualsiasi altra combinazione si tradurrà in un duplicato numero dopo la prima iterazione.

Ora ci sono 19 coppie di cifre interiore (perché in questo caso lasciamo il primo dei due a zero).

x0xx...
xx0x x0xx...
xx1x x0xx...
xx2x x0xx...
xx3x ecc

Questo funziona per tutti i numeri anche cifre. Se il numero da esaminare è un numero dispari di cifre, dobbiamo moltiplicare per dieci, a causa delle cifre in mezzo:

xxx0xxx
xxx1xxx
...
xxx9xxx

Come si può vedere, di calcolare, per esempio, come molte iterazioni sono necessarie per controllare tutti questi 7 numeri a due cifre che si differenziano per gli importi coppia di cifre, dobbiamo moltiplicare tali coefficienti:

18 * 19 ^ 2 * 10 = 64.980 iterazioni (invece di 9.000.000)

18 è per la coppia esterna di cifre, 10 è per la metà cifra, 19 ^ 2 è per le due coppie interne. Si può vedere come molto più veloce questa ricerca sarebbe nel lungo periodo.

Possiamo anche costruire una formula generale per calcolare il numero di numeri da verificare:

18 * 19 ^ ((n-2) div 2) * 10 ^ (n mod 2)

n

è la lunghezza del numero, e deve essere maggiore di 1. La parte 10 ^ (n mod 2) fornisce 10 per lunghezze dispari, 1 per lunghezze pari.

La seguente tabella può aiutare a dimostrare:

NOTA: Questo non è completa. E 'solo un esempio di cosa dovrebbe essere fatto per verificare i numeri di cifre tra 3 e 17.

Numero di cifre Totale Cifre numeri da controllare Ratio Ogni ennesimo da controllare
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SUM:
900
9.000
90.000
900.000
9.000.000
90.000.000
900.000.000
9.000 milioni
90 miliardi
900.000.000.000
9.000.000.000.000
90.000.000.000.000
900.000.000.000.000
9.000.000.000.000.000
90.000.000.000.000.000
99.999.999.999.999.900
180
342
3.420
6.498
64.980
123.462
1.234.620
2.345.778
23.457.780
44.569.782
445.697.820
846.825.858
8.468.258,58 mila
16.089.691,302 mila
160.896.913.020
186.819.193.422
20.000000%
3.800000%
3.800000%
0.722000%
0.722000%
0.137180%
0.137180%
0.026064%
0.026064%
0.004952%
0.004952%
0.000941%
0.000941%
0.000179%
0.000179%
0.000187%
5
26
26
138
138
728
728
3.836
3.836
20.193
20.193
106.279
106.279
559.364
559.364
535.276

Quindi, se prendiamo in considerazione soltanto i numeri di ricerca tra i 3 ei 17 cifre, ci sono 186.819.193.422 numeri che devono essere controllati per verificare una sola conseguenza di ogni thread.

Secondo passo: il filtraggio dei numeri indipendente Seed

.

La prossima cosa da fare sarebbe quella di iniziare la retromarcia / add processo per ognuno dei restanti numeri ed eliminare i numeri a monte per ciascuno. Per esempio, se dovessimo andare a 9 cifre, 887 / 7.436 / 13.783 / 52.514 / 94.039 / 187.088 / 1.067.869 / 10.755.470 / 18.211.171 / 35.322.452 / 60.744.805 / 111.589.511 / 227.574.622 / 454.050.344 e 897.100.798 sarebbero tutti devono essere rimossi dalla lista, dal momento che sono tutti nel thread 196. Allo stesso tempo, tutti i numeri che portano ad un palindromo, saranno cancellati. Ad esempio, 89, 187, 968, 1837,... 8.813.200.023.188 sarebbero stati tutti eliminati, dal 89 diventerà un palindromo in 24 iterazioni.

Quando avete finito, nulla lasciato sulla vostra lista, dovrebbe essere un numero di semi.....

Devo ammettere che questa non è l'unico modo per la ricerca di questi numeri. Potrebbe non essere il più facile da programmare. Potrebbe non essere da nessuna parte vicino il modo più veloce per trovare questi numeri. Ma è un modo che sembra il suono.