整数のべき数のプログラムについて

Question

以下のようなプログラムを組んでいます。a^4+b^4+c^4+d^4=(n^4+(n+1)^4+(n+2)^4+(n+3)^4)^4=(e)^4となるような数の組み合わせを探すものです。実行はするのですが、答えがデタラメです。エラーではじくのでも実行しないのでもなく、直感的にわかるような間違った数値をかえしてきます。何が問題でしょうか。

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

unsigned long pow4(unsigned long a,int e)
{
return (a*a*a*a);
}

int main()
{
int i, j, k,z,m;
int ctr = 0;
unsigned long long int beki, sigma,temp;

FILE *file;

file = fopen("bekijyo_4.txt", "w");

for (i = 1; i < 200; i++) {
for (j = i + 1; j < 300; j++) {
for (k = j + 1; k < 400; k++) {
for (m = k + 1;m < 500;m++){
beki = pow4(i, 4) + pow4(j, 4) + pow4(k, 4) + pow4(m,4);
for(z = 1;z < 500; z++){
sigma = pow4((z-1), 4) + pow4(z, 4) + pow4((z + 1),4) + pow4((z + 2), 4);
temp = pow4(sigma, 4);
if (beki == temp) {
if (ctr == 0){
printf("ready-----go!\n");
}
ctr++;
printf("(%d ,%d ,%d,%d)=(%d ,%d ,%d, %d)=(%d) \n", i, j, k,m,(z - 1), z, (z + 1),(z + 2), sigma);
fprintf(file, "(%d ,%d ,%d ,%d)=(%d ,%d ,%d ,%d)=(%d) \n", i, j, k, m ,(z - 1), z, (z + 1),(z + 2), sigma);
}
if (beki < temp) break;
}
}
}
}
}
fclose(file);
printf("finish!");
return 0;
}

実行結果
(a,b,c,d)=(n,n+1,n+2,n+3)=(e)

(4 ,164 ,240 ,402)=(0 ,1 ,2 ,3)=(98)
(18 ,48 ,80 ,304)=(191 ,192 ,193 ,194)=(1198807058)
(24 ,264 ,336 ,414)=(28 ,29 ,30 ,31)=(3055458)
(26 ,132 ,200 ,472)=(191 ,192 ,193 ,194)=(1198807058)
(28 ,60 ,296 ,494)=(1 ,2 ,3 ,4)=(354)
(32 ,176 ,312 ,482)=(32 ,33 ,34 ,35)=(5071458)
(36 ,164 ,230 ,268)=(0 ,1 ,2 ,3)=(98)
(44 ,176 ,208 ,470)=(0 ,1 ,2 ,3)=(98)
(48 ,190 ,196 ,276)=(191 ,192 ,193 ,194)=(1198807058)
(64 ,84 ,160 ,214)=(1 ,2 ,3 ,4)=(354)
(64 ,146 ,180 ,492)=(32 ,33 ,34 ,35)=(5071458)
(72 ,108 ,244 ,258)=(26 ,27 ,28 ,29)=(2310354)
(76 ,110 ,236 ,456)=(4 ,5 ,6 ,7)=(4578)
(120 ,208 ,230 ,428)=(30 ,31 ,32 ,33)=(3968018)
(140 ,190 ,284 ,496)=(191 ,192 ,193 ,194)=(1198807058)
(152 ,226 ,352 ,424)=(4 ,5 ,6 ,7)=(4578)

よろしくお願いします。

Ogre7077 · Accepted Answer

追記(5) について

e^4 = a^4 + b^4 + c^4 + d^4
なので、比較する temp[i] は四乗が必要

log2(73938) = 16.17... 
なので、4乗すると64ビット超で桁あふれし計算不可
これ以上の計算は、任意精度演算ライブラリが必要

計算量を減らすため、計算済みの作業用変数を用意する
例) 
e を決める → t0 = e^4
a を決める → t1 = t0 - a^4
...
d を決める → t4 = t3 - d^4
t4 == 0 → 見つけた!

計算量を減らすため、不要な繰り返しは行わせない
例)
b を決める → t2 を計算 → t2 < 0 ならその後の b,c,d の処理は不要
c を決める → t3 を計算 → t3 < 0 ならその後の c,d の処理は不要

余談ではありますが、
すこし計算しましたが、条件を満たす (a,b,c,d,e) の組はなさそうです...

tatsumaru77 · Answer

範囲を５００に広げましたが、１件も該当しません。
ソースは下記URLです。
https://ideone.com/qsofO3

あなたの提示された
if (beki == temp[i])は
if (beki == pow4(temp[i],4))ではないかと思いますが。。。

Tacosan · Answer

pow4 はどうなっている? あと「訳の分からないエラー」ってなに? どんな「メッセージ」が出てる?

なお, 現状では z をそんな驚異的に大きな値にするのは無駄かつ無意味. z<11 で十分.

Tacosan · Answer

ちょっとその「作り変えてみ」たプログラムを出してもらえませんか?

いちばん「簡単」なのは
自動的に多倍長演算するようなプログラム言語を使う
こと, なんだけどね....

Ogre7077 · Answer

int / long は多分 32 ビット整数ですので、
上限である 2^32-1 を超えると桁あふれします。
四乗しても 2^32-1 を超えない値は、
x^4 < 2^32
x < 2^8
x < 256
であるため、256 以上の値を四乗すると破綻します。

修正案1.
関数 pow4 の引数と戻り値を 64 ビット整数の long long 型にする

修正案2.
引数 a は int のままでも、計算途中で long long になるように変形する
例) a * 1ULL * a * a * a

修正案3.
printf で long long を使用するなら、長さ修飾子 ll を指定する
例) printf("%llu", temp); // unsigned long long

修正案4.
2^64 を超える値を計算できる任意精度演算ライブラリの導入を検討する
https://ja.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97

本題とは関係ありませんが、

提案1.
変数 (i,j,k,m,z) は (a,b,c,d,n) と変えるべきです。
仕様と実装の変数名が意味もなく違うので、読んでいて混乱しました

提案2.
a^4+b^4+c^4+d^4 = e^4
を満たす (a,b,c,d,e) を探すより、
n^4+(n+1)^4+(n+2)^4+(n+3)^4 = e
を満たす (n,e) を探すほうがはるかに簡単ですので、
探索順番を以下のようにすれば計算量が削除できます。
n を決める→ 対応する e を計算 → [1,e) の範囲から a,b,c,d を探索