Re: Res: [obm-l] Algoritmo
O algoritmo que usei para achar soluções enormes (escrevi em C) foi
basicamente desse jeito:
1) Descubra todos os números possíveis com b positivo (ou seja, para cada a
com a²1000, teste os b's). Essa parte é muito simples e rápida.
2) Achar os números com b negativo:
- Volte o a para 0 (importante, porque há soluções com a²1000 e b0), e
comece a diminuir o b (começando de -1). Eu escolhi ir diminuindo o b e
não o a porque tem menos b's do que a's em qualquer solução.
- Para um determinado b, todos os possíveis a são dados pela inequação:
100a^2 + b^3999
100-b^3a^2999-b^3
sqrt(100-b^3) a sqrt(999-b^3)
Se não há números inteiros entre sqrt(100-b^3) e sqrt(999-b^3), então não há
solução. Se há, esses números são soluções garantidas, e você pode fazer o
que quiser com eles (mostrar na command line, adicionar a uma lista de
soluções, etc.). O código está aí embaixo, mas se você não souber usar GMP
não vai servir pra muita coisa... O último valor que eu vejo depois de meio
minuto rodando ele é:
a = 611085363
b = -720114
a^2+b^3 = 225
Depois desse valor ele parece parar de produzir soluções por um bom tempo.
#include stdio.h
#include gmp.h
int main() {
mpz_t b, a, b_cbd, min_val, max_val, sum, a_sq;
mpz_init_set_si(b, -1);
mpz_init(a);
mpz_init(b_cbd);
mpz_init(min_val);
mpz_init(max_val);
mpz_init(sum);
mpz_init(a_sq);
while (1) {
mpz_pow_ui(b_cbd, b, 3);
mpz_ui_sub(min_val, 100, b_cbd);
if (mpz_perfect_square_p(min_val)) {
mpz_sqrt(min_val, min_val);
}
else {
mpz_sqrt(min_val, min_val);
mpz_add_ui(min_val, min_val, 1);
}
mpz_ui_sub(max_val, 999, b_cbd);
mpz_sqrt(max_val, max_val);
mpz_add_ui(max_val, max_val, 1);
mpz_set(a, min_val);
while (mpz_cmp(a, max_val) == -1) {
mpz_pow_ui(a_sq, a, 2);
mpz_add(sum, b_cbd, a_sq);
mpz_out_str(NULL, 10, sum);
printf( );
mpz_out_str(NULL, 10, a);
printf( );
mpz_out_str(NULL, 10, b);
printf(\n);
mpz_add_ui(a, a, 1);
}
mpz_sub_ui(b, b, 1);
}
}
Quem te passou esse problema disse que ele podia ser resolvido? Ou você está
satisfazendo um problema-curiosidade? Se for a segunda opção, é possível
que você nunca encontre todos os valores possíveis. Se for a primeira,
talvez tenha um jeito matemático de reduzir os possíveis valores finais...
Res: Res: [obm-l] Algoritmo
Será que baseado no fato de o limite não existir eu posso afirmar que TODOS os numeros de três algarismos podem ser escritos como a soma de um quadrado e um cubo. X=a^2+b^3 onde a e b são inteiros quaisquer. - Mensagem original De: Danilo Nascimento [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Segunda-feira, 24 de Setembro de 2007 14:08:01 Assunto: Res: [obm-l] Algoritmo Se tal limite não existe, como que eu vou fazer um algoritmo então? Será que eu vou ter que usar os limites que a linguagem oferece? Dá algo em torno de 2 bilhões. Mas qual a garantia que eu tenho que eu vou achar todos os numeros de três algarismos? Parece ser complicado. - Mensagem original De: Fetofs Ashu [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Sábado, 22 de Setembro de 2007 14:35:34 Assunto: Re: [obm-l] Algoritmo Eu acho que não há limites para a e b, se b pode ser negativo. Tome como exemplo a = 38339 e b = -1137 (resultado 568). Tenho certeza de que se continuasse acharia valores maiores ainda... Fernando Oliveira On 9/21/07, Danilo Nascimento [EMAIL PROTECTED] wrote: Olá pessoal estou tentando desenvolver um algoritmo em Pascal para achar todos os números de 3 algarismos que podem ser escritos como a soma de um quadrado e um cubo. Só que tem um problema, como achar os limites dos valores que estão variando o contador? Por exemplo : 100a^2+b^3999. Preciso fazer um loop com os valores de a e b, que podem ser tanto positivos quanto negativos. Eu fiz na base da tentativa e erro e achei que o máximo de a seria 941 e o mínimo de b=-96. Não sei se são exatamente esses os valores. Mas de qualquer forma como eu faria isso de um modo formal? Agradeço desde já qualquer ajuda. Flickr agora em português. Você clica, todo mundo vê. Saiba mais . Flickr agora em português. Você clica, todo mundo vê. Saiba mais. Flickr agora em português. Você clica, todo mundo vê. http://www.flickr.com.br/
Re: Res: [obm-l] Algoritmo
Conjectura de Danilo, hehehehehehe Vc pode tentar comprovar isso montando um programa que começe com a²=1, e vai variando b no sentido positivo e vá vendo os numeros de 3 algarismos formados; faça isso enquanto a²1000; quando a²=1000, faça-0 continar aumentando, e agora faça b variar no sentido negativo; há uma grande chance dessa sua conjectura está correta. Vc também pode tentar contar na forma de funcao geratriz, mas aí daria trabalho Em 26/09/07, Danilo Nascimento [EMAIL PROTECTED] escreveu: Será que baseado no fato de o limite não existir eu posso afirmar que TODOS os numeros de três algarismos podem ser escritos como a soma de um quadrado e um cubo. X=a^2+b^3 onde a e b são inteiros quaisquer. - Mensagem original De: Danilo Nascimento [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Segunda-feira, 24 de Setembro de 2007 14:08:01 Assunto: Res: [obm-l] Algoritmo Se tal limite não existe, como que eu vou fazer um algoritmo então? Será que eu vou ter que usar os limites que a linguagem oferece? Dá algo em torno de 2 bilhões. Mas qual a garantia que eu tenho que eu vou achar todos os numeros de três algarismos? Parece ser complicado. - Mensagem original De: Fetofs Ashu [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Sábado, 22 de Setembro de 2007 14:35:34 Assunto: Re: [obm-l] Algoritmo Eu acho que não há limites para a e b, se b pode ser negativo. Tome como exemplo a = 38339 e b = -1137 (resultado 568). Tenho certeza de que se continuasse acharia valores maiores ainda... Fernando Oliveira On 9/21/07, Danilo Nascimento [EMAIL PROTECTED] wrote: Olá pessoal estou tentando desenvolver um algoritmo em Pascal para achar todos os números de 3 algarismos que podem ser escritos como a soma de um quadrado e um cubo. Só que tem um problema, como achar os limites dos valores que estão variando o contador? Por exemplo : 100a^2+b^3999. Preciso fazer um loop com os valores de a e b, que podem ser tanto positivos quanto negativos. Eu fiz na base da tentativa e erro e achei que o máximo de a seria 941 e o mínimo de b=-96. Não sei se são exatamente esses os valores. Mas de qualquer forma como eu faria isso de um modo formal? Agradeço desde já qualquer ajuda. Flickr agora em português. Você clica, todo mundo vê. Saiba mais http://br.rd.yahoo.com/mail/taglines/flickr/*http://www.flickr.com.br/. Flickr agora em português. Você clica, todo mundo vê. Saiba maishttp://br.rd.yahoo.com/mail/taglines/flickr/*http://www.flickr.com.br/. Flickr agora em português. Você clica, todo mundo vê. Saiba maishttp://br.rd.yahoo.com/mail/taglines/flickr/*http://www.flickr.com.br/. -- Samir Rodrigues
Re: Res: [obm-l] Algoritmo
Esqueçam sobre a função geratriz Em 26/09/07, Samir Rodrigues [EMAIL PROTECTED] escreveu: Conjectura de Danilo, hehehehehehe Vc pode tentar comprovar isso montando um programa que começe com a²=1, e vai variando b no sentido positivo e vá vendo os numeros de 3 algarismos formados; faça isso enquanto a²1000; quando a²=1000, faça-0 continar aumentando, e agora faça b variar no sentido negativo; há uma grande chance dessa sua conjectura está correta. Vc também pode tentar contar na forma de funcao geratriz, mas aí daria trabalho Em 26/09/07, Danilo Nascimento [EMAIL PROTECTED] escreveu: Será que baseado no fato de o limite não existir eu posso afirmar que TODOS os numeros de três algarismos podem ser escritos como a soma de um quadrado e um cubo. X=a^2+b^3 onde a e b são inteiros quaisquer. - Mensagem original De: Danilo Nascimento [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Segunda-feira, 24 de Setembro de 2007 14:08:01 Assunto: Res: [obm-l] Algoritmo Se tal limite não existe, como que eu vou fazer um algoritmo então? Será que eu vou ter que usar os limites que a linguagem oferece? Dá algo em torno de 2 bilhões. Mas qual a garantia que eu tenho que eu vou achar todos os numeros de três algarismos? Parece ser complicado. - Mensagem original De: Fetofs Ashu [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Sábado, 22 de Setembro de 2007 14:35:34 Assunto: Re: [obm-l] Algoritmo Eu acho que não há limites para a e b, se b pode ser negativo. Tome como exemplo a = 38339 e b = -1137 (resultado 568). Tenho certeza de que se continuasse acharia valores maiores ainda... Fernando Oliveira On 9/21/07, Danilo Nascimento [EMAIL PROTECTED] wrote: Olá pessoal estou tentando desenvolver um algoritmo em Pascal para achar todos os números de 3 algarismos que podem ser escritos como a soma de um quadrado e um cubo. Só que tem um problema, como achar os limites dos valores que estão variando o contador? Por exemplo : 100a^2+b^3999. Preciso fazer um loop com os valores de a e b, que podem ser tanto positivos quanto negativos. Eu fiz na base da tentativa e erro e achei que o máximo de a seria 941 e o mínimo de b=-96. Não sei se são exatamente esses os valores. Mas de qualquer forma como eu faria isso de um modo formal? Agradeço desde já qualquer ajuda. Flickr agora em português. Você clica, todo mundo vê. Saiba mais http://br.rd.yahoo.com/mail/taglines/flickr/*http://www.flickr.com.br/. Flickr agora em português. Você clica, todo mundo vê. Saiba maishttp://br.rd.yahoo.com/mail/taglines/flickr/*http://www.flickr.com.br/. Flickr agora em português. Você clica, todo mundo vê. Saiba mais http://br.rd.yahoo.com/mail/taglines/flickr/*http://www.flickr.com.br/. -- Samir Rodrigues -- Samir Rodrigues
Res: [obm-l] Algoritmo
Se tal limite não existe, como que eu vou fazer um algoritmo então? Será que eu vou ter que usar os limites que a linguagem oferece? Dá algo em torno de 2 bilhões. Mas qual a garantia que eu tenho que eu vou achar todos os numeros de três algarismos? Parece ser complicado. - Mensagem original De: Fetofs Ashu [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Sábado, 22 de Setembro de 2007 14:35:34 Assunto: Re: [obm-l] Algoritmo Eu acho que não há limites para a e b, se b pode ser negativo. Tome como exemplo a = 38339 e b = -1137 (resultado 568). Tenho certeza de que se continuasse acharia valores maiores ainda... Fernando Oliveira On 9/21/07, Danilo Nascimento [EMAIL PROTECTED] wrote: Olá pessoal estou tentando desenvolver um algoritmo em Pascal para achar todos os números de 3 algarismos que podem ser escritos como a soma de um quadrado e um cubo. Só que tem um problema, como achar os limites dos valores que estão variando o contador? Por exemplo : 100a^2+b^3999. Preciso fazer um loop com os valores de a e b, que podem ser tanto positivos quanto negativos. Eu fiz na base da tentativa e erro e achei que o máximo de a seria 941 e o mínimo de b=-96. Não sei se são exatamente esses os valores. Mas de qualquer forma como eu faria isso de um modo formal? Agradeço desde já qualquer ajuda. Flickr agora em português. Você clica, todo mundo vê. Saiba mais . Flickr agora em português. Você clica, todo mundo vê. http://www.flickr.com.br/
Res: [obm-l] Algoritmo
Olá Marcelo, acho que não vai funcionar desse jeito. Eu, por exemplo, posso tomar a=33 e b=-5 a^2+b^3 = 964. Eu estaria excluindo esse número. []'s. - Mensagem original De: Marcelo Salhab Brogliato [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Enviadas: Sexta-feira, 21 de Setembro de 2007 21:41:06 Assunto: Re: [obm-l] Algoritmo Olá Danilo, fica aqui uma sugestão: Considere b=0, entao: 100 a^2 999 10 |a| 32 [soh pra arredondar] Do mesmo modo, vc acha: 4 |b| 10 faca a variar de 10 à 32... b variar de 4 à 10... se a soma passar de 999, dê um break no for interno e passe para o proximo... abracos, Salhab On 9/21/07, Danilo Nascimento [EMAIL PROTECTED] wrote: Olá pessoal estou tentando desenvolver um algoritmo em Pascal para achar todos os números de 3 algarismos que podem ser escritos como a soma de um quadrado e um cubo. Só que tem um problema, como achar os limites dos valores que estão variando o contador? Por exemplo : 100a^2+b^3999. Preciso fazer um loop com os valores de a e b, que podem ser tanto positivos quanto negativos. Eu fiz na base da tentativa e erro e achei que o máximo de a seria 941 e o mínimo de b=-96. Não sei se são exatamente esses os valores. Mas de qualquer forma como eu faria isso de um modo formal? Agradeço desde já qualquer ajuda. Flickr agora em português. Você clica, todo mundo vê. Saiba mais. = 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 = Flickr agora em português. Você clica, todo mundo vê. http://www.flickr.com.br/
