４．n と max(n) の関係

n と max(n) の関係

n と max(n) の間に何か関係はないか。

max(n) が n の何乗に相当するか、すなわち、

log_nmax(n) = log(max(n))/log(n)

を調べてみる。

n and max(n)

n	max(n)	lognmax(n)
27	9232	2.7702921473225270973
447	39364	1.7337985056559493653
639	41524	1.6461585349156394626
703	250504	1.8963468156818830341
1819	1276936	1.8731541446083022596
4255	6810136	1.8829828887954350854
4591	8153620	1.8873635826111263587
9663	27114424	1.8652425380222833139
20895	50143264	1.7824391362435275872
26623	106358020	1.8138540333287852068
31911	121012864	1.7946133377815046826
60975	593279152	1.8334338047327572736
77671	1570824736	1.8804991567712454073
113383	2482111348	1.858686744015530798
138367	2798323360	1.8375487515714095702
159487	17202377752	1.9673513229796590878
270271	24648077896	1.913138207015879498
665215	52483285312	1.8409910542107325618
704511	56991483520	1.8392640846708863322
1042431	90239155648	1.8204235434025088373
1212415	139646736808	1.8319641019342189245
1441407	151629574372	1.8154199184637089691
1875711	155904349696	1.7842439312671941191
1988859	156914378224	1.7774831929811105369
2643183	190459818484	1.7563967448581379868
2684647	352617812944	1.7961591030955438878
3041127	622717901620	1.8192547405182980373
3873535	858555169576	1.8114106722913689741
4637979	1318802294932	1.8181191024373793748
5656191	2412493616608	1.8337537269140500102
6416623	4799996945368	1.8628867257452770168
6631675	60342610919632	2.0201385540797855264
19638399	306296925203752	1.9862788884772012965
38595583	474637698851092	1.9345270521247527573
80049391	2185143829170100	1.9408813273460452312
120080895	3277901576118580	1.920372052693041628
210964383	6404797161121264	1.898859713255962811
319804831	1414236446719942480	2.1341290308817894479
1410123943	7125885122794452160	2.0605868024039021545
8528817511	18144594937356598024	1.939277301613860048

この計算結果を見ると、いくつか例外はあるがだいたい 2 弱ぐらいの値を示しているように見える。
すなわち、n に対する max(n) の値には上限値 s があって、ある値以上の n については、

Conjecture

max(n) ≤ n^s   (s=2+ε)

が成り立つのではないかという予想が立てられる。
もし、これが証明できるなら、任意の n の挙動が必ず n^s 以下におさまるということになり、
「任意の n は無限大に発散しない」ということを証明できる。
（ただし、ループの可能性は残る）

『計算の愉しみ』では、 n を 2 進数で表したときの下 k 桁の挙動に着目する、
という方法が紹介されているが、これは、今回の内容と本質的には同じである。

追補（2001/06/04）

Mark Gibson からの連絡により、Tomas Oliveira と Silva も同じ方針の計算、
n に対する最大値 max(n) の探査を進めていることが分かった (3x+1 conjecture verification results）。
彼らが得た結果は、以下のとおり。

n and max(n)  where n < 112589990684262400

n	max(n)	lognmax(n)
8528817511	18144594937356598024	1.939277301613860048
12327829503	10361199457202525864	1.8844141998050365199
23035537407	34419078320774113520	1.8853549708636835626
45871962271	41170824451011417002	1.8397507395602994688
51739336447	57319808570806999220	1.8441884552141065432
59152641055	75749682531195100772	1.845472385932052334
59436135663	102868194685920926084	1.8574519394374376045
70141259775	210483556894194914852	1.8738030346819725479
77566362559	458306514538433899928	1.8973164044963655153
110243094271	686226824783134190180	1.8869593030094581278
204430613247	707630396504827495544	1.8433952354124018303
231913730799	1095171911941437256778	1.8511991156920975808
272025660543	10974241817835208981874	1.9275143419327129426
446559217279	19766638455389030190536	1.9138338439360873776
567839862631	50270086612792993117994	1.9313317500585215646
871673828443	200279370410625061016864	1.9515029625083460762
2674309547647	385209974924871186526136	1.8979074422895333933
3716509988199	103968231672274974522437732	2.0697391100054868976
9016346070511	126114763591721667597212096	2.0147205198519785498
64848224337147	637053460104079232893133864	1.9406583879018438272
116050121715711	1265292033916892480613118196	1.9269728896148309796
201321227677935	2636975512088803001946985208	1.9170384364615899565
265078413377535	2857204078078966555847716826	1.903572671092275162
291732129855135	3537558936133726760243328464	1.9045097584416383577
394491988532895	6054282113227445504606919650	1.9033975039320943561
406738920960667	12800696705021228411442619682	1.923925399587870349
613450176662511	22881441742972862145992619776	1.917764852866688732
737482236053119	37684665798782446690107505928	1.922023282775447441
1254251874774375	1823036311464280263720932141024	2.0042405729079157097
5323048232813247	1964730439297455725829478995944	1.9263000122389505916
8562235014026655	13471057008351679202003944688336	1.9538196397458298822
10709980568908647	175294593968539094415936960141122	2.0114905542829812762
49163256101584231	301753104069007668258074264675786	1.9458633485710065322
82450591202377887	875612750096198197075499421245450	1.9473832303450652195
93264792503458119	2115362774686865777485863406680032	1.9638149196720639522

彼らの表では、log _n max(n) ではなく、 max(n)/n² が 1 に近いことを確認しているが、内容的には同じである。