Re: Res: [obm-l] Algoritmo

["Fetofs Ashu" <fetofs@xxxxxxxxx>]

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 b<0), 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:
100<a^2 + b^3<999
100-b^3<a^2<999-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...