Re: [obm-l] Fatorial <> Quadrado
Caro Claudio Buffara > Se P(n) = n-esimo primo (P(1) = 2, P(2) = 3, P(3) = 5, ...), entao prove > que > para n >= 5, P(n)^2 < P(1)*P(2)*...*P(n-1). Ha demosntracao disto em: Rademacher, H. et alt. PLAISIR DES MATHEMATIQUES Dunod 1967 Angelo Barone Netto <[EMAIL PROTECTED]> = 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 =
Re: [obm-l] Fatorial <> Quadrado
Oi, Eduardo: Infelizmente, acho que você está certo - sem postulado de Bertrand, nada feito! De fato, Bertrand prova a seguinte generalização desse resultado: O produto de n inteiros positivos consecutivos (n >= 2) nunca é igual a uma potência de algum inteiro (expoente >= 2). Seja M o maior inteiro do produto. Então, o maior primo p <= M tem expoente 1 na decomposição do produto em fatores primos, pois caso contrário, teríamos 2p <= n e, portanto, pelo postulado de Bertrand, existiria um primo q tal que p < q < 2p <= n, contrariamente à escolha de p. Um abraço, Claudio. - Original Message - From: "Eduardo Azevedo" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Friday, September 19, 2003 11:42 AM Subject: Re: [obm-l] Fatorial <> Quadrado > Foi mal galera. Como várias pessoas da lista já comentaram, a "solução" que > eu mandei para esse problema está errada. Inclusive, eu acho que vai ser > difícil de fazer essa sem o postulado de Bertrand. É só dar uma olhada > nessas fatorações dos n!, que vou digitar agora. Tem vários casos onde só os > "últimos" primos tem expoentes ímpares. E para garantir que existem esses > últimos primos só com o postulado de Bertrand. Mesmo a observação do Will > não salva, pois toda hora o 2 está com potência par > > > > > 1, 1 > > > 2, (2) > > > 3, (2) (3) > > >3 > 4, (2) (3) > > > 3 >5, (2) (3) (5) > > > 42 >6, (2) (3) (5) > > >42 > 7, (2) (3) (5) (7) > > >72 > 8, (2) (3) (5) (7) > > >74 > 9, (2) (3) (5) (7) > > >842 > 10, (2) (3) (5) (7) > > > 842 > 11, (2) (3) (5) (7) (11) > > > 1052 > 12, (2) (3) (5) (7) (11) > > > 1052 > 13, (2) (3) (5) (7) (11) (13) > > > 11522 > 14, (2) (3) (5) (7) (11) (13) > > > 11632 > 15, (2) (3) (5) (7) (11) (13) > > > 15632 > 16, (2) (3) (5) (7) (11) (13) > > > 15632 >17, (2) (3) (5) (7) (11) (13) (17) > > > 16832 >18, (2) (3) (5) (7) (11) (13) (17) > > > 16832 > 19, (2) (3) (5) (7) (11) (13) (17) (19) > > > 18842 > 20, (2) (3) (5) (7) (11) (13) (17) (19) > > > 18943 > 21, (2) (3) (5) (7) (11) (13) (17) (19) > > >19943 2 > 22, (2) (3) (5) (7) (11) (13) (17) (19) > > > 19943 2 > 23, (2) (3) (5) (7) (11) (13) (17) (19) (23) > > > 221043 2 > 24, (2) (3) (5) (7) (11) (13) (17) (19) (23) > > > 221063 2 > 25, (2) (3) (5) (7) (11) (13) (17) (19) (23) > > > 231063 2 2 > 26, (2) (3) (5) (7) (11) (13) (17) (19) (23) > > > 231363 2 2 > 27, (2) (3) (5) (7) (11) (13) (17) (19) (23) > > > 251364 2 2 > 28, (2) (3) (5) (7) (11) (13) (17) (19) (23) > > > 251364 2 2 > 29, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) > > > 261474 2 2 > 30, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) > > >261474 2 2 > 31, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) > > >311474 2 2 > 32, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) > > >311574 3 2 > 33, (2) (3) (5
Re: [obm-l] Fatorial <> Quadrado
Foi mal galera. Como várias pessoas da lista já comentaram, a "solução" que eu mandei para esse problema está errada. Inclusive, eu acho que vai ser difícil de fazer essa sem o postulado de Bertrand. É só dar uma olhada nessas fatorações dos n!, que vou digitar agora. Tem vários casos onde só os "últimos" primos tem expoentes ímpares. E para garantir que existem esses últimos primos só com o postulado de Bertrand. Mesmo a observação do Will não salva, pois toda hora o 2 está com potência par 1, 1 2, (2) 3, (2) (3) 3 4, (2) (3) 3 5, (2) (3) (5) 42 6, (2) (3) (5) 42 7, (2) (3) (5) (7) 72 8, (2) (3) (5) (7) 74 9, (2) (3) (5) (7) 842 10, (2) (3) (5) (7) 842 11, (2) (3) (5) (7) (11) 1052 12, (2) (3) (5) (7) (11) 1052 13, (2) (3) (5) (7) (11) (13) 11522 14, (2) (3) (5) (7) (11) (13) 11632 15, (2) (3) (5) (7) (11) (13) 15632 16, (2) (3) (5) (7) (11) (13) 15632 17, (2) (3) (5) (7) (11) (13) (17) 16832 18, (2) (3) (5) (7) (11) (13) (17) 16832 19, (2) (3) (5) (7) (11) (13) (17) (19) 18842 20, (2) (3) (5) (7) (11) (13) (17) (19) 18943 21, (2) (3) (5) (7) (11) (13) (17) (19) 19943 2 22, (2) (3) (5) (7) (11) (13) (17) (19) 19943 2 23, (2) (3) (5) (7) (11) (13) (17) (19) (23) 221043 2 24, (2) (3) (5) (7) (11) (13) (17) (19) (23) 221063 2 25, (2) (3) (5) (7) (11) (13) (17) (19) (23) 231063 2 2 26, (2) (3) (5) (7) (11) (13) (17) (19) (23) 231363 2 2 27, (2) (3) (5) (7) (11) (13) (17) (19) (23) 251364 2 2 28, (2) (3) (5) (7) (11) (13) (17) (19) (23) 251364 2 2 29, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) 261474 2 2 30, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) 261474 2 2 31, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) 311474 2 2 32, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) 311574 3 2 33, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) 321574 3 2 2 34, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) 321585 3 2 2 35, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) 341785 3 2 2 36, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) 341785 3 2 2 37, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) (37) 351785 3 2 2 2 38, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) (37) 351885 3 3 2 2 39, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) (37) 381895 3 3 2 2 40, (2) (3) (5) (7) (11) (13) (17) (19) (23) (29) (31) (37) abraço -Eduardo = 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 =
Re: [obm-l] Fatorial <> Quadrado
Vamos tentar por partes... Quando n eh primo fica facil ver que n! nao eh quadrado Para n nao primos: Usando a sua menssagem "Base 2 / Fatoriais / Binom(n,k)" 1) O expoente do primo p na decomposicao de n! eh igual a: [n/p] + [n/p^2] + [n/p^3] + ... onde [x] = maior inteiro <= x. Soh analizando o expoente de 2 da pra eliminar varios numeros se n = 2^m (m inteiro positivo) entao n!=2^a*3^b*... (a impar) <> quadrado se n = 2k ou 2k + 1 (k par) o coeficiente de 2 tb eh sempre impar faltam soh os n nao primos da forma 2k ou 2k +1 (k impar) ... no caso de k primo acho ki e facil ver que o coeficiente de k eh impar... deve ter uma maneira de escolher o melhor coeficiente pra analizar quando k eh impar. De qualquer forma isso foi o ki eu pensei ate agora, pode servir ou nao, e nao ofereco garantia nenhuma :). Se estiver totalmente errado nao eh a primeira vez e certamente nao sera a ultima. -Auggy - Original Message - From: "Claudio Buffara" <[EMAIL PROTECTED]> To: "Lista OBM" <[EMAIL PROTECTED]> Sent: Tuesday, September 16, 2003 3:46 PM Subject: [obm-l] Fatorial <> Quadrado > Oi, pessoal: > > Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado > perfeito que nao use o postulado de Bertrand? > > > > Mesma pergunta para este aqui: > > Se P(n) = n-esimo primo (P(1) = 2, P(2) = 3, P(3) = 5, ...), entao prove que > para n >= 5, P(n)^2 < P(1)*P(2)*...*P(n-1). > > > Um abraco, > 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 =
Re: [obm-l] Fatorial <> Quadrado
on 17.09.03 19:45, marcelo oliveira at [EMAIL PROTECTED] wrote: >> >> Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado >> perfeito que nao use o postulado de Bertrand? >> > Bem, não sei se estou falando besteira mas acho que tenho uma demonstração > simples para o problema proposto, que até usa números primos, mas não > utiliza o Postulado de Bertrand. > > Seja n! = 1.2.3.4.5...(n - 1).n > Agora faça o seguinte: a partir de n, ande da direita para a esquerda na > expressão 1.2.3.4...(n - 1).n, analisando se cada número que você está > passando é primo ou composto. Uma hora você vai passar pela primeira vez por > um número primo p. Claramente este primo p não possui nenhum divisor > 1 > menor que ele, ou seja, na fatoração de n! o expoente de p é 1, fazendo com > que n! nunca seja um quadrado perfeito para n > 1. > > Até mais, > Marcelo Rufino de Oliveira > Oi, Marcelo: Eu pensei nisso. Voce estah falando do maior primo p tal que p <= n. O expoente desse p em n! serah igual a 1 se e somente se n < 2p, mas como voce prova isso sem usar o postulado de Bertrand? Com Bertrand sai em 2 linhas: Se n >= 2p, entao existirah um primo q tal que p < q < 2p <= n, contrariamente a escolha de p. Logo, deve ser n < 2p. Um abraco, 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 =
Re: [obm-l] Fatorial <> Quadrado
Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado perfeito que nao use o postulado de Bertrand? Bem, não sei se estou falando besteira mas acho que tenho uma demonstração simples para o problema proposto, que até usa números primos, mas não utiliza o Postulado de Bertrand. Seja n! = 1.2.3.4.5...(n - 1).n Agora faça o seguinte: a partir de n, ande da direita para a esquerda na expressão 1.2.3.4...(n - 1).n, analisando se cada número que você está passando é primo ou composto. Uma hora você vai passar pela primeira vez por um número primo p. Claramente este primo p não possui nenhum divisor > 1 menor que ele, ou seja, na fatoração de n! o expoente de p é 1, fazendo com que n! nunca seja um quadrado perfeito para n > 1. Até mais, Marcelo Rufino de Oliveira _ MSN Messenger: instale grátis e converse com seus amigos. http://messenger.msn.com.br = 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 =
Re: [obm-l] Fatorial <> Quadrado
Oi, Ed: Infelizmente, você só pode dizer que d(m*n) = d(m)*d(n) se m e n forem primos entre si, o que não é válido no caso de n! se n >= 4, pois mdc(4,2) = 2 (e de fato d(4!) = d(24) = 8, mas d(4)*d(3)*d(2)*d(1) = 3*2*2*1 = 12). Mas valeu pela atenção ao problema. Um abraço, Claudio. - Original Message - From: Eduardo Azevedo To: [EMAIL PROTECTED] Sent: Wednesday, September 17, 2003 3:05 PM Subject: Re: [obm-l] Fatorial <> Quadrado > Oi, pessoal:>> Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado> perfeito que nao use o postulado de Bertrand? É só a gente ver que os quadrados são os números que tem uma quantidade ímpar de divisores. Afinal, os divisores de n vem em pares n e n/d. A única exceção é, se existir, raiz de n. Agora, se chamarmos de d(n) o número de divisores de n temos d(n!) = d(n)*d(n-1)*...d(2)*d(1), que é par pois d(2) é par. Então n! não pode ser quadrado. abrc -ed
Re: [obm-l] Fatorial <> Quadrado
d(24)=8 d(6)=4 d(4)=3 Logo, d(24)<>d(6)*d(4). A igualdade so vale, se os fatores forem primos entre si. Abraco, Salvador On Wed, 17 Sep 2003, Eduardo Azevedo wrote: > > Oi, pessoal: > > > > Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado > > perfeito que nao use o postulado de Bertrand? > > É só a gente ver que os quadrados são os números que tem uma quantidade ímpar de > divisores. Afinal, os divisores de n vem em pares n e n/d. A única exceção é, se > existir, raiz de n. > > Agora, se chamarmos de d(n) o número de divisores de n temos > > d(n!) = d(n)*d(n-1)*...d(2)*d(1), que é par pois d(2) é par. Então n! não pode ser > quadrado. > > > abrc > > -ed = 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 =
Re: [obm-l] Fatorial <> Quadrado
> Oi, pessoal:>> Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado> perfeito que nao use o postulado de Bertrand? É só a gente ver que os quadrados são os números que tem uma quantidade ímpar de divisores. Afinal, os divisores de n vem em pares n e n/d. A única exceção é, se existir, raiz de n. Agora, se chamarmos de d(n) o número de divisores de n temos d(n!) = d(n)*d(n-1)*...d(2)*d(1), que é par pois d(2) é par. Então n! não pode ser quadrado. abrc -ed
Re: [obm-l] Fatorial <> Quadrado
Eu acho que isto nao e tao facil:a coisa e achar todos os pares (a,b) com a^2=b! e voce so demonstrou que a nao e igual a b...Felipe Pina <[EMAIL PROTECTED]> wrote: > Oi, pessoal:>> Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado> perfeito que nao use o postulado de Bertrand?Sim, uma demonstração bem simples.Sejamf(n) := n^2g(n) := n!=> (DELTA(f))(n) = f(n+1) - f(n) = (n + 1)^2 - n^2 = 2n + 1(DELTA(g))(n) = g(n+1) - g(n) = (n + 1)! - n! = (n + 1)*(n!) - n! = n*(n!)Então (DELTA(g))(n) - (DELTA(f))(n) = n*(n! - 2) - 1n >=4 => n! >= 24 => n*(n! - 2) >= 4*(24 - 2) = 4*22 = 88Ou seja, para n >=4, a função g(n) cresce mais rapidamente que f(n)Ora, g(4) = 4! = 24 e f(4) = 4^2 = 16g(4) > f(4). Logo, de n=4 em diante as funções nao se igualam mais.Resta apenas checar os pontos antes de 4...g(3) = 3! = 6 != 9 = 3^2 = f(3)g(2) = 2! = 2 != 4 = 2^2 = f(2)Então f(n) e g(n) são diferentes para todo n > 1.-- Felipe Pina=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html===Desafio AntiZona: participe do jogo de perguntas e respostas que vai dar 1 Renault Clio, computadores, câmeras digitais, videogames e muito mais!
Re: [obm-l] Fatorial <> Quadrado
Vc tem toda a razao. Meu erro. On Tue, 16 Sep 2003 23:11:36 -0300, Eduardo Casagrande Stabel <[EMAIL PROTECTED]> wrote: Oi Felipe, a pergunta é mais geral do que esta: será que para n > 1 existe m tal que f(m) = g(n)? Duda. From: "Felipe Pina" <[EMAIL PROTECTED]> > Oi, pessoal: > > Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado > perfeito que nao use o postulado de Bertrand? Sim, uma demonstração bem simples. Sejam f(n) := n^2 g(n) := n! => (DELTA(f))(n) = f(n+1) - f(n) = (n + 1)^2 - n^2 = 2n + 1 (DELTA(g))(n) = g(n+1) - g(n) = (n + 1)! - n! = (n + 1)*(n!) - n! = n*(n!) Então (DELTA(g))(n) - (DELTA(f))(n) = n*(n! - 2) - 1 n >=4 => n! >= 24 => n*(n! - 2) >= 4*(24 - 2) = 4*22 = 88 Ou seja, para n >=4, a função g(n) cresce mais rapidamente que f(n) Ora, g(4) = 4! = 24 e f(4) = 4^2 = 16 g(4) > f(4). Logo, de n=4 em diante as funções nao se igualam mais. Resta apenas checar os pontos antes de 4... g(3) = 3! = 6 != 9 = 3^2 = f(3) g(2) = 2! = 2 != 4 = 2^2 = f(2) Então f(n) e g(n) são diferentes para todo n > 1. -- Felipe Pina = 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 = -- Felipe Pina = 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 =
Re: [obm-l] Fatorial <> Quadrado
Oi Felipe, a pergunta é mais geral do que esta: será que para n > 1 existe m tal que f(m) = g(n)? Duda. From: "Felipe Pina" <[EMAIL PROTECTED]> > > Oi, pessoal: > > > > Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado > > perfeito que nao use o postulado de Bertrand? > > Sim, uma demonstração bem simples. > > Sejam >f(n) := n^2 >g(n) := n! > > => (DELTA(f))(n) = f(n+1) - f(n) = (n + 1)^2 - n^2 = 2n + 1 >(DELTA(g))(n) = g(n+1) - g(n) = (n + 1)! - n! = (n + 1)*(n!) - n! = > n*(n!) > > Então (DELTA(g))(n) - (DELTA(f))(n) = n*(n! - 2) - 1 > > n >=4 => n! >= 24 => n*(n! - 2) >= 4*(24 - 2) = 4*22 = 88 > Ou seja, para n >=4, a função g(n) cresce mais rapidamente que f(n) > Ora, g(4) = 4! = 24 e f(4) = 4^2 = 16 > g(4) > f(4). Logo, de n=4 em diante as funções nao se igualam mais. > Resta apenas checar os pontos antes de 4... > > g(3) = 3! = 6 != 9 = 3^2 = f(3) > g(2) = 2! = 2 != 4 = 2^2 = f(2) > Então f(n) e g(n) são diferentes para todo n > 1. > > -- > Felipe Pina > > = > 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 =
Re: [obm-l] Fatorial <> Quadrado
Oi, pessoal: Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado perfeito que nao use o postulado de Bertrand? Sim, uma demonstração bem simples. Sejam f(n) := n^2 g(n) := n! => (DELTA(f))(n) = f(n+1) - f(n) = (n + 1)^2 - n^2 = 2n + 1 (DELTA(g))(n) = g(n+1) - g(n) = (n + 1)! - n! = (n + 1)*(n!) - n! = n*(n!) Então (DELTA(g))(n) - (DELTA(f))(n) = n*(n! - 2) - 1 n >=4 => n! >= 24 => n*(n! - 2) >= 4*(24 - 2) = 4*22 = 88 Ou seja, para n >=4, a função g(n) cresce mais rapidamente que f(n) Ora, g(4) = 4! = 24 e f(4) = 4^2 = 16 g(4) > f(4). Logo, de n=4 em diante as funções nao se igualam mais. Resta apenas checar os pontos antes de 4... g(3) = 3! = 6 != 9 = 3^2 = f(3) g(2) = 2! = 2 != 4 = 2^2 = f(2) Então f(n) e g(n) são diferentes para todo n > 1. -- Felipe Pina = 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 =
[obm-l] Fatorial <> Quadrado
Oi, pessoal: Alguem conhece alguma demonstracao de que nenhum fatorial > 1 eh quadrado perfeito que nao use o postulado de Bertrand? Mesma pergunta para este aqui: Se P(n) = n-esimo primo (P(1) = 2, P(2) = 3, P(3) = 5, ...), entao prove que para n >= 5, P(n)^2 < P(1)*P(2)*...*P(n-1). Um abraco, 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 =
