タイトルがわかりにくいが、
自然数を1つ選んで、例えば3とすると、
奇数だから3かけて1たして、10、
偶数だから2で割って、5、
奇数だから3かけて1たして、16、
あとは、8→4→2、
のようにしていくと、いつか必ず1になる。
7だと、
7→22→11→34→17→52→26→13→40→20→10→5→…→1
このようにループせずに1を根とするツリー状になる。
というのは、確か証明されていなかった、はず。
が、1億まで試したら、確かに常に1になった。
はじめる自然数によって何回で1に到達するかはそれぞれだが、
だいたいの傾向としては、小さい数からはじめたほうが少ない回数だろう。
そこで、1から1億まで、何回かかるか数えて、
それまでの最大の回数を拾ってみた。
最初のほうは、
2 1
3 7
6 8
7 16
9 19
18 20
25 23
27 111
27は非常に長いが、どう辿って1に到達するかというと、
27→82→41→124→62→31→94→47→142→71→214→107→322→161→
484→242→121→364→182→91→274→137→412→206→103→310→155→
466→233→700→350→175→526→263→790→395→1186→593→1780→
890→445→1336→668→334→167→502→251→754→377→1132→566→
283→850→425→1276→638→319→958→479→1438→719→2158→1079→
3238→1619→4858→2429→7288→3644→1822→911→2734→1367→4102→
2051→6154→3077→9232→4616→2308→1154→577→1732→866→433→
1300→650→325→976→488→244→122→61→184→92→46→23→70→35→
106→53→160→80→40→20→10→5→16→8→4→2→1
元に戻って最大の回数をグラフにすると、
logになるかと思ったが、これを見るかぎりではそうではなさそう。
ちょっとデータが少なすぎる。
#includeusing namespace std;
int calc_length(int m);
void main() {
const int N = (int)1e8;
int max_length = 0;
for(int i = 1; i <= N; i++) {
int length = calc_length(i);
if(length > max_length) {
max_length = length;
cerr << i << " " << length << endl;
cout << i << " " << length << endl;
}
}
}int calc_length(int m) {
const __int64 limit = 0x2AAAAAAAAAAAAAAA;
__int64 n = m;
int len;
for(len = 0; n != 1; len++) {
if(n & 1) {
if(n > limit) {
cerr << "overflow." << endl;
exit(1);
}
n = n * 3 + 1;
}
else {
n /= 2;
}
}
return len;
}
