今回も他人様の動画をネタにしています。
コラッツの問題は数論の未解決問題のひとつです。1937年にローター・コラッツが問題を提示しました。
これは「任意の正の整数 n をとり、n が偶数の場合はnを2で割り、奇数の場合は3をかけて1を足すという操作を繰り返すと、有限回の操作のうちに必ず 1 に到達するというものです。これについては証明されていません。
「n が偶数の場合はnを2で割り、奇数の場合は3をかけて1を足す」。この操作をしているときに2のn乗になってしまうとあとは2で割り続けることになるので必ず1になります。だからコラッツ予想は正しそうです。現在では2の68乗まで反例がないことが確かめられています。
そこで任意の数を指定すればどのようにして1にたどり着くことができるかを出力するプログラムを作成してみたいと思います。
intやlongでは使えないような大きな数でも処理できるようにBigInteger型を使用しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
using System; using System.Text; using System.Windows.Forms; using System.Numerics; namespace WindowsFormsApp1 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { BigInteger i = 0; try { i = BigInteger.Parse(textBox1.Text); } catch { richTextBox1.Text = "入力されている値が不正です。"; return; } StringBuilder sb = new StringBuilder(); while(true) { if(i % 2 == 0) { sb.Append(String.Format("{0}÷2 = {1}\n", i, i / 2)); i /= 2; } else { sb.Append(String.Format("{0}×3 ＋1 = {1}\n", i, 3 * i + 1)); i = 3 * i + 1; } if(i == 1) break; } richTextBox1.Text = sb.ToString(); } } } |
動画によると27はけっこう大変なことになります。111回計算することになります。
27×3 ＋1 = 82
82÷2 = 41
41×3 ＋1 = 124
124÷2 = 62
62÷2 = 31
31×3 ＋1 = 94
94÷2 = 47
47×3 ＋1 = 142
142÷2 = 71
71×3 ＋1 = 214
214÷2 = 107
107×3 ＋1 = 322
322÷2 = 161
161×3 ＋1 = 484
484÷2 = 242
242÷2 = 121
121×3 ＋1 = 364
364÷2 = 182
182÷2 = 91
91×3 ＋1 = 274
274÷2 = 137
137×3 ＋1 = 412
412÷2 = 206
206÷2 = 103
103×3 ＋1 = 310
310÷2 = 155
155×3 ＋1 = 466
466÷2 = 233
233×3 ＋1 = 700
700÷2 = 350
350÷2 = 175
175×3 ＋1 = 526
526÷2 = 263
263×3 ＋1 = 790
790÷2 = 395
395×3 ＋1 = 1186
1186÷2 = 593
593×3 ＋1 = 1780
1780÷2 = 890
890÷2 = 445
445×3 ＋1 = 1336
1336÷2 = 668
668÷2 = 334
334÷2 = 167
167×3 ＋1 = 502
502÷2 = 251
251×3 ＋1 = 754
754÷2 = 377
377×3 ＋1 = 1132
1132÷2 = 566
566÷2 = 283
283×3 ＋1 = 850
850÷2 = 425
425×3 ＋1 = 1276
1276÷2 = 638
638÷2 = 319
319×3 ＋1 = 958
958÷2 = 479
479×3 ＋1 = 1438
1438÷2 = 719
719×3 ＋1 = 2158
2158÷2 = 1079
1079×3 ＋1 = 3238
3238÷2 = 1619
1619×3 ＋1 = 4858
4858÷2 = 2429
2429×3 ＋1 = 7288
7288÷2 = 3644
3644÷2 = 1822
1822÷2 = 911
911×3 ＋1 = 2734
2734÷2 = 1367
1367×3 ＋1 = 4102
4102÷2 = 2051
2051×3 ＋1 = 6154
6154÷2 = 3077
3077×3 ＋1 = 9232
9232÷2 = 4616
4616÷2 = 2308
2308÷2 = 1154
1154÷2 = 577
577×3 ＋1 = 1732
1732÷2 = 866
866÷2 = 433
433×3 ＋1 = 1300
1300÷2 = 650
650÷2 = 325
325×3 ＋1 = 976
976÷2 = 488
488÷2 = 244
244÷2 = 122
122÷2 = 61
61×3 ＋1 = 184
184÷2 = 92
92÷2 = 46
46÷2 = 23
23×3 ＋1 = 70
70÷2 = 35
35×3 ＋1 = 106
106÷2 = 53
53×3 ＋1 = 160
160÷2 = 80
80÷2 = 40
40÷2 = 20
20÷2 = 10
10÷2 = 5
5×3 ＋1 = 16
16÷2 = 8
8÷2 = 4
4÷2 = 2
2÷2 = 1
ただコンピュータでやれば一瞬です。ではほかにもっと大きな数でやればどうなるんだろうと思ってやってみましたが、100桁くらいの大きな値を入力しても意外に時間はかかりません。
9916081725728254857179771451445987297557896503245024278924562927（乱数で64桁の数を適当に作った）のような数を入れてもすぐに答えがでてしまいます（全部で1381回。結果を貼り付けようとしたけど文字数がいたずらに多くなるだけ（14万文字を超える）なのでやめる）。
