x=a^3+b^3を満たす異なる2つのa,bの組を探す

Question

/*
x=a^3+b^3を満たす異なる2つのa,bの組を持つxを探す
*/

#include <stdio.h>
int main(void)
{
	int x, a1, b1, y, a2, b2;

	for(x = 1; x <= 10000; x++) {	
		for(a1 = 1; a1 <= 22; a1++) {
			for(b1 = 1; b1<= 22; b1++) {
				for(y = 1;y <= 10000; y++) {
					for(a2 = 1; a2 <= 22; a2++) {
						for(b2 = 1; b2 <= 22; b2++) {
							x = a1*a1*a1 + b1*b1*b1;
							y = a2*a2*a2 + b2*b2*b2;
							if(x == y && a1 != a2 && b1 != b2)
							printf("%d\n",x);
							
						}
					}
				}	
			}
		}
	}

	return 0;
}

1<=x<=10000の整数xについて、x=a^3+b^3を満たす異なる整数a,bの組を2つ持つxを表示するプログラムを作ろうとしています。
例えば、1729=1^3+12^3=9^3+10^3のように異なる2つのa,bの組を持つxを探します。
じぶんの考えとしては、x=aaa+bbb, y=ccc+dddと置いて、xとyが等しく、aとcが異なり、bとdが異なる時にそのxを表示するようにしたのですが、うまくいきません。a~dの繰り返しが22までなのは3乗して10000を超えないのが22までだからです。どのように修正すればうまくできるでしょうか。言語はCです。

Answer 1

元のループでは、ループ内でxやyを書き換えてしまっているため、うまくループしません。というより、計算結果しか入れないのであればxやyでループさせる意味が全くありません。

そして、効率のことを考えれば、

1. まず1～22までの3乗にした値の表を作っておいて、それを2つ組み合わせる形で計算する
2. そして、a^3 + b^3 = c^3 + d^3となる以上、a < c ≦ d < bに限定して探せばいい

というような絞り込みをやれば、探索範囲はぐっと狭くなります。

Comments

[maisumakun]

なお、試しに計算させてみたところ、条件を満たすのは1729と4104だけのようです。

[vain_taka]

なるほど、xとyを使う必要はなかったんですね。
a<c<=b<dにするという発想は浮かびませんでした。非常に参考になります。

Answer 2

アルゴリズムをすべて検証したわけではありませんが、forループにxとyを使ったものがあるのに、

                            x = a1*a1*a1 + b1*b1*b1;
                            y = a2*a2*a2 + b2*b2*b2;

としてループ内の処理で値を変えてしまうと、うまくループが回らなくなるのではないですか?
xとyは計算で求める値なので、ループ変数にする必要はないと思います。

Answer 3

こんにちは、maisumakunさんがおっしゃるとおり

a^3 + b^3 = c^3 + d^3となる以上、a < c ≦ d < bに限定して探せばいい

ので、for文でループする際a,b,c,dのループするスタート地点は

それぞれa = 1, c = a + 1,d = c, b = d + 1とすればいいでしょう。

こうすることで、必然的にa != c , b != dとなります。

ゴール地点ですが基本的に3乗の値が10000未満までという条件式を立てれればいいでしょう。
ただ、効率化を図るためにb < 10000 - (現在のaの３乗)とすれば処理速度は速くなります。dも同様です。
私は、3乗を求めるところを関数にしていますが、関数にしなくてもいいです。

#include <stdio.h>

#define MAX_NUMBER 10000

int Cubed(int);

int main(void){
    
    int a,b,c,d;
    int sum1,sum2;
    for(a = 1; Cubed(a) < MAX_NUMBER; a++){
       for(c = a + 1; Cubed(c) < MAX_NUMBER; c++){
    	   for(d = c; Cubed(d) < MAX_NUMBER - Cubed(c) ; d++){
    	      for(b = d + 1; Cubed(b) < MAX_NUMBER - Cubed(a); b++){
    	         sum1 = Cubed(a) + Cubed(b);
    	         sum2 = Cubed(c) + Cubed(d);
                 if(sum1 == sum2){
                   printf("%d ^ 3 + %d ^ 3 = %d ^ 3 + %d ^ 3 = %d\n",a,b,c,d,sum1);
    	         }
              }
    	   }
        }
    }
    return 0;
}

int Cubed(int a){
    return a * a * a;
}

<実行結果>
1 ^ 3 + 12 ^ 3 = 9 ^ 3 + 10 ^ 3 = 1729
2 ^ 3 + 16 ^ 3 = 9 ^ 3 + 15 ^ 3 = 4104

Comments

[vain_taka]

maisumakunさんおっしゃったことをさらに詳しく説明していただきとてもわかりやすかったです。効率化のくだりは参考になりました。