Re: [obm-l] Sequencia de numeros compostos

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Da Eureka 18, página 61:

Você sabia…
Que existem infinitos inteiros positivos ímpares k tais que k.2^n+1 é composto
para todo n ? Tais inteiros k são chamados números de Sierpinski. Em 1962,
John Selfridge provou que 78557 é um número de Sierpinski, e conjectura-se
que seja o menor deles. Atualmente há 11 números menores que 78557 sobre os
quais não se sabe se são números de Sierpinski ou não: 4847, 10223, 19249,
21181, 22699, 24737, 27653, 28433, 33661, 55459 e 67607. O número 5359 fazia
parte dessa lista até 6/12/2003, quando Randy Sundquist ( um participante do
Seventeen or Bust, um projeto distribuído para atacar o problema de
Sierpinski) encontrou o primo 5359.2^5054502+1 , que tem 1521561 dígitos e é o quarto maior
primo conhecido, e maior primo conhecido que não é de Merssenne. 
Veja: http://www.seventeenorbust.com para mais informações.

Exercício: Prove que 78557 é um número de Sierpinski, e que existem
infinitos números de Sierpinski a partir das congruências
78557.2^0+1=0 (mod 3)
78557.2^1+1=0 (mod 5)
78557.2^7+1=0 (mod 7)
78557.2^11+1=0 (mod 13)
78557.2^3+1=78557.2^39+1=0 (mod 73)
78557.2^15+1=0 (mod 19)
78557.2^27+1=0 (mod 37).


   Abraços,
              Gugu

P.S.: Agora so' faltam 10: em 30/12/2004 foi achado o primo 
28433.2^7830457+1, tirando o 28433 da lista acima.

>
>on 02.10.04 21:13, Qwert Smith at lord_qwert@hotmail.com wrote:
>
>> 
>> 
>> 
>>> From: Claudio Buffara <claudio.buffara@terra.com.br>
>>> 
>>> on 02.10.04 12:05, Qwert Smith at lord_qwert@hotmail.com wrote:
>>> 
>>>> 
>>>>> From: Claudio Buffara <claudio.buffara@terra.com.br>
>>>>> 
>>>>> 
>>>>> E o caso de k*2^n + 1? Para que valor de k isso eh sempre composto?
>>>>> 
>>>> 
>>>> Vou escrever so a solucao pro Super Buffara ver se confere...
>>>> o raciocinio escrevo assim ki tiver tempo
>>>> 
>>>> para k*2^n + 1 basta k=[(3*5*11*17)*t + 1] ou
>>>> k= 2805*t + 1 com t inteiro > 0
>>>> 
>>> Boa tentativa, mas 2806*2^8+1 = 718337 eh primo.
>>> Por acaso voce usou o TCR?
>>> 
>>> []s,
>>> Claudio.
>>> 
>> 
>> Poxa, foi uma bobeira que nao sei explicar...
>Nesse caso, use a explicacao padrao: era um teste pra ver se as pessoas
>estavem prestando atencao...
>
>> olhando de volta
>> no guardanapo onde tinha escrito isso as potencias de 2 eram
>> 2, 4, 8, 16, 32, 64, 128, 516 (acho ki embolei 256 e 512)
>Ja vi piores aqui na lista. Por exemplo, o meu 14 == -1 (mod 13).
>
>> Agora... se 2^8 fosse 516 tinha matado o problema :).
>> Nao usei TCR nao, quer dizer acho ki nao
>> pelo menos diretamente...fiz meio que reinventando a roda.
>> Infelizmente nao conheco a terminologia matematica suficiente
>> pra classificar o metodo. Mas vou descrever e vc me diz o que
>> que e.  Comecei com a mesma ideia dos outros problemas
>> identificar um m onde 2^n = -1 (mod m) pra qualquer n.
>> Como eh impossivel passei ao plano B. Idetinficar alguns 'm's
>> 2^n = -1 (mod m) para parte dos 'n's. Isso na minha opniao eh
>> uma aplicacao abaianada (com todo respeito) do TCR.
>Possivelmente.
>
>> Dividi on 'n's em 4 conjuntos: [4t], [4t+1], [4t+2] e [4t+3]
>> Se existir um grupo finito de 'm's onde 2^n = -1 (mod m_i) em
>> todos os casos acima entao k = m_1*m_2*...*m_i + 1.
>> 
>> O '11' da minha resposta foi baseado na lambanca anterior de
>> 2^8 = 516 = -1 (mod 11).  Agora estou em duvida se da pra
>> achar finitos 'm's.  O problema sao os casos onde n eh potencia
>> de 2.  Um dia vou aprender matematica e ai vcs vao ver so :).
>> Mas espera sentado viu?
>>
>Esse eh um teorema provado por Sierpinski: existem infinitos impares k tais
>que k*2^n + 1 eh composto. Conjectura-se que o menor k com essa propriedade
>eh 78557 = 17*4621. De uma olhada em: http://www.prothsearch.net/sierp.html
>
>[]s,
>Claudio.
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================
>

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================