[obm-l] Milésimo número primo
Caros Amigos, Na sucessão dos números primos (positivos), qual é o milésimo termo? Existe fórmula para o cálculo direto? Abraços do Ennius Lima. = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Milésimo número primo
2011/11/23 ennius : > Caros Amigos, > > Na sucessão dos números primos (positivos), qual é o milésimo termo? Os números primos são todos positivos. Quanto à sua questão, o maple (ou qualquer outro software) diz: ithprime(1000) -> 7919 (aliás, vale notar que o maple, como os matemáticos atuais, diz que o primeiro número primo é 2) > Existe fórmula para o cálculo direto? A resposta rápida é "não". A resposta longa é: existem algoritmos que permitem calcular todos os números primos menores do que um dado número, mas isso leva bastante tempo (crivo de Eratóstenes). Existem algoritmos que decidem se um dado número é primo ou não (Lucas-Lehmer para alguns, AKS, ...). Existem fórmulas que dão estimativas para o intervalo onde estará o n-ésimo número primo, e que começam em geral com "n*log(n)". http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number O mesmo Maple diz que o 1 000 000ésimo primo é 15 485 863. Usando a fórmula n-ésimo primo >= n log(n) + n log(log(n)) - n, temos que realmente esse número é maior do que 15 441 302.48. Obs: não faço a menor idéia como o maple calcula isso... Ele levou uns 30s para calcular o 17 000 000ésimo primo (= 314 606 869 >=313 837 977.04080 na aproximação), mas vai ficando bm lento depois. > Abraços do Ennius Lima. Abraços, -- Bernardo Freitas Paulo da Costa = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] soluções inteiras não negativas
Meu aluno me pegou... "Quantas são as soluções inteiras não negativas para: 25x + 10y + 5z + w = 37" Saí no braço contando cada quadra de resultados e achei 24. Mas, como pensar sem ter que contar as soluções uma uma? Obrigado Fabio MS
[obm-l] Re: [obm-l] soluções inteiras não negativas
2011/11/23 Fabio Silva > > Meu aluno me pegou... > > "Quantas são as soluções inteiras não negativas para: 25x + 10y + 5z + w = 37" > > Saí no braço contando cada quadra de resultados e achei 24. > > Mas, como pensar sem ter que contar as soluções uma uma? Bom, a primeira coisa a fazer é olhar as divisibilidades. Daí, w = 2 mod 5 (porque o resto é divisível por 5) e daí você tem que resolver 5x + 2y + z = (37 - w)/5. Para cada valor de w, isso dá uma equação com 3 variáveis. Bom, daí você vai "no braço", mas dá pra montar um esqueminha recursivo (que evita "contar tudo", mesmo se no fim das contas é o que você vai acabar fazendo) onde as variáveis "vão entrando" conforme o lado direito aumenta. (37 - w)/5 pode ser 7, 6, 5, 4, 3, 2, 1, 0. Se for 0, tem uma solução apenas(z = 0). Se for 1, idem (z = 1). Se for 2, tem duas soluções (2y + z = 2, tem y=1, z=0 ou z=2) Se for 3, idem (aumente z de um em cada uma). Se for 4, tem 3 soluções. Se for 5, "idem" + 1 solução x = 1 => 4 soluções Se for 6, tem 4 soluções com x=0, mais uma solução com x=1. Se for 7, "idem" para x=0, e dessa vez tem duas soluções com x=1 (repare que isso é igual à 2y + z = 2, e é assim que funciona a recorrência). 1+1+2+2+3+(3+1)+(4+1)+(4+2)=24 Uma outra idéia (que eu acho que dá mais trabalho, para números pequenos como o seu, mas que é mais geral) é montar uma recorrência polinomial dependendo da congruência do lado direito módulo o mmc dos fatores : http://math.stackexchange.com/questions/30638/count-the-number-of-positive-solutions-for-a-linear-diophantine-equation > Obrigado > > Fabio MS Abraços, -- Bernardo Freitas Paulo da Costa = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] RE: [obm-l] Re: [obm-l] Milésimo número primo
Bem... há autores que consideram número primo todo inteiro que tenha somente dois divisores positivos. Ver, por exemplo, Elementos de Álgebra, de Jacy Monteiro. Assim, -2, -3, -5, etc. seriam primos. Abraços do Pedro Chaves! > Date: Wed, 23 Nov 2011 21:37:46 +0100 > Subject: [obm-l] Re: [obm-l] Milésimo número primo > From: bernardo...@gmail.com > To: obm-l@mat.puc-rio.br > > 2011/11/23 ennius : > > Caros Amigos, > > > > Na sucessão dos números primos (positivos), qual é o milésimo termo? > Os números primos são todos positivos. Quanto à sua questão, o maple > (ou qualquer outro software) diz: > > ithprime(1000) -> 7919 > > (aliás, vale notar que o maple, como os matemáticos atuais, diz que o > primeiro número primo é 2) > > > Existe fórmula para o cálculo direto? > A resposta rápida é "não". > > A resposta longa é: existem algoritmos que permitem calcular todos os > números primos menores do que um dado número, mas isso leva bastante > tempo (crivo de Eratóstenes). Existem algoritmos que decidem se um > dado número é primo ou não (Lucas-Lehmer para alguns, AKS, ...). > Existem fórmulas que dão estimativas para o intervalo onde estará o > n-ésimo número primo, e que começam em geral com "n*log(n)". > http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number > > O mesmo Maple diz que o 1 000 000ésimo primo é 15 485 863. Usando a fórmula > n-ésimo primo >= n log(n) + n log(log(n)) - n, temos que realmente > esse número é maior do que 15 441 302.48. Obs: não faço a menor idéia > como o maple calcula isso... Ele levou uns 30s para calcular o 17 000 > 000ésimo primo (= 314 606 869 >=313 837 977.04080 na aproximação), mas > vai ficando bm lento depois. > > > Abraços do Ennius Lima. > > Abraços, > -- > Bernardo Freitas Paulo da Costa > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] RE: [obm-l] Re: [obm-l] Milésimo número primo
Não existe fórmula matemática para calcular número primo, mas você pode usar um programa de computador para isso. Usando C++ dá pra calcular. Usando uma fórmula baseada no algoritmo de Euclides encontrei que o 1000º primo é 7919.Acho que manualmente não há uma maneira muito prática.> From: brped...@hotmail.com > To: obm-l@mat.puc-rio.br > Subject: [obm-l] RE: [obm-l] Re: [obm-l] Milésimo número primo > Date: Thu, 24 Nov 2011 01:28:44 +0300 > > > Bem... há autores que consideram número primo todo inteiro que tenha somente > dois divisores positivos. Ver, por exemplo, Elementos de Álgebra, de Jacy > Monteiro. > Assim, -2, -3, -5, etc. seriam primos. > Abraços do Pedro Chaves! > > > > Date: Wed, 23 Nov 2011 21:37:46 +0100 > > Subject: [obm-l] Re: [obm-l] Milésimo número primo > > From: bernardo...@gmail.com > > To: obm-l@mat.puc-rio.br > > > > 2011/11/23 ennius : > > > Caros Amigos, > > > > > > Na sucessão dos números primos (positivos), qual é o milésimo termo? > > Os números primos são todos positivos. Quanto à sua questão, o maple > > (ou qualquer outro software) diz: > > > > ithprime(1000) -> 7919 > > > > (aliás, vale notar que o maple, como os matemáticos atuais, diz que o > > primeiro número primo é 2) > > > > > Existe fórmula para o cálculo direto? > > A resposta rápida é "não". > > > > A resposta longa é: existem algoritmos que permitem calcular todos os > > números primos menores do que um dado número, mas isso leva bastante > > tempo (crivo de Eratóstenes). Existem algoritmos que decidem se um > > dado número é primo ou não (Lucas-Lehmer para alguns, AKS, ...). > > Existem fórmulas que dão estimativas para o intervalo onde estará o > > n-ésimo número primo, e que começam em geral com "n*log(n)". > > http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number > > > > O mesmo Maple diz que o 1 000 000ésimo primo é 15 485 863. Usando a fórmula > > n-ésimo primo >= n log(n) + n log(log(n)) - n, temos que realmente > > esse número é maior do que 15 441 302.48. Obs: não faço a menor idéia > > como o maple calcula isso... Ele levou uns 30s para calcular o 17 000 > > 000ésimo primo (= 314 606 869 >=313 837 977.04080 na aproximação), mas > > vai ficando bm lento depois. > > > > > Abraços do Ennius Lima. > > > > Abraços, > > -- > > Bernardo Freitas Paulo da Costa > > > > = > > Instruções para entrar na lista, sair da lista e usar a lista em > > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > > = > > = > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > =
[obm-l] Re: [obm-l] RE: [obm-l] Re: [obm-l] Milésimo número primo
2011/11/24 Frederico Matos : > > Não existe fórmula matemática para calcular número primo, mas você pode usar > um programa de computador para isso. > Usando C++ dá pra calcular. Usando uma fórmula baseada no algoritmo de > Euclides encontrei que o 1000º primo é 7919. Qual alg de Euclides? O do mdc? > Acho que manualmente não há uma maneira muito prática. Isso, com certeza, não :) Mas durante muito tempo foi a única maneira, e os matemáticos "se viraram" :) Abraços -- Bernardo Freitas Paulo da Costa = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
