３．探査不要の n

探査不要の n

前ページのプログラムにより、

an+b   (a=2^k, b=1, 3, ... , a-1)

の形の数について、どのくらいふるい落とせるかを調べてみる。
実行結果は以下のとおり。

探査不要となる数の比率

k	a	探査不要	比率(%)
2	4	3	75.00
3	8	6	75.00
4	16	13	81.25
5	32	28	87.50
6	64	56	87.50
7	128	115	89.84
8	256	237	92.58
9	512	474	92.58
10	1024	960	93.75
11	2048	1920	93.75
12	4096	3870	94.48
13	8192	7825	95.52
14	16384	15650	95.52
15	32768	31473	96.05
16	65536	63422	96.77
17	131072	126844	96.77
18	262144	254649	97.14
19	524288	509298	97.14
20	1048576	1021248	97.39

2²⁰+b (b=1, ... , 2²⁰-1) の場合、 対象となる式 2²⁰=1048576 個のうち、
1021248 個は探査不要、27328個だけ調べればよいことがわかる。
これは大変な効率化である。

n と最大値 max(n)

n に対する最大値 max(n) を求めてみる。
オリジナルの a よりも小さくならなかった時の b を格納するための配列 diff%() を確保する。
個数は例えば a=8192のとき、上の計算より 8192-7825=367個とればよい。
この配列を利用して、

n = L * a + diff%(j)   (L=0, 1, ..., J=0, 1, ... , 367)

の式で表される n について調べていく。1.14×10¹⁰以下の n に対する実行結果は以下のとおり。

n と max(n)

n	max(n)
27	9232
447	39364
639	41524
703	250504
1819	1276936
4255	6810136
4591	8153620
9663	27114424
20895	50143264
26623	106358020
31911	121012864
60975	593279152
77671	1570824736
113383	2482111348
138367	2798323360
159487	17202377752
270271	24648077896
665215	52483285312
704511	56991483520
1042431	90239155648
1212415	139646736808
1441407	151629574372
1875711	155904349696
1988859	156914378224
2643183	190459818484
2684647	352617812944
3041127	622717901620
3873535	858555169576
4637979	1318802294932
5656191	2412493616608
6416623	4799996945368
6631675	60342610919632
19638399	306296925203752
38595583	474637698851092
80049391	2185143829170100
120080895	3277901576118580
210964383	6404797161121264
319804831	1414236446719942480
1410123943	7125885122794452160
8528817511	18144594937356598024

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