No.308

$N$ が小さい ($N \lt 100$) ときは $W$ が小さい順に幅優先探索で到達できるかどうかを試す.

$N$ が大きい場合は以下の方法で求める.

1の右は2で素数なので, 最初は下に移動するしかない. 下も素数の場合は移動できないので $W+1$ は合成数である必要がある.

$W+1$ が合成数の場合を挙げてみると,

$W=3$ のとき:

1	2	3
4	5	6
7	8	9

$W=5$ のとき:

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

$W=7$ のとき:

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

$W=8$ のとき:

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
49	50	51	52	53	54	55	56

$W=9$ のとき:

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

$W=11$ のとき:

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

$W=13$ のとき:

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	49	50	51	52
53	54	55	56	57	58	59	60	61	62	63	64	65

$W=14$ のとき:

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	49	50	51	52	53	54	55	56
57	58	59	60	61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80	81	82	83	84
85	86	87	88	89	90	91	92	93	94	95	96	97	98

となる.

$W = 8, 14$ のとき以外は途中に壁があるので外には出られない.

$W = 8, 14$ のときは偶数が縦に並ぶので, その偶数の列すべてに行くことができれば, すべての合成数に到達できる. したがって $N$ がある程度より大きければ, $W = 8$ が最小となる.

ただし, $W = 8$ の場合でも, 下のように $N = 8k+1$ で $N-8$ が素数の場合は到達できない.

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
49

この場合は $W = 14$ が最小となる.

$N = 14m+1$ で $N - 14$ が素数の場合も到達できないが, $N = 8k+1$ かつ $N = 14m+1$ の場合, $N = 56n+1$ となり, $N-8=56n-7$ は $7$ で割り切れるため合成数となるので, $N = 8k+1$ で $N-8$ が素数である場合, $N = 14m+1$ とはなりえないので, $W=14$ で到達できる.

$N-8$ が素数かどうかの判定であるが, $N$ が小さい ($N \lt 10^8$) 場合は $\sqrt{N}$ までの試し割りで判定し, $N$ が大きい場合はミラー=ラビン法で判定する.

D言語の場合は大きな数の乱数を求めるのに手間がかかるので, ここは GMP の乱数判定(ミラー=ラビン法を使っている)関数を使う.