今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(4)～世界記録に挑む

0. はじめに

これまで一般化したビリヤード問題について独自の検討を行ってきた。

• 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(1)～導入編 - Qiita
• 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(2)～計算機を使う - Qiita
• 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(3)～計算量オーダーを考える - Qiita

しかし，一般化したビリヤードの問題についてネットを検索してみるとボールの個数 $n = 20$ あるいは $n = 30$ における解を得ることに成功した人がいるようだ。残念ながら現在はリンクが切れていて詳しい内容は辿れない。

自分の場合 $n = 17$ ですら二週間を費やした。$n = 20$ となるとその1000倍の時間を要する見込みになるが，アルゴリズム自体は非常に並列化が効き，マルチスレッド化してさらに最新の PC を複数台使えば数十倍は速くなるはずで，$n = 20$ までは力技で何とかなると思うが $n = 30$ に至っては絶望的である。

探索アルゴリズム自体，あるいはアプローチ自体が違うのかもしれない。ということで先行研究をリサーチしてみる。

そして目標は一般化したビリヤードの問題の世界記録更新である！

1. モジュラーゴロム定規（分度器）

英語だと Circular Golomb Ruler あるいは Modular Golomb Ruler（CGR/MGR）と呼ぶらしい。いわゆるゴロム定規の両端を繋いだバージョンである。下図は目盛が五つの場合であり，長さ $21$ の円周上に起点から長さ $0$, $5$, $6$, $9$, $19$ の位置に目盛を入れると $360/21$ 度の整数倍（$1$ ～ $21$ 倍まで）の角度を測ることができるというものだが，目盛と目盛の間隔を測ると $\lbrace 5, 1, 3, 10, 2 \rbrace$ となり，五つの玉のビリヤードの問題の解 $\lbrace 1, 3, 10, 2, 5 \rbrace$ と全く同じであることが分かる。

日本語だと「魔円陣」とも呼ぶらしい。詳しくは参考文献を参照のこと。

2. 完全差集合 Perfect Difference Set (PDS)

そして，この完全なモジュラーゴラム定規が存在する条件として完全差集合という概念が出てくる。$0$ 以上かつ $m$ より小さい純単調増加の整数列 $a_i$ において，すべての $i \ne j$ において $(a_i - a_j) \bmod m$ が重複しないで $1$ から $m - 1$ の自然数を網羅する場合，これらの数列を完全差集合と呼ぶようだ。一例として，法を$21$とする場合の完全差集合は $a_i = \lbrace 0, 5, 6, 9, 19, (21) \rbrace$ となる。試しに差を $21$ で割った余りを求めてみると，対角項を除けば見事に重ならないことが分かる。

表１　差の演算表

	0	5	6	9	19
0	0	16	15	12	2
5	5	0	20	17	7
6	6	1	0	18	8
9	9	4	3	0	11
19	19	14	13	10	0

3. 解が存在する条件

完全差集合が存在する条件はビリヤードの問題の解が存在する条件と等しいと思われる。ボールの数を $n$ 個とすると，$n - 1$ が素数または素数のべき乗であるときに解を持つと予想されている。実際 $n \le 17$ の範囲までは自分も計算できており，確かに解の有無についての予想は正しいようだ。ただ $n \ge 18$ については確かめようがない。

表２　ボールの個数 $n$ と解の有無の関係

$n$	$n - 1$	解の有無		$n$	$n - 1$	解の有無
3	2	○		18	17	○
4	3	○		19	2×3²	×
5	2²	○		20	19	○
6	5	○		21	2²×5	×
7	2×3	×		22	3×7	×
8	7	○		23	2×11	×
9	2³	○		24	23	○
10	3²	○		25	2³×3	×
11	2×5	×		26	5²	○
12	11	○		27	2×13	×
13	2²×3	×		28	3³	○
14	13	○		29	2²×7	×
15	2×7	×		30	29	○
16	3×5	×		31	2×3×5	×
17	2⁴	○		32	31	○

4. 完全差集合の作り方

なんと参考文献のサイトに完全差集合の作り方が書いてある。

まず初項 $(t_0,t_1,t_2) = (0,0,1)$ としてトリボナッチ数列の一般項 $t_i$（$i \ge 3$）を

t_i = \left( A \cdot t_{i - 3} + B \cdot t_{i - 2} + C \cdot t_{i - 1} \right) \bmod p

と定義する。数列 $t_i$ が $0$ になる番号 $i$ の数列 $u_j$ を作る。二回連続で $0$ になると終了とする。一例として $(A,B,C) = (1,1,1)$ における $p = 3$ の計算例を示す。

表３　トリボナッチ数列の計算例（$p = 3$）

$i$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$
$t_i$	$0$	$0$	$1$	$1$	$2$	$1$	$1$	$1$	$0$	$2$	$0$	$2$	$1$	$0$	$0$
$u_j$	$u_0$	$u_1$							$u_2$		$u_3$			$u_4$	$u_5$

数列 $u_j = \lbrace 0, 1, 8, 10, 13, 14 \rbrace$ に対して差分 $v_j = u_{j + 1} - u_j$ を取ると $v_j = \lbrace 1, 7, 2, 3, 1 \rbrace$ となる。分かり易く順番をひっくり返して最後の $1$ を取り除くと $\lbrace 1, 3, 2, 7 \rbrace$ となる。これはボールが四個のときのビリヤード問題の解二つのうちの一つに当たる。

ビリヤード問題に置き換えると，素数 $p$ に対してボールの個数 $n = 1 + p$ のとき，ボールの数値の総和 $\sigma = n(n - 1) + 1 = p(p + 1) + 1$ としてトリボナッチ数列 $t_i$ を作り，トリボナッチ数列 のパラメータ $(A,B,C)$ を上手く選ぶと周期 $\sigma$ で繰り返す周期数列が得られる。$t_i = 0$ となる位置 $i$ を一周期分 $\sigma$ だけ読み取ると完全差集合 $u_j$ が得られる。ビリヤード問題の解は完全差集合の差分 $v_j = u_{j + 1} - u_j$ として得られる。なお，トリボナッチ数列のパラメータ $(A,B,C)$ について特に設計方法は無いようで $0 \le A,B,C < p$ の範囲でしらみつぶしに調べる必要があるようだ。

本来（狭義の）トリボナッチ数列とは，初項 $t_0 = 0, t_1 = 0, t_2 = 1$，一般項（$i \ge 3$）を $t_i = t_{i - 3} + t_{i - 2} + t_{i - 1}$ と定義し，

t_i = \lbrace 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, \cdots \rbrace

と無限大に発散する数列のことを言う。本記事では，広義のトリボナッチ数列を再定義したと解釈されたい。

5. 実装コード

実装コードを以下に示す。トリボナッチ数列のパラメータ $(A,B,C)$ を全探索しながら解を求める。さほどスピードを問われないこと（あっという間に計算が終わること）や重複する解を除去したり，見やすいようにソートしたいこともあって小回りが利く JavaScript（WSH）で作成した。

OnePlusPrime1.js

var	args = WScript.Arguments.Unnamed;
var	ret = main(args)
try {
	WScript.Quit(ret);
} catch(e) {
	/* 何もしない */
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main(args) {
	//--------------------------------------------------------------------------
	// ヘルプメッセージ
	//--------------------------------------------------------------------------
	if(args.Count == 0) {
		WScript.Echo("Usage: OnePlusPrime1(.js) [prime-number]");
		return false;
	}
	var	p = parseInt(args(0));
	//--------------------------------------------------------------------------
	// トリボナッチ数列のパラメータ (a,b,c) を全探索する
	//--------------------------------------------------------------------------
	var	r = p * (p + 1) + 1;
	var	d = [];
	for(var a = 0; a < p; a++) {
		for(var b = 0; b < p; b++) {
			for(var c = 0; c < p; c++) {
				//--------------------------------------------------------------
				// トリボナッチ数列より完全差集合を作成する
				//--------------------------------------------------------------
				var	s = [];
				s.push(0); s.push(0); s.push(1);
				for( i = 3; i < r + 2; i++) {
					var	q = (a * s[i - 3] + b * s[i - 2] + c * s[i - 1]) % p;
					s.push(q);
					if(q == 0 && s[i - 1] == 0) break;
				}
				if(i == r) continue;
				var	t = [];
				for(var i = 0; i < s.length; i++)
					if(s[i] == 0) t.push(i);
				//--------------------------------------------------------------
				// 完全差集合をボール配置に変換する
				//--------------------------------------------------------------
				var	u = [];
				for(var i = 1; i < t.length; i++)
					u.push(t[i] - t[i - 1]);
				//--------------------------------------------------------------
				// ボール配置を左右反転する
				//--------------------------------------------------------------
				if(u[1] > u[u.length - 2]) u.reverse();
				u.pop();
				//--------------------------------------------------------------
				// ボール配置のチェック＆重複するボール配置を取り除く
				//--------------------------------------------------------------
				if(!check(u)) continue;
				var	k = [a, b, c].join(" ")
				var	v = u.join(" ");
				if(d[v] == null) d[v] = k;
			}
		}
	}
	//--------------------------------------------------------------------------
	// ボール配置をソートして出力する
	//--------------------------------------------------------------------------
	var	e = [];
	for(var v in d)
		e.push({ key:d[v], val:v, arr:v.split(" ") });
	e.sort(function(a, b) {
		for(var i = 0; i < a.arr.length; i++)
			if(a.arr[i] != b.arr[i]) return a.arr[i] - b.arr[i];
		return 0;
	});
	for(var i = 0; i < e.length; i++)
		WScript.Echo([p, e[i].key, e[i].val].join("\t"));
	//--------------------------------------------------------------------------
	// 解の個数を出力する
	//--------------------------------------------------------------------------
	WScript.Echo(e.length);
	return true;
}
//------------------------------------------------------------------------------
// ボール配置のチェック
//------------------------------------------------------------------------------
function check(ball) {
	var	num = ball.length;
	var	sum = num * (num -  1) + 1;
	for(var i = 0, s = 0; i < ball.length; i++)
		s += ball[i];
	if(sum != s) return false;
	var	flag = [];
	for(var i = 0; i <= sum; i++)
		flag.push(false);
	for(var i = 0; i < ball.length - 1; i++) {
		for(var j = 0, s = 0; i + j >= 0; j--) {
			s += ball[i + j];
			if(flag[s] || flag[sum - s]) return false;
			flag[s] = true;
			flag[sum - s] = true;
		}
	}
	return true;
}

6. 実行例

コマンドラインから実行する。引数はボールの個数 $n$ ではなく，それから１を引いた $n - 1$ を与える。$n - 1$ は素数でなくてはならない。

ボールの個数 $n = 20$ のときの実行結果を以下に示す。最初の $19$ はボールの個数 $20$ から１を引いた数であり，素数である条件を満たしている。続く三つの数値はトリボナッチ数列のパラメータ $(A,B,C)$ であり，その次の数列がボールの配置となる。最後の行の $42$ が解の個数である。

ボールの個数が20個の場合の実行例

OnePlusPrime1 19
19	2 0 10	1 2 9 5 48 10 19 23 7 8 13 18 4 33 71 26 6 34 20 24
19	4 0 4	1 2 10 15 23 14 17 4 18 8 33 56 11 5 24 20 46 32 36 6
19	2 0 4	1 2 40 6 14 47 5 7 9 8 10 77 31 33 11 26 4 15 13 22
19	2 4 8	1 3 5 12 11 26 61 24 10 56 6 7 33 2 36 15 14 16 25 18
19	2 2 2	1 3 18 25 14 20 30 5 31 2 11 29 12 51 32 26 48 8 9 6
19	2 2 6	1 3 23 19 2 14 17 24 36 13 7 8 10 12 59 11 54 29 34 5
19	2 8 13	1 3 48 10 2 20 47 23 8 18 7 86 21 6 9 19 11 5 24 13
19	2 8 1	1 4 3 38 42 20 6 48 16 9 47 19 11 33 32 2 15 12 10 13
19	2 10 4	1 4 14 10 7 6 3 48 2 32 43 12 15 46 8 30 22 11 47 20
19	2 1 4	1 4 16 6 43 7 37 3 11 17 24 12 30 32 57 2 46 15 10 8
19	2 5 7	1 4 17 52 15 10 13 3 8 19 12 6 14 44 2 70 9 47 7 28
19	2 8 8	1 5 19 7 40 28 8 12 10 23 16 18 3 14 27 2 9 4 50 85
19	2 5 6	1 5 24 2 21 15 18 43 28 65 7 12 8 14 3 57 9 4 35 10
19	2 8 18	1 6 3 28 14 4 12 17 24 36 50 26 39 5 20 2 13 8 11 62
19	2 8 15	1 6 4 12 26 21 20 5 9 91 19 8 29 2 13 30 32 3 33 17
19	2 8 6	1 7 3 57 9 17 22 5 35 2 21 15 14 4 16 12 13 6 24 98
19	2 2 12	1 7 24 5 21 14 9 2 52 13 3 17 10 12 6 41 15 4 34 91
19	2 4 7	1 7 33 3 26 16 14 9 12 25 27 11 20 96 10 5 13 4 2 47
19	2 5 4	1 7 45 48 47 17 3 13 26 12 18 10 4 5 6 35 27 34 2 21
19	2 4 5	1 7 69 48 6 18 10 27 19 41 25 4 11 2 3 33 14 12 9 22
19	2 5 16	1 9 14 18 11 5 3 17 13 26 44 2 4 65 15 12 28 7 66 21
19	2 2 15	1 10 22 13 25 18 12 39 3 37 4 20 96 6 2 7 14 5 31 16
19	2 8 2	1 11 26 24 32 8 13 6 9 5 2 23 42 4 70 10 44 3 31 17
19	2 1 15	1 12 3 5 24 30 7 4 6 36 14 38 26 23 2 33 22 68 9 18
19	2 10 11	1 12 51 35 14 65 4 5 6 22 34 25 23 7 17 3 16 2 8 31
19	2 8 3	1 13 15 31 39 11 68 23 21 3 2 7 10 8 37 16 4 32 6 34
19	2 2 14	1 14 7 5 19 10 6 2 36 39 11 9 23 25 3 30 72 4 13 52
19	2 5 8	1 14 16 20 17 7 3 2 6 46 38 4 19 9 13 21 48 39 33 25
19	2 2 11	1 16 22 33 91 2 7 5 6 41 15 28 8 24 3 10 21 19 4 25
19	2 2 4	1 16 35 23 4 15 11 29 10 18 3 64 6 66 34 2 7 5 8 24
19	2 5 1	1 18 7 2 8 6 71 5 33 22 29 37 3 12 49 4 30 13 11 20
19	2 5 17	1 18 7 6 16 38 24 3 9 5 23 33 2 8 34 11 4 89 30 20
19	2 1 16	1 18 15 10 7 23 8 4 24 13 16 46 22 47 9 2 3 87 6 20
19	2 2 7	1 18 28 32 52 6 55 11 14 2 13 22 54 5 4 8 26 7 3 20
19	2 4 11	1 18 35 9 2 14 13 82 43 7 8 22 4 6 49 12 5 28 3 20
19	2 5 12	1 22 7 3 6 15 19 26 11 14 27 88 4 8 5 42 2 18 28 35
19	2 10 5	1 22 9 8 64 12 43 25 2 19 7 30 5 6 4 14 20 13 3 74
19	2 4 16	1 22 18 46 17 2 28 3 6 5 10 38 7 13 12 4 72 43 8 26
19	2 1 2	1 23 17 2 8 3 25 20 14 12 6 15 16 60 5 4 35 22 7 86
19	2 8 16	1 28 11 23 8 36 16 9 57 7 72 12 2 4 15 5 17 10 3 45
19	2 4 3	1 28 50 23 13 6 2 3 9 18 16 15 22 4 55 7 10 35 25 39
19	2 1 18	1 66 9 8 33 2 3 18 7 19 13 29 11 34 14 6 4 12 15 77
42

恐ろしいことに，この結果は１秒程度で出てくる。Chakra エンジンを使えばさらに一桁速くなるが，この程度のボールの個数では必要ないくらいだ。

これを見ると $A = 2$ のときしか解を持たないように見えるが，重複解は早着順のため $A \ge 3$ 以降に解が存在しても $A = 2$ のときの解が優先されるためである。ただ $A = 0$ や $A = 1$ のときに解を持たないことだけは言える。

7. 実行結果

$n < 100$ において，ボールの個数 $n$ と解の個数の関係を調べた。なお，計算にはメインノート PC（i5-1135G7，Tiger Lake，2.4GHz／4.2GHz）を使用した。計算時間の単位は秒である。

表４　解の個数と計算時間

$n$	$n - 1$	解の個数	計算時間
3	2	1	0.039
4	3	2	0.040
6	5	5	0.043
8	7	6	0.048
12	11	18	0.048
14	13	20	0.053
18	17	51	0.078
20	19	42	0.079
24	23	78	0.144
30	29	132	0.357
32	31	110	0.409
38	37	132	0.722
42	41	287	1.320
44	43	210	1.477
48	47	360	2.810
54	53	408	4.300
60	59	590	8.320
62	61	384	7.330
68	67	420	10.460
72	71	852	19.280
74	73	600	19.610
80	79	588	23.510
84	83	1,098	39.090
90	89	1,335	52.730
98	97	1,056	70.660

解の個数はボールの個数 $n$ の二乗に比例するようである。

本記事の結果は，あくまでボールの個数 $n$ が「１＋素数」で表される数のときであり，「１＋素数のべき乗」の場合はどうなるか分からないが，なんとなく解の個数はずっと少ないような感じがする。

また計算時間はボールの個数 $n$ の五乗に比例するようだ。JavaScript プログラムは最初に JIT コンパイラによるコンパイルを要するため，計算時間が極めて短いケースでは明確な関係が見えにくい。このため計算時間が１秒未満のケースを除いて近似曲線を描いた。

計算量はトリボナッチ数列のパラメータ $(A,B,C)$ の探索空間の広さ $p^3$ とトリボナッチ数列の長さ $\sigma$ の積に比例すると考えられる。$n$ が十分大きくなれば計算量は $O(n^5)$ に近づくと考えられる。

p^3 \cdot \sigma = (n - 1)^3 \lbrace n(n - 1) + 1 \rbrace \sim n^5

ボールの個数 $n$ が増えれば加速度的に計算時間が増えるが，それでも多項式時間 $O(n^5)$ で増加するので，前回のようにボールが１個増えるたびに計算時間が十倍になる $O(10^n)$ よりは随分マシになった。

8. まとめ

ああ，そうだ！世界記録を狙うと言っていたので（そもそも元の記録を知らないが）いちおう自己最高到達点を残しておこう。下記のスクリプトは世界記録挑戦用に作成したものであり，素数およびトリボナッチ数列のパラメータ $A,B,C$ を指定し，解を発見したときのみボールの配置を出力する。

OnePlusPrimeWR.js（世界記録挑戦用）

var	args = WScript.Arguments.Unnamed;
var	opts = WScript.Arguments.Named;
var	ret = main(args, opts)
try {
	WScript.Quit(ret);
} catch(e) {
	/* 何もしない */
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main(args, opts) {
	//--------------------------------------------------------------------------
	// ヘルプメッセージ
	//--------------------------------------------------------------------------
	if(args.Count == 0) {
		WScript.Echo("Usage: OnePlusPrimeWR(.js) (option) [prime-number]");
		WScript.Echo("option:");
		WScript.Echo("/A:[n] Tribonacci Sequence Factor A (default: 1)");
		WScript.Echo("/B:[n] Tribonacci Sequence Factor B (default: 1)");
		WScript.Echo("/C:[n] Tribonacci Sequence Factor C (default: 1)");
		return false;
	}
	//--------------------------------------------------------------------------
	// コマンドライン解析
	//--------------------------------------------------------------------------
	var	p = parseInt(args(0));
	var	a = opts.Exists("A") ? parseInt(opts("A")) : 1;
	var	b = opts.Exists("B") ? parseInt(opts("B")) : 1;
	var	c = opts.Exists("C") ? parseInt(opts("C")) : 1;
	//--------------------------------------------------------------------------
	// トリボナッチ数列より完全差集合を作成する
	//--------------------------------------------------------------------------
	var	r = p * (p + 1) + 1;
	var	s = [];
	s.push(0); s.push(0); s.push(1);
	for(i = 3; i < r + 2; i++) {
		var	q = (a * s[i - 3] + b * s[i - 2] + c * s[i - 1]) % p;
		s.push(q);
		if(q == 0 && s[i - 1] == 0) break;
	}
	if(i == r) return false;
	var	t = [];
	for(var i = 0; i < s.length; i++)
		if(s[i] == 0) t.push(i);
	//--------------------------------------------------------------------------
	// 完全差集合をボール配置に変換する
	//--------------------------------------------------------------------------
	var	u = [];
	for(var i = 1; i < t.length; i++)
		u.push(t[i] - t[i - 1]);
	//--------------------------------------------------------------------------
	// ボール配置を正規化（左右対称）
	//--------------------------------------------------------------------------
	if(u[1] > u[u.length - 2]) u.reverse();
	u.pop();
	//--------------------------------------------------------------------------
	// ボール配置のチェック＆出力
	//--------------------------------------------------------------------------
	if(check(u)) WScript.Echo([p, u.join(" ")].join("\t"));
	return true;
}
//------------------------------------------------------------------------------
// ボール配置のチェック
//------------------------------------------------------------------------------
function check(ball) {
	var	num = ball.length;
	var	sum = num * (num -  1) + 1;
	for(var i = 0, s = 0; i < ball.length; i++)
		s += ball[i];
	if(sum != s) return false;
	var	flag = [];
	for(var i = 0; i <= sum; i++)
		flag.push(false);
	for(var i = 0; i < ball.length - 1; i++) {
		for(var j = 0, s = 0; i + j >= 0; j--) {
			s += ball[i + j];
			if(flag[s] || flag[sum - s]) return false;
			flag[s] = true;
			flag[sum - s] = true;
		}
	}
	return true;
}

上記のスクリプトは下記のバッチファイルと組み合わせて使う。下記のバッチファイルは 1000 以下の素数を全探索するものである。

gogoWR.cmd（1000未満の素数を全探索するバッチファイル）

@echo off
rem ----------------------------------------------------------------------------
rem トリボナッチ数列のパラメータ (A,B,C)=(1,0,1) 固定で 1000 以下の素数を探索する
rem ----------------------------------------------------------------------------
for %%I in (
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311
313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431
433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557
563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661
673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937
941 947 953 967 971 977 983 991 997) do OnePlusPrimeWR %%I /A:1 /B:0 /C:1

上記のバッチファイルを用いて得られた最大素数 $p = 977$，すなわちボールの個数 $n = 978$ のときの解を以下に示す。おそらく一般化したビリヤードの問題としてはボールの個数最大，すなわち世界記録を達成したのではないかと思う。ちなみに解はこれ以外におそらく十万個くらいあるはずだ。

$n = 978$ のときの解の一つ

1 2 5 1653 820 269 465 2397 747 724 495 4 568 1024 818 1194 76 187 1104 1075 13 1112 405 219 297 1812 2539 835 9 452 1421 398 1391 222 4349 126 1086 247 237 629 2800 634 251 983 1659 291 146 285 1068 417 240 372 61 907 506 24 1527 46 154 937 3537 575 2676 93 116 295 272 2440 807 36 403 767 153 1100 540 125 1788 307 3937 664 357 456 719 1312 501 4812 364 311 581 447 303 929 707 732 1290 1519 2976 1430 377 604 756 259 1880 679 2294 1808 476 469 1102 250 341 368 1375 134 2525 11 22 2078 758 1161 791 281 169 1150 706 1285 444 466 274 186 1351 996 1040 918 590 367 244 17 3211 3129 94 89 681 1608 933 399 207 1193 2793 306 573 361 167 3836 1074 743 157 489 797 613 688 858 345 662 32 78 1754 451 310 783 854 771 816 2184 1186 161 1013 954 1254 470 552 502 1673 201 1361 2019 579 787 213 927 246 199 387 2209 84 513 1324 388 833 943 1666 2726 1181 736 21 3052 1520 510 1553 984 140 280 276 759 1505 63 355 407 1198 972 80 1672 1683 225 324 913 578 1079 1213 693 410 25 5570 3102 3419 2740 455 194 337 2709 1380 2645 468 397 315 163 806 672 810 168 1480 1504 27 7464 1401 5517 179 111 254 220 2090 127 79 256 170 890 821 4430 180 1909 2069 406 151 789 727 473 1288 1188 121 408 101 3656 107 3250 316 287 2781 748 698 241 1249 553 680 218 96 404 735 39 97 902 1177 1634 65 1428 525 811 3329 98 1994 965 416 1588 908 1442 340 38 1133 106 800 596 130 100 204 29 56 4031 640 394 521 239 602 1252 1363 652 195 58 1968 685 784 252 132 196 1230 2028 2864 44 114 479 720 131 231 1616 224 159 215 1225 641 620 623 874 77 2825 887 1151 115 1258 1945 942 145 682 432 1250 319 1308 1742 35 1728 3202 1746 2076 1602 62 956 271 716 982 147 1062 1857 28 1354 731 385 92 2813 618 569 1064 359 1894 1529 1084 188 334 1276 909 267 1747 371 819 1003 1077 1179 88 2493 14 1590 2024 203 1044 278 626 1083 721 1306 308 395 1431 601 430 655 1635 3346 828 453 458 690 48 916 189 1025 438 589 1781 119 2431 850 1037 895 2349 150 794 155 952 668 1023 490 555 848 1257 1376 1001 2169 193 483 99 427 436 621 2142 1388 1126 2380 1207 2833 348 2356 619 198 725 4218 1855 1611 59 43 515 1162 1506 938 113 1355 1535 523 1715 1905 124 2155 588 577 191 1744 677 4192 663 45 1515 493 963 4917 336 446 714 380 255 1055 1049 16 2083 402 143 518 985 654 69 1069 86 1408 216 919 202 3340 587 1851 2365 2094 400 40 980 2555 68 347 1338 292 284 323 536 2684 733 184 467 1598 1963 1550 279 390 897 294 64 2446 823 1449 352 23 137 162 379 332 1806 182 642 1479 133 4095 503 238 1334 75 1163 2246 1470 296 1326 1942 118 1533 457 2348 286 574 128 487 2399 192 83 166 298 2433 2866 836 2322 2183 1002 305 565 1130 235 614 935 3315 3038 1888 105 370 492 41 123 1269 1304 1004 1986 2658 31 1405 979 10 72 57 425 360 52 1655 480 396 973 325 428 1896 317 829 148 1166 60 728 288 81 2231 223 514 1236 312 855 993 258 1483 2305 443 42 671 144 277 171 366 47 695 692 3733 3053 1271 71 1701 211 941 6 639 754 55 2346 650 928 138 5562 4081 12 4424 5333 786 19 520 5135 1510 1476 1706 74 1447 627 309 1745 594 376 329 1185 117 236 424 551 839 472 66 109 780 217 300 262 686 877 2171 884 1080 1278 1565 221 1976 1688 2154 2508 559 638 1303 1215 2127 2282 326 1348 1318 1132 699 2841 1669 2812 896 1982 20 1397 990 845 423 73 356 566 149 1265 15 227 2146 1783 53 50 1473 282 229 1378 2281 2333 234 697 1907 1665 524 749 152 419 812 1368 3366 1260 178 320 560 2234 2204 3920 270 338 232 1350 2168 1041 391 1073 37 801 87 257 1122 471 302 2147 343 205 283 486 2432 804 491 1738 49 1345 142 4337 1142 636 5418 54 156 18 90 535 243 689 2072 91 792 327 331 2756 2575 414 2107 3093 1809 122 386 684 4659 382 2129 507 1136 185 998 1584 3522 1705 542 67 181 351 730 534 3020 1512 700 95 354 442 313 1852 190 1892 745 666 1056 1816 610 1757 260 867 633 1985 960 1733 1730 704 177 165 781 2299 869 543 350 878 2669 2448 1774 172 834 214 1078 763 1098 363 1095 583 744 1594 141 409 808 4540 872 1229 212 393 1159 710 112 1422 30 1803 1293 766 729 687 648 3546 70 34 527 3981 1460 751 1714 4334 26 1216 717 1050 1879 245 667 135 481 401 1740 1164 454 339 622 208 1481 563 659 197 176 173 497 301 691 930 494 459 1245 653 1692 3017 644 600 595 950 1120 1934 392 1518 422 330 51 2236 293 1609 1663 765 226 120 1282 321 2016 746 265

ちなみに自分が作成したスクリプトでは，ボールの個数 $n$ とすると $n - 1$ が素数のときのみ解を得られる。ビリヤード問題自体は素数のべき乗のときにも解があるとされているが，どうやら未解決の問題のようである。

次回に続く。

9. 参考文献

参考になったサイトを以下に示す。