Homepage

196 E OUTROS NÚMEROS LYCHREL

Random Dizer

Site Links

Bem-vindo à p196.org!

De um dos e-mails de Jason:

Estou muito curioso. Eu lembro que eu li em algum lugar que, de todos os números em 5000 ou algo assim, todos os números caíram em um dos 3 sementes (eu assumo um de 196, 879 ou 1997 - a partir dos números acima deste e-mail), e eu não podia t 'acreditar. Gostaria de ter assumido que haveria 100 é um deles. Foi muito intrigante que todos eles caíram em 3. Ele faz parecer que há algo muito especial com os números - que todos os outros que não se palíndromos cair em um deles - se não, tornam-se palíndromos! Poderia ajudar a fornecer dados para provar, de uma vez por todas, que 196 nunca vai resolver fora!

Lychrel Numbers and Palindromes

Pessoalmente, eu ficaria triste de encontrar uma prova de que 196 não tem solução palíndromo. Eu passei muito tempo em que número e.... Bem.... Você entende.

Por outro lado, eu gostaria de encontrar algo em comum com os números que não têm solução palíndromo! É por isso que eu decidi que é preciso haver uma lista deles em algum lugar. Assim que as pessoas podem olhar para eles, poke-los com uma vara, e geralmente só dar-lhes um pouco do pensamento. Há um traço comum entre eles? Sabemos que 196 é o menor, o que é a maior que conhecemos? (Infinity não conta. Eu já decidiram que a Infinity em si deve ser um palíndromo. :-))

Jason, Istvan e eu conversamos sobre esses números. A seguir estão algumas das notas que eu compilei a partir das discussões, bem como a melhor abordagem provável eficiente procura para os próximos Lychrel maior número... A primeira metade do trabalho a seguir pode ser creditado à Jason Doucette. Istvan é quem explicou-me, mas eu acredito que ele estava explicando que Jason já havia feito de forma eficiente para busca em seu trabalho Palindrome Longest atrasadas. Eu tentei reescrevê-lo, simplesmente, de modo que pessoas como eu podia entender, com um pouco de reflexão. Acho que a maioria da segunda etapa é um trabalho Istvan e idéias. (Às vezes é difícil lembrar que o que contribuiu, e garantir que eles são reconhecidos!) Duvido que acrescentou muito à discussão..... :-(

Seria fácil o suficiente para começar com uma lista de todos os números entre os dois pontos indicados. Diga, 0-1,000,000.

O primeiro passo óbvio para mim, seria a de percorrer a lista e exclua todos os números que já são palíndromos. Isso vai eliminar um monte de números desde o início.

Uma das primeiras coisas que devemos fazer é encontrar e eliminar todos os números que se seguirão a mesma linha, a longo prazo. Por exemplo, 196, 295, 394, 493, 592, 691 será toda forma 887 na primeira iteração, e, em seguida, depois de tudo isso será idêntica para todos os seis números. Direito fora do bastão, teríamos um monte de redundância de tempo de computação, se não eliminar, os outros números de 196. A economia de tempo seria substancial!

Então iríamos realizar 1 iteração de cada um desses números, descobrir que todos eles levam a 887, em seguida, excluir 295, 394, 493, 592 e 691 da nossa lista.

Deste ponto de vista, nós temos que examinar os pares correspondentes dígitos, o primeiro eo último, o segundo eo último de menos, o terceiro e último 2 etc menos Sempre que estes pares de números dão a mesma quantia, o inversão / aditamento procedimento irá produzir o mesmo resultado.

Há 18 pares de dígitos exterior o que resultará em montantes diferentes.

Dez primeiros:
1xx0
1xx1
1xx2
...
1xx8
1xx9
E os oito seguintes:
2x... x9
3x... x9
4x... x9
5x... x9
6x... x9
7x... x9
8x... x9
9x... x9

Qualquer outra combinação irá resultar em um número duplicado após a primeira iteração.

Em seguida, existem 19 pares de dígitos interior (porque, neste caso, permitir que o primeiro dos dois a zero).

x0xx...
xx0x x0xx...
xx1x x0xx...
xx2x x0xx...
xx3x etc

Isto irá funcionar para todos os números, mesmo dígito. Se o número a ser examinado tem um número ímpar de dígitos, deve-se multiplicar por dez, por causa do dígito no meio:


xxx0xxx
xxx1xxx ...

xxx9xxx

Como você pode ver, para calcular, por exemplo, quantas iterações são necessárias para verificar todos os números de 7 dígitos que diferem nos montantes par de dígitos, devemos multiplicar os coeficientes:

18 * 19 ^ 2 * 10 = 64.980 iterações (em vez de 9000000)

18 é para o par externo de dígitos, 10 é para o meio de dígitos, 19 ^ 2 é para os dois pares interior. Você pode ver o quanto mais rápido de pesquisa isto seria, a longo prazo.

Podemos até construir uma fórmula geral para calcular a quantidade de números a serem verificados:

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

n é o comprimento da peça, e deve ser maior que 1. A parte 10 ^ (n mod 2) dá 10 para comprimentos ímpar, 1 para comprimentos mesmo.

A tabela a seguir pode ajudar a demonstrar:

NOTA: Isso não é completa. É apenas um exemplo do que teria de ser feita para verificar os números entre os dígitos 3 e 17.

número de dígitos Dígitos Total Números a ser verificado Ratio Cada Nth a ser verificado
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SUM :
900
9000
90.000
900.000
9.000.000
90.000.000
900000000
9000000000
90000000000
900000000000
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
3420
6498
64.980
123.462
1.234.620
2.345.778
23.457.780
44.569.782
445697820
846825858
8468258580
16089691302
160896913020
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
3836
3836
20.193
20.193
106.279
106.279
559.364
559.364
535.276

Então, se nós estamos indo somente os números de pesquisa entre 3 e 17 dígitos, existem 186.819.193.422 números que devem ser verificados, a fim de verificar apenas uma conseqüência de cada segmento.

Segundo passo: filtrar os números independentes Seed

.

A próxima coisa a fazer seria a de começar a reverter adicionar o processo para cada um dos restantes números, e eliminar os números de upstream para cada um. Por exemplo, se estivéssemos indo a 9 dígitos, 887 / 7436 / 13783 / 52514 / 94039 / 187088 / 1067869 / 10755470 / 18211171 / 35322452 / 60744805 / 111589511 / 227574622 / 454050344 e 897100798 todos teriam que ser removidos da lista, uma vez que estão todos na discussão 196. Ao mesmo tempo, todos os números que levam a um palíndromo, serão apagados. Por exemplo, 89, 187, 968, 1837,... 8.813.200.023.188 tudo seria excluído, uma vez que 89 será um palíndromo em 24 iterações.

Quando você está acabado, nada deixou em sua lista, deve ser um número de sementes......

Admito que esta não é a única forma de busca para estes números. Pode não ser o mais fácil de programar. Não poderia ser em qualquer lugar perto o caminho mais rápido para encontrar esses números. Mas é um caminho que parece o som.