「ある整数が偶数なら2で割り、奇数なら3倍して1足す」
この操作を何度も繰り返すとどんな整数でもいつかは1にたどりつく。
って予想があります。コラッツ予想とか角谷予想とか言われてます。
整数nに対し上記操作を何回やれば1になるか、
その回数を返す関数を collatz(n) としましょうか。
たとえば:
3→10→5→16→8→4→2→1(7回) なので collatz(3) = 7 です。
collattz(n)が大きな値となるnを、ちょいちょいとコード書いて走らせてます。
目下のところ collatz(226588897) = 956 を見つけました。
無限の桁を持つ整数クラスがあるなら、時間さえかければいくらでも大きな
やつが見つかると思うけど、いまんとこ(30分ブン回し)ここらが限界かしら。
ぃゃだからどーしたってことはなく、ぢみに面白いなー、と。
[追記] 一晩回しっぱにして collatz(537099606) = 965 。
回しっぱにしてるのはコレ↓ 凝ったマネはしてましぇん。
#include <iostream>
#include <cassert>
typedef unsigned long long integer;
integer collatz(integer n) {
integer count = 0;
while ( n != 1 ) {
if ( n % 2 ) {
integer t = n * 3 + 1;
assert( t > n ); // over-flow除け
n = t;
} else {
n >>=1 ;
}
++count;
}
return count;
}
int main() {
integer max = 0;
for ( integer n = 2; n != 0; ++n) {
integer result = collatz(n);
if ( max <= result ) {
std::cout << "collatz(" << n << ") = "
<< result << std::endl;
max = result;
}
}
}