循環する整数

 簡単な数字の計算をしてみましょう.適当な2つの数字を思い浮かべます.どんな数字でもいいです.2番目の数字に1を足して,1番目の数字で割ります.出てきた数字にまた1を足して,その前の数字で割ります.その操作を繰り返していきます.
   x,y,(y+1)/x,・・・
 例えば最初の2つの数字を 2と5だとします.次の数字を計算していきましょう.
   (5+1)÷2=3
   (3+1)÷5=0.8
   (0.8+1)÷3=0.6
   (0.6+1)÷0.8=2
   (2+1)÷0.6=5
これらの数字を並べると,
   ,3,0.8,0.6,,3,・・・・
となり,最初の2つの数字が何度も繰り返されるのがわかりますね.どんな数字を選んでもなるのでしょうか?違う数字で試してみましょう.
   10,11/3,7/15.2/5,10,・・・
   −4,−2,−1/7,−3/7,−4,・・・
 色々な数字で試しても,やはり同様な結果が得られます.これは最初の数字をa1=x,a2=yとして,次の数を計算してみればわかります.
   a3=(y+1)/x
   a4={(y+1)/x+1}/y=(x+y+1)/xy
   a5={(x+y+1)/xy+1}/{(y+1)/x}=(x+1)/y
   a6={(x+1)/y+1}/{(x+y+1)/xy}=x
 6項目で最初の数字と同じになるのがわかりますね.

 それでは次に,次の様な数の並びを考えてみましょう.

ある数xある数xが
もし偶数なら半分に
奇数なら3倍して1を足す
その数字が
もし偶数なら半分に
奇数なら3倍して1を足す
→・・・

 例えば 11 で出発してみましょう.
  11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4 2 1
最後に 4 2 1 で循環してしまいましたね.偶然でしょうか?違う数字で試してみましょう.
  19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4 2 1
  40 20 10 5 16 8 4 2 1 4 2 1
どうですか? どれも“4,2,1”のループができますね.もっと大きな数で試してみましょう.そのために簡単なプログラムを作成して,コンピュータに計算させてみます.この程度のプラグラムであれば,センター試験に出てもおかしくない問題ですね.次のプログラム例は十進BASICを用いていますが,MOD( x , 2)は2で割ったときの余りを表しています.

input PROMPT  "X=":x
do
   print x;
   if x=1 then exit do
   if MOD( x , 2) =0 then
      LET  x=x/2
   else
      LET  x=3*x+1
   end if 
loop
END
 これをもとに大きな数で計算させて見ましょう.

X=12345
  12345  37036  18518  9259  27778  13889  41668  20834  10417  31252
  15626  7813  23440  11720  5860  2930  1465  4396  2198  1099  3298
  1649  4948  2474  1237  3712  1856  928  464  232  116  58  29  88
  44  22  11  34  17  52  26  13  40  20  10  5  16  8  4  2  1
X=87453
  87453  262360  131180  65590  32795  98386  49193  147580  73790
  36895  110686  55343  166030  83015  249046  124523  373570  186785
  560356  280178  140089  420268  210134  105067  315202  157601  472804
  236402  118201  354604  177302  88651  265954  132977  398932  199466
  99733  299200  149600  74800  37400  18700  9350  4675  14026  7013
  21040  10520  5260  2630  1315  3946  1973  5920  2960  1480  740  370
  185  556  278  139  418  209  628  314  157  472  236  118  59  178  89
  268  134  67  202  101  304  152  76  38  19  58  29  88  44  22  11  34
  17  52  26  13  40  20  10  5  16  8  4  2  1 
X=987654
  987654  493827  1481482  740741  2222224  1111112  555556  277778
  138889  416668  208334  104167  312502  156251  468754  234377  703132
  351566  175783  527350  263675  791026  395513  1186540  593270  296635
  889906  444953  1334860  667430  333715  1001146  500573  1501720
  750860  375430  187715  563146  281573  844720  422360  211180  105590
  52795  158386  79193  237580  118790  59395  178186  89093  267280
  133640  66820  33410  16705  50116  25058  12529  37588  18794  9397
  28192  14096  7048  3524  1762  881  2644  1322  661  1984  992  496
  248  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 

 やはりどれも“4,2,1”のループが出てきますね.実はこの問題,最初の例と違って証明されていません.コンピュータではかなり大きな数まで確かめられているのですが,きちんとした証明はなされていないのです.誰かチャレンジしてみてはいかがですか?