0. はじめに

森博嗣氏の小説「笑わない数学者」に登場するビリヤード問題について下記のシリーズ記事で取り扱ってきた。

一般化したビリヤード問題については，魔円陣（Magic Circle）もしくは周期ゴロム定規と呼ばれる数学の問題であり，古くから研究が行われてきたようである。このような先行研究を発見するたびに記事を書いてきたので，今となってはまとまりのない内容になってしまった。このため最新の状況を反映させながら本記事を総括編としてまとめたい。

1. 五つの玉の問題：手計算で解く場合

シリーズ第１回の記事では，その後のプログラム化を想定した非人間的なアルゴリズムを採用したが，おそらく一般的な（人間的な）計算手順は下記のようになる。

①と②の数は組み合わせで作れないので必ず必要となる
回転対称形を排除すると①の玉の位置を固定してよい
左右対称形を排除すると②の玉の位置は①の隣と一つ間を空けた場所の二つのみ
３個目の玉は，これまで表されていない数の中で最小値とし，場所は残り三つから選ぶ
４個目の玉も，これまで表されていない数の中で最小値とし，場所は残り二つから選ぶ
合計が２１となることから５個目の玉の数は自動的に決まり，場所も決まる
重複する数をチェックして排除する　※４個目を置くときエラーになる場合もある

上記の手順により，実際に場合分けを行った結果を表１に示す。なお赤色は新たに置く玉を示す。(…)内の数字は表すことのできる数字である。

表１　手計算による場合分け
１個目	２個目	３個目	４個目	５個目	判定
①－－－－ (1)	①②－－－ (1,2,3)	①②④－－ (1,2,3,4,6,7)	①②④⑤－	①②④⑤⑨	×④+⑤=⑨

			①②④－⑤	①②④⑨⑤	×⑤+①=②+④

		①②－④－ (1,2,3,4)	①②⑤④－	①②⑤④⑨	×⑤+④=⑨

			①②－④⑤	①②⑨④⑤	×⑨=④+⑤

		①②－－④ (1,2,3,4,5,7)	①②⑥－④	①②⑥⑧④	×②+⑥=⑧

			①②－⑥④	①②⑧⑥④	×②+⑧=⑥+④

	①－②－－ (1,2)	①③②－－ (1,2,3,4,5,6)	①③②⑦－	①③②⑦⑧	×⑧+①=②+⑦

			①③②－⑦	①③②⑧⑦	×⑧=⑦+①

		①－②③－ (1,2,3,5)	①④②③－		×①+④=②+③

			①－②③④		×④+①=②+③

		①－②－③ (1,2,3,4)	①⑤②－③	①⑤②⑩③	○

			①－②⑤③	①⑩②⑤③	×⑩＝②+⑤+③

こうやってしらみ潰しに調べても高々１２通りである。唯一の解は ①⑩②⑤③ となるが，左右反転させた ①③⑤②⑩ のほうが分かり易いだろう。

一見非効率的に見える方法だが，実は次項で述べる計算機手法はこの手順に沿ったアルゴリズムを採用しており，有限体理論を用いた手法を除き，全探索する方法としては最も探索効率が良いと考えている。

2. 一般的な問題：力技で全探索する方法

シリーズ第２回の記事で紹介したC言語版プログラムよりも第１１回の Visual Basic 版プログラムほうが格段に優れたアルゴリズムを採用している。下記はそれをC言語に移植したものであるが，Visual Basic（というより.NET環境）からC言語に移植しただけで四割ほどスピードがアップした。

実装コードを以下に示す。

C言語版プログラム billiard2.c のソースはコチラ

billiard2.c

#include <stdio.h>
#include <stdlib.h>
#define	FALSE			(0)									// 偽の値
#define	TRUE			(!FALSE)							// 真の値
#define	MIN_BALL_NUM	(3)									// ボールの個数の最大値
#define	MAX_BALL_NUM	(20)								// ボールの個数の最大値
#define	MAX_BALL_SUM	(1+MAX_BALL_NUM*(MAX_BALL_NUM-1))	// ボールの総和の最大値
static	int		count;										// 解の個数
static	int		ball_num;									// ボールの個数
static	int		ball_sum;									// ボールの総和
static	int		ball[1 + MAX_BALL_NUM];						// ボールの配置
static	int		flag[1 + MAX_BALL_SUM];						// 重複チェック用配列
//------------------------------------------------------------------------------
// 解の出力
//------------------------------------------------------------------------------
static	void	output( void ) {
	fprintf( stdout, "(%d) %d", ++count, ball[1] );
	if( ball[2] < ball[ball_num] ) {
		for( int i = 2; i <= ball_num; i++ )
			fprintf( stdout, " %d", ball[i] );
	} else {
		for( int i = ball_num; i >= 2; i-- )
			fprintf( stdout, " %d", ball[i] );
	}
	fprintf( stdout, "\n" );
}
//------------------------------------------------------------------------------
// インクリメンタル加算チェック，未配置の最小数の位置 k とする
//------------------------------------------------------------------------------
static	int		icheck( int k ) {
	int	j, r, t;
	for( j = 1, r = k, t = 0; j < ball_num; j++ ) {
		if( ball[r] == 0 ) break;
		if( ( t += ball[r] ) >= ball_sum || flag[t] ) goto SKIP;
		flag[t] = TRUE;
		for( int i = j + 1, l = k - 1, u = t; i < ball_num; i++ ) {
			if( ball[l] == 0 ) break;
			if( ( u += ball[l] ) >= ball_sum || flag[u] ) {
				for(;;) {
					u -= ball[l]; flag[u] = FALSE;
					if( u == t ) break;
					if( ++l > ball_num ) l = 1;
				}
				goto SKIP;
			}
			flag[u] = TRUE;
			if( --l == 0 ) l = ball_num;
		}
		if( ++r > ball_num ) r = 1;
	}
	return TRUE;
SKIP:
	while( j > 1 ) {
		j--;
		t -= ball[r]; flag[t] = FALSE;
		for( int i = j + 1, l = k - 1, u = t; i < ball_num; i++ ) {
			if( ball[l] == 0 ) break;
			u += ball[l]; flag[u] = FALSE;
			if( --l == 0 ) l = ball_num;
		}
		if( --r == 0 ) r = ball_num;
	}
	return FALSE;
}
//------------------------------------------------------------------------------
// インクリメンタル加算クリア，未配置の最小数の位置 k とする
//------------------------------------------------------------------------------
static	void	iclear( int k ) {
	for( int j = 1, r = k, t = 0; j < ball_num; j++ ) {
		if( ball[r] == 0 ) break;
		t += ball[r]; flag[t] = FALSE;
		for( int i = j + 1, l = k - 1, u = t; i < ball_num; i++ ) {
			if( ball[l] == 0 ) break;
			u += ball[l]; flag[u] = FALSE;
			if( --l == 0 ) l = ball_num;
		}
		if( ++r > ball_num ) r = 1;
	}
}
//------------------------------------------------------------------------------
// 再帰チェック関数，未配置の最小数 m，探索範囲の上限 range とする
//------------------------------------------------------------------------------
static	void	rcheck( int m, int range ) {
	for( int k = 2; k <= range; k++ ) {
		if( ball[k] != 0 ) continue;
		ball[k] = m;
		//----------------------------------------------------------------------
		// インクリメンタル加算チェック
		//----------------------------------------------------------------------
		if( icheck( k ) ) {
			//------------------------------------------------------------------
			// 次の未配置の最小数を探す
			//------------------------------------------------------------------
			int		s;
			for( s = m + 1; s <= ball_sum; s++ )
				if( !flag[s] ) break;
			if( s >= ball_sum ) {
				//--------------------------------------------------------------
				// 解の表示
				//--------------------------------------------------------------
				output();
			} else {
				//--------------------------------------------------------------
				// 再帰的に次の数をチェックする
				//--------------------------------------------------------------
				rcheck( s, ball_num );
			}
			//------------------------------------------------------------------
			// インクリメンタル加算クリア
			//------------------------------------------------------------------
			iclear( k );
		}
		ball[k] = 0;
	}
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
int		main( int argc, char *argv[] ) {
	//--------------------------------------------------------------------------
	// ヘルプメッセージ
	//--------------------------------------------------------------------------
	if( argc < 2 ) {
		fprintf( stderr, "Usage: billiard2(.exe) [ball-num]\n" );
		return( -1 );
	}
	//--------------------------------------------------------------------------
	// 準備
	//--------------------------------------------------------------------------
	ball_num = atoi( argv[1] );
	if( ball_num < MIN_BALL_NUM || ball_num > MAX_BALL_NUM ) {
		fprintf( stderr, "ボールの個数 %d が不正です!!\n", ball_num );
		return( -1 );
	}
	ball_sum = 1 + ball_num * ( ball_num - 1 );
	//--------------------------------------------------------------------------
	// 1 のボールは先頭に固定する
	// 2 のボールは二番目から中央まで移動する
	//--------------------------------------------------------------------------
	ball[1] = 1; flag[1] = TRUE;
	rcheck( 2, ( 1 + ball_num ) / 2 );
	//--------------------------------------------------------------------------
	// ボール個数が偶数かつ 2 のボールが中央のとき
	// 3 のボールは二番目から 2 のボールの手前まで移動する
	//--------------------------------------------------------------------------
	if( ( ball_num & 1 ) == 0 ) {
		int		k = 1 + ball_num / 2;
		ball[k] = 2; flag[2] = TRUE;
		rcheck( 3, k - 1 );
	}
	return( 0 );
}

あまりにも速くなったので，これまで未到達であった玉の数 $n = 18$ の場合でも三時間強で計算できるようになった。実行結果を以下に示す。
※Core i7-13700（ベース2.1GHz，ブースト5.2GHz）マシンの場合

C言語版プログラム billiard2.exe の実行結果はコチラ

表２　C言語版プログラムの実行結果
玉の数	計算時間[s]	解となる玉の配置
3	0.01	(1) 1 2 4
4	0.01	(1) 1 2 6 4 (2) 1 3 2 7
5	0.01	(1) 1 3 10 2 5
6	0.01	(1) 1 2 5 4 6 13 (2) 1 2 7 4 12 5 (3) 1 3 2 7 8 10 (4) 1 3 6 2 5 14 (5) 1 7 3 2 4 14
7	0.01	なし
8	0.01	(1) 1 2 10 19 4 7 9 5 (2) 1 6 12 4 21 3 2 8 (3) 1 4 22 7 3 6 2 12 (4) 1 4 2 10 18 3 11 8 (5) 1 3 8 2 16 7 15 5 (6) 1 3 5 11 2 12 17 6
9	0.01	(1) 1 2 4 8 16 5 18 9 10 (2) 1 11 8 6 4 3 2 22 16 (3) 1 6 4 24 13 3 2 12 8 (4) 1 4 7 6 3 28 2 8 14
10	0.01	(1) 1 2 6 18 22 7 5 16 4 10 (2) 1 5 4 13 3 8 7 12 2 36 (3) 1 4 2 20 8 9 23 10 3 11 (4) 1 6 9 11 29 4 8 2 3 18 (5) 1 4 3 10 2 9 14 16 6 26 (6) 1 3 9 11 6 8 2 5 28 18
11	0.02	なし
12	0.07	(1) 1 2 14 4 37 7 8 27 5 6 13 9 (2) 1 2 9 8 14 4 43 7 6 10 5 24 (3) 1 2 12 31 25 4 9 10 7 11 16 5 (4) 1 2 14 12 32 19 6 5 4 18 13 7 (5) 1 5 12 21 29 11 3 16 4 22 2 7 (6) 1 4 19 20 27 3 6 25 7 8 2 11 (7) 1 4 16 3 15 10 12 14 17 33 2 6 (8) 1 14 3 2 4 7 21 8 25 10 12 26 (9) 1 22 14 20 5 13 8 3 4 2 10 31 (10) 1 7 13 12 3 11 5 18 4 2 48 9 (11) 1 3 23 24 6 22 10 11 18 2 5 8 (12) 1 3 8 9 5 19 23 16 13 2 28 6 (13) 1 3 12 34 21 2 8 9 5 6 7 25 (14) 1 4 7 3 16 2 6 17 20 9 13 35 (15) 1 8 10 5 7 21 4 2 11 3 26 35 (16) 1 15 5 3 25 2 7 4 6 12 14 39 (17) 1 14 10 20 7 6 3 2 17 4 8 41 (18) 1 4 20 3 40 10 9 2 15 16 6 7
13	0.40	なし
14	2.72	(1) 1 2 21 17 11 5 9 4 26 6 47 15 12 7 (2) 1 2 13 7 5 14 34 6 4 33 18 17 21 8 (3) 1 2 28 14 5 6 9 12 48 18 4 13 16 7 (4) 1 6 8 22 4 5 33 21 3 20 32 16 2 10 (5) 1 5 2 24 15 29 14 21 13 4 33 3 9 10 (6) 1 10 48 9 19 4 8 6 7 17 3 2 34 15 (7) 1 4 20 2 12 3 6 7 33 11 8 10 35 31 (8) 1 12 48 6 2 38 3 22 7 10 11 5 4 14 (9) 1 9 21 25 3 4 8 5 6 16 2 36 14 33 (10) 1 9 5 40 3 4 21 35 16 18 2 6 11 12 (11) 1 3 12 7 20 14 44 6 5 24 2 28 8 9 (12) 1 8 21 45 6 7 11 17 3 2 10 4 23 25 (13) 1 9 14 26 4 2 11 5 3 12 27 34 7 28 (14) 1 3 24 6 12 14 11 55 7 2 8 5 16 19 (15) 1 3 5 6 25 32 23 10 18 2 17 7 22 12 (16) 1 4 6 31 3 13 2 7 14 12 17 46 8 19 (17) 1 10 22 34 27 12 3 4 2 14 24 5 8 17 (18) 1 5 23 27 42 3 4 11 2 19 12 10 16 8 (19) 1 8 3 10 23 5 56 4 2 14 15 17 7 18 (20) 1 4 8 52 3 25 18 2 9 24 6 10 7 14
15	20.33	なし
16	163.20	なし
17	1,323.52	(1) 1 2 4 8 16 32 27 26 11 9 45 13 10 29 5 17 18 (2) 1 7 31 2 11 3 9 36 17 4 22 6 18 72 5 10 19 (3) 1 7 12 44 25 41 9 17 4 6 22 33 13 2 3 11 23 (4) 1 21 11 50 39 13 6 4 14 16 25 26 3 2 7 8 27 (5) 1 3 12 10 31 7 27 2 6 5 19 20 62 14 9 28 17 (6) 1 7 3 15 33 5 24 68 2 14 6 17 4 9 19 12 34
18	11,314.37	(1) 1 2 18 4 6 37 9 14 79 7 8 11 16 13 32 12 5 33 (2) 1 2 24 15 4 16 12 25 38 50 14 17 5 8 10 11 49 6 (3) 1 2 42 13 4 11 23 14 12 20 7 29 18 71 10 9 16 5 (4) 1 2 41 12 5 6 8 7 9 4 29 36 18 22 10 27 25 45 (5) 1 2 27 7 13 5 21 22 19 12 4 24 32 10 23 71 6 8 (6) 1 2 20 6 12 47 15 30 27 21 4 39 7 10 34 19 5 8 (7) 1 9 2 3 23 7 43 4 20 16 6 19 34 51 13 8 31 17 (8) 1 12 34 5 16 60 36 14 6 3 15 4 7 37 17 8 2 30 (9) 1 5 2 25 4 12 44 34 18 20 19 26 21 3 11 40 13 9 (10) 1 9 2 4 43 36 5 26 8 22 46 28 7 17 3 18 19 13 (11) 1 17 2 10 4 7 38 5 8 24 15 42 6 22 3 68 9 26 (12) 1 4 2 16 12 13 8 24 38 44 15 27 10 9 17 3 11 53 (13) 1 3 34 2 45 7 18 5 48 16 10 57 6 13 14 8 9 11 (14) 1 37 11 24 26 16 29 23 18 33 6 8 13 4 3 2 10 43 (15) 1 5 24 4 32 17 54 15 7 9 26 52 3 8 10 2 25 13 (16) 1 27 3 13 2 6 50 5 9 11 12 10 7 19 41 53 4 34 (17) 1 5 4 45 11 27 41 7 24 26 13 8 43 16 2 12 3 19 (18) 1 6 11 3 2 28 34 35 4 38 10 27 19 24 12 13 32 8 (19) 1 22 20 7 9 10 5 29 3 8 17 13 48 4 2 12 21 76 (20) 1 14 39 19 2 10 28 8 35 6 3 13 4 7 18 5 32 63 (21) 1 4 36 35 32 49 7 6 3 14 8 12 27 19 2 24 18 10 (22) 1 3 25 7 20 30 46 15 38 10 6 5 13 47 2 17 14 8 (23) 1 3 11 13 5 20 10 7 51 6 16 34 26 19 2 44 31 8 (24) 1 23 26 5 11 9 18 21 13 6 22 35 71 2 8 4 3 29 (25) 1 17 9 31 6 2 12 16 5 47 3 4 15 10 13 11 62 43 (26) 1 6 52 16 50 3 31 5 9 15 4 13 8 2 20 35 26 11 (27) 1 3 20 9 58 19 2 25 36 13 22 31 12 5 11 26 8 6 (28) 1 6 9 32 18 5 14 21 4 13 11 91 2 8 12 31 3 26 (29) 1 7 15 24 20 9 2 3 38 13 6 26 4 12 21 79 10 17 (30) 1 4 27 43 6 11 2 7 3 18 16 8 14 39 25 33 15 35 (31) 1 12 36 19 25 7 11 4 5 30 3 21 2 8 6 72 17 28 (32) 1 5 14 4 22 12 9 50 27 51 3 8 2 15 16 32 7 29 (33) 1 4 16 7 17 25 8 26 3 6 13 39 2 12 18 64 36 10 (34) 1 12 3 5 9 27 4 2 66 10 24 25 28 11 7 19 32 22 (35) 1 7 35 32 36 44 4 12 17 5 23 2 24 15 31 6 3 10 (36) 1 6 36 9 16 13 26 2 3 15 4 8 65 21 35 14 23 10 (37) 1 39 18 4 6 76 15 11 9 3 31 2 14 5 8 17 7 41 (38) 1 20 14 59 19 5 3 9 33 7 4 2 16 10 15 23 37 30 (39) 1 9 12 16 14 3 15 8 27 31 59 2 4 7 36 39 5 19 (40) 1 3 11 20 7 33 10 9 17 22 6 2 16 5 32 12 13 88 (41) 1 5 22 24 12 13 8 26 9 30 2 29 19 53 37 3 4 10 (42) 1 15 28 6 12 11 3 5 2 20 36 35 13 4 38 9 45 24 (43) 1 12 9 5 38 16 28 3 32 37 2 18 58 8 7 4 6 23 (44) 1 3 8 45 9 18 10 6 7 17 2 29 15 5 59 38 14 21 (45) 1 4 3 36 23 6 18 22 9 2 19 63 14 34 16 10 15 12 (46) 1 7 3 27 6 12 23 5 19 2 51 9 4 16 34 57 17 14 (47) 1 12 23 3 7 21 16 18 22 2 6 11 32 20 5 4 90 14 (48) 1 4 6 17 13 8 16 9 20 2 12 72 15 3 32 7 19 51 (49) 1 5 9 8 4 7 32 24 18 2 35 3 10 49 29 25 16 30 (50) 1 4 27 13 70 17 6 29 22 2 9 3 7 18 30 8 26 15 (51) 1 9 29 4 20 11 45 16 65 2 3 12 6 7 19 8 14 36

3. 有限体理論を用いた方法

3.1 解の個数公式（予想）

シリーズ第６回の記事より引用する。

素数 $p$，自然数 $m$ として，ビリヤードの玉の数 $n = 1 + p^m$ 個と表されるとき，

\textsf{解の個数} = \frac{\phi(1 + n(n - 1))}{6m}

と予想されている。ここで $\phi(x)$ はオイラーの ϕ 関数といい，$x$ 以下で $x$ と互いに素な自然数の個数を返す。自然数 $x$ を素数 $p_1,\hspace1px p_2,\hspace1px p_3,\hspace1px\cdots,\hspace1px p_q$ のべき乗数の積として以下のように定義する。

\begin{aligned}
x &= p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \cdots \times p_q^{k_q} \\
&= \prod_{i = 1}^{q} p_i^{k_i}
\end{aligned}

このとき $\phi(x)$ は次のように定義される。

\begin{aligned}
\phi(x) &= x \times \left( 1 - \frac{1}{p_1} \right) \times \left( 1 - \frac{1}{p_2} \right) \times \left( 1 - \frac{1}{p_3} \right) \times \cdots \times \left( 1 - \frac{1}{p_q} \right) \\
&= x \prod_{i = 1}^{q} \left( 1 - \frac{1}{p_i} \right)
\end{aligned}

とくに $x$ が素数の場合は $\phi(x) = x - 1$ となる。

JavaScript によるサンプルコードを以下に示す。

オイラーの ϕ 関数

function euler_totient(n) {
	var	r = n;
	for(var i = 2; i * i <= n; i++) {
		if(n % i != 0) continue;
		while(n % i == 0) n /= i;
		r -= r / i;
	}
	if(n > 1) r -= r / n;
	return r;
}

3.2 玉の数が「１＋素数」個の場合

シリーズ第４回の記事で紹介したプログラムを少し改良した。主な改良点を以下に示す。

数列のパラメータの順を入れ替えた。これは参考文献の順とうっかり逆にしてしまっていたものを今回を機に修正したものだ。
解の個数の公式に従い，全ての解を得られたら直ちに終了するようにした。これで一桁以上速くなった。
最初の解を得たら直ちに終了するオプション /F を追加した。これは玉の数が多くなると全ての解を保持しておくことがメモリの制約によって難しくなるため。

実装コードを以下に示す。

JavaScript プログラム GaloisField.js のソースはコチラ

GaloisField.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("ボールの個数が「１＋素数」の場合の解を求めます。");
		WScript.Echo("");
		WScript.Echo("GaloisField(.js) (オプション) [素数]");
		WScript.Echo("");
		WScript.Echo("/F　最初の解を発見したら終了します。");
		return false;
	}
	//--------------------------------------------------------------------------
	// コマンドライン解析
	//--------------------------------------------------------------------------
	var	p = parseInt(args(0));
	var	f_flag = opts.Exists("F") ? true : false;
	//--------------------------------------------------------------------------
	// 線形再帰剰余数列のパラメータ (a,b,c) を全探索する
	//--------------------------------------------------------------------------
	var	num = 1 + p;						// ボールの個数
	var	sum = 1 + num * (num - 1);			// ボールの数値の総和
	var	limit = euler_totient(sum) / 6;		// 解の個数（予想値）
	var	count = 0;							// 解の個数
	var	d = [];								// 解（ボール配置）
BREAK:
	for( var a = 0; a < p; a++ ) {
		for( var b = 0; b < p; b++ ) {
			for( var c = 1; c < p; c++ ) {
				//--------------------------------------------------------------
				// 完全差集合を作成する
				//--------------------------------------------------------------
				var	s = [0, 0, 1];
				for(i = 3; i < sum + 2; i++) {
					var	v = (a * s[i - 1] + b * s[i - 2] + c * s[i - 3]) % p;
					s.push(v);
					if(v == 0 && s[i - 1] == 0) break;
				}
				if(i != sum + 1) 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_ball(u)) continue;
				//--------------------------------------------------------------
				// ボール配置の出力
				//--------------------------------------------------------------
				var	k = [a, b, c].join(" ")
				var	v = u.join(" ");
				if(f_flag) {
					WScript.Echo([num, k, v].join("\t"));
					return true;
				} else if(d[v] == null) {
					d[v] = k;
					if(++count >= limit) break BREAK;
				}
			}
		}
	}
	//--------------------------------------------------------------------------
	// ボール配置をソートして出力する
	//--------------------------------------------------------------------------
	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([num, e[i].key, e[i].val].join("\t"));
	//--------------------------------------------------------------------------
	// 解の個数を出力する
	//--------------------------------------------------------------------------
	WScript.Echo(e.length);
	return true;
}
//------------------------------------------------------------------------------
// ボール配置のチェック
//------------------------------------------------------------------------------
function check_ball(ball) {
	var	num = ball.length;
	var	sum = 1 + num * (num -  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;
}
//------------------------------------------------------------------------------
// オイラーのφ関数
//------------------------------------------------------------------------------
function euler_totient(n) {
	var	r = n;
	for(var i = 2; i * i <= n; i++) {
		if(n % i != 0) continue;
		while(n % i == 0) n /= i;
		r -= r / i;
	}
	if(n > 1) r -= r / n;
	return r;
}

高速 JavaScript エンジンを用いるバッチファイル Chakra.cmd のソースはコチラ

Chakra.cmd

@echo off
setlocal
if "%1"=="" goto USAGE
rem ----------------------------------------------------------------------------
rem スクリプトファイルの拡張子が省略された場合 .JS とする
rem ----------------------------------------------------------------------------
if "%~x1"=="" (
  set SCRIPTFILE=%~1.JS
) else (
  set SCRIPTFILE=%~1
)
rem ----------------------------------------------------------------------------
rem スクリプトファイルが存在する場合
rem ----------------------------------------------------------------------------
if exist %SCRIPTFILE% (
  set SCRIPTPATH=%SCRIPTFILE%
  goto SKIP
)
rem ----------------------------------------------------------------------------
rem スクリプトファイルをパスから検索する
rem ----------------------------------------------------------------------------
for %%I in ( %SCRIPTFILE% ) do set SCRIPTPATH=%%~$PATH:I
if "%SCRIPTPATH%"=="" (
  echo %SCRIPTFILE% が見つかりません!!
  exit /b
)
:SKIP
rem ----------------------------------------------------------------------------
rem スクリプトファイルのオプション解析
rem ----------------------------------------------------------------------------
set SCRIPTARGS=%SCRIPTPATH%
:LOOP
  if "%~2"=="" goto BREAK
  set SCRIPTARGS=%SCRIPTARGS% %2
  shift /2
goto LOOP
:BREAK
rem ----------------------------------------------------------------------------
rem スクリプトの実行
rem ----------------------------------------------------------------------------
cscript //E:{1B7CD997-E5FF-4932-A7A6-2A9E636DA385} %SCRIPTARGS%
exit  /b
:USAGE
rem ----------------------------------------------------------------------------
rem ヘルプメッセージ
rem ----------------------------------------------------------------------------
echo Microsoft Edge の chakra エンジンを用いて Javascript を高速実行します。
echo.
echo CHAKRA(.CMD) [スクリプトファイル名(.JS)]  [スクリプトオプション] ...
echo.
echo スクリプトファイルの拡張子を省略すると .JS とします。
exit /b

実行例を以下に示す。引数を何も指定しないとヘルプメッセージを表示する。

引数を何も指定しない場合

Chakra GaloisField.JS
ボールの個数が「１＋素数」の場合の解を求めます。

GaloisField(.js) (オプション) [素数]

/F　最初の解を発見したら終了します。

素数のみを指定した場合，解をソートして出力する。重複する解は出力しない。なお出力行において最初の 4 はボールの個数（１＋与えた素数）であり，続く三つの数値は数列のパラメータ，その次の数列がボールの配置となる。最後の行の 2 は得られた解の個数である。

素数のみを指定した場合

Chakra GaloisField.JS 3
4       1 0 2   1 2 6 4
4       1 1 1   1 3 2 7
2

オプション /F を指定すると最初の解を発見すると終了する。

オプション /F を指定した場合

Chakra GaloisField.JS 3 /F
4       1 0 2   1 2 6 4

指定可能な最大素数は JavaScript を実行する仮想マシンの使用可能なメモリ（おそらく2GB以下）によって決まる。当方の環境で確認できた上限値は以下の通り。

オプションを指定しないとき素数 953（玉の数としては 954 個）解の個数は 150,660 個，計算時間は9時間弱要した。なお計算時間は概ね玉の数の四乗に比例する傾向がみられる。なお素数 967（玉の数としては 968 個）はメモリ不足で失敗した。
オプション /F を使用したとき素数 15,583（玉の数としては 15,584 個）計算時間は 13 秒あまり。なお素数 15,601（玉の数としては 15,602 個）はメモリ不足で失敗した。

JavaScript プログラム GaloisField.js の実行結果はコチラ

表３　ボールの個数 $n = 1 + p$ と計算時間
素数 $p$	玉の数 $n$	解の数	計算時間 [s]	素数 $p$	玉の数 $n$	解の数	計算時間 [s]
2	3	1	0.03	421	422	19,740	534.46
3	4	2	0.03	431	432	26,136	784.45
5	6	5	0.03	433	434	20,304	661.32
7	8	6	0.03	439	440	20,460	804.50
11	12	18	0.03	443	444	28,098	1,024.48
13	14	20	0.03	449	450	33,312	1,159.52
17	18	51	0.04	457	458	19,932	882.99
19	20	42	0.04	461	462	35,340	1,262.74
23	24	78	0.05	463	464	22,608	929.43
29	30	132	0.05	467	468	34,506	1,331.14
31	32	110	0.05	479	480	37,422	1,455.57
37	38	132	0.07	487	488	22,632	1,048.69
41	42	287	0.10	491	492	39,168	1,521.43
43	44	210	0.11	499	500	23,544	1,101.62
47	48	360	0.17	503	504	39,000	1,788.04
53	54	408	0.22	509	510	42,252	1,940.20
59	60	590	0.44	521	522	43,710	2,064.59
61	62	384	0.33	523	524	28,104	1,578.65
67	68	420	0.40	541	542	27,924	1,607.36
71	72	852	0.72	547	548	33,048	2,097.60
73	74	600	0.67	557	558	44,394	2,651.46
79	80	588	0.74	563	564	51,210	3,576.32
83	84	1,098	1.09	569	570	46,326	3,223.27
89	90	1,335	1.38	571	572	30,600	2,269.32
97	98	1,056	1.57	577	578	35,100	2,829.29
101	102	1,717	2.27	587	588	57,330	4,443.94
103	104	1,190	1.94	593	594	58,320	4,533.79
107	108	1,512	2.26	599	600	51,342	4,013.26
109	110	1,140	1.99	601	602	37,104	3,045.40
113	114	1,980	2.91	607	608	37,848	3,302.01
127	128	1,806	4.96	613	614	35,844	3,239.19
131	132	2,882	7.08	617	618	62,880	5,014.99
137	138	2,592	7.22	619	620	40,392	3,729.30
139	140	1,992	5.89	631	632	44,064	3,736.13
149	150	3,060	8.91	641	642	58,788	5,045.67
151	152	2,184	7.20	643	644	45,504	4,114.96
157	158	2,756	12.95	647	648	69,510	5,868.24
163	164	2,376	11.96	653	654	53,352	5,049.29
167	168	4,676	20.78	659	660	66,912	5,612.40
173	174	5,017	23.21	661	662	48,620	4,319.87
179	180	4,602	22.04	673	674	50,400	5,019.19
181	182	3,588	17.98	677	678	76,501	6,956.82
191	192	4,680	24.76	683	684	66,738	5,963.07
193	194	3,564	22.82	691	692	50,328	4,963.96
197	198	6,156	35.11	701	702	82,017	7,052.33
199	200	4,422	28.28	709	710	47,940	5,738.11
211	212	4,320	35.47	719	720	86,022	9,799.94
223	224	5,550	46.80	727	728	58,806	7,654.91
227	228	8,496	67.90	733	734	56,628	8,465.28
229	230	5,760	50.36	739	740	52,080	7,393.03
233	234	7,788	63.83	743	744	92,132	12,316.02
239	240	9,054	69.72	751	752	53,784	7,953.77
241	242	6,480	60.63	757	758	58,848	8,950.20
251	252	10,290	83.36	761	762	96,647	13,131.07
257	258	10,860	113.39	769	770	63,660	9,096.61
263	264	9,072	116.41	773	774	99,717	14,676.52
269	270	10,800	133.79	787	788	66,600	11,306.95
271	272	8,190	110.64	797	798	105,300	16,009.53
277	278	6,912	106.75	809	810	81,648	12,155.67
281	282	13,068	158.82	811	812	69,120	10,777.85
283	284	8,784	130.99	821	822	95,760	14,687.07
293	294	14,357	187.02	823	824	63,000	11,267.67
307	308	10,248	153.80	827	828	114,126	17,042.65
311	312	15,318	207.49	829	830	76,020	12,299.66
313	314	10,860	177.18	839	840	117,460	17,219.54
317	318	14,400	212.21	853	854	79,044	13,708.36
331	332	10,464	204.47	857	858	122,551	18,859.21
337	338	12,348	233.08	859	860	122,688	18,593.30
347	348	15,912	361.69	863	864	106,512	17,825.33
349	350	12,852	291.46	877	878	71,280	14,084.91
353	354	19,728	423.26	881	882	122,688	18,593.30
359	360	17,928	394.40	883	884	86,730	14,803.78
367	368	13,848	362.52	887	888	121,176	20,232.70
373	374	12,096	321.66	907	908	78,432	16,557.91
379	380	15,720	375.68	911	912	138,472	25,789.41
383	384	24,512	566.84	919	920	69,984	14,896.11
389	390	21,672	486.71	929	930	143,052	28,408.93
397	398	16,980	452.97	937	938	97,656	18,722.13
401	402	23,028	542.96	941	942	147,420	35,457.38
409	410	18,632	541.98	947	948	127,512	32,863.05
419	420	27,072	735.34	953	954	150,660	32,272.79

3.3 玉の数が「１＋素数のべき乗」の場合

シリーズ第５回の記事で紹介したプログラムを少し改良した。これまで指数ごとに別々のプログラムに分かれていたが，一つのプログラムに統合した。また GaloisField.js と同じ改良を加えた。実装コードを以下に示す。

JavaScript プログラム GaloisField2.js のソースはコチラ

GaloisField2.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("ボールの個数が「１＋素数のべき乗」の場合の解を求めます。");
		WScript.Echo("");
		WScript.Echo("GaloisField2(.js) (オプション) [素数] (指数)");
		WScript.Echo("");
		WScript.Echo("/F　最初の解を発見したら終了します。");
		return false;
	}
	//--------------------------------------------------------------------------
	// コマンドライン解析
	//--------------------------------------------------------------------------
	var	p = parseInt(args(0));
	var	m = args.Count > 1 ? parseInt(args(1)) : 1;
	var	f_flag = opts.Exists("F") ? true : false;
	//--------------------------------------------------------------------------
	// 線形再帰剰余数列のパラメータ a[] を全探索する
	//--------------------------------------------------------------------------
	var	num   = 1 + Math.pow(p, m);				// ボールの個数
	var	sum   = 1 + num * (num - 1);			// ボールの数値の総和
	var	limit = euler_totient(sum) / (6 * m);	// 解の個数（予想値）
	var	count = 0;								// 解の個数
	var	d = [];									// 解（ホール配置）
	var	a = [];									// 数列の係数
	//--------------------------------------------------------------------------
	// 完全差集合をボール配置に変換して出力する
	//--------------------------------------------------------------------------
	var	output = function(t) {
		//----------------------------------------------------------------------
		// 完全差集合をボール配置に変換する
		//----------------------------------------------------------------------
		var	u = [];
		for(var i = 1; i < t.length; i++)
			u.push(t[i] - t[i - 1]);
		//----------------------------------------------------------------------
		// 1 のボールを探す
		//----------------------------------------------------------------------
		for(var i = 0; i < u.length; i++)
			if(u[i] == 1) break;
		if(i >= num) return;
		var	v = [];
		for(j = 0; j < num + 1; j++)
			v.push(u[i + j]);
		//----------------------------------------------------------------------
		// ボール配置を正規化（左右反転）
		//----------------------------------------------------------------------
		if(v[1] > v[num - 1]) v.reverse();
		v.pop();
		//----------------------------------------------------------------------
		// ボール配置のチェック＆重複するボール配置を取り除く
		//----------------------------------------------------------------------
		if(!check_ball(v)) return;
		//----------------------------------------------------------------------
		// ボール配置の出力
		//----------------------------------------------------------------------
		var	k = a.join(" ");
		var	w = v.join(" ");
		if(f_flag) {
			WScript.Echo([num, k, w].join("\t"));
			throw new Error();
		} else if(d[w] == null) {
			d[w] = k;
			if(++count >= limit) throw new Error();
		}
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の場合
	//--------------------------------------------------------------------------
	var	search1 = function() {
		var	s = [0, 0, 1];
		for(var i = 3 * 1; i < sum * 2; i++) {
			var	v = a[0] * s[i - 1] + a[1] * s[i - 2] + a[2] * s[i - 3];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 0; i < sum * 2; i++)
			if(s[i] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の二乗の場合
	//--------------------------------------------------------------------------
	var	search2 = function() {
		var	s = [0, 0, 0, 0, 0, 1];
		for(var i = 3 * 2; i < sum * 3; i++) {
			var	v = a[0] * s[i - 1] + a[1] * s[i - 2] + a[2] * s[i - 3]
				  + a[3] * s[i - 4] + a[4] * s[i - 5] + a[5] * s[i - 6];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 1; i < sum * 3; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の三乗の場合
	//--------------------------------------------------------------------------
	var	search3 = function() {
		var	s = [0, 0, 0, 0, 0, 0, 0, 0, 1];
		for(var i = 3 * 3; i < sum * 4; i++) {
			var	v = a[0] * s[i - 1] + a[1] * s[i - 2] + a[2] * s[i - 3]
				  + a[3] * s[i - 4] + a[4] * s[i - 5] + a[5] * s[i - 6]
				  + a[6] * s[i - 7] + a[7] * s[i - 8] + a[8] * s[i - 9];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 2; i < sum * 4; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0 && s[i - sum * 2] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の四乗の場合
	//--------------------------------------------------------------------------
	var	search4 = function() {
		var	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
		for(var i = 3 * 4; i < sum * 5; i++) {
			var	v = a[0] * s[i - 1]  + a[1]  * s[i - 2]  + a[2]  * s[i - 3]
				  + a[3] * s[i - 4]  + a[4]  * s[i - 5]  + a[5]  * s[i - 6]
				  + a[6] * s[i - 7]  + a[7]  * s[i - 8]  + a[8]  * s[i - 9]
				  + a[9] * s[i - 10] + a[10] * s[i - 11] + a[11] * s[i - 12];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 3; i < sum * 5; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0 && s[i - sum * 2] == 0 && s[i - sum * 3] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の五乗の場合
	//--------------------------------------------------------------------------
	var	search5 = function() {
		var	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
		for(var i = 3 * 5; i < sum * 6; i++) {
			var	v = a[0]  * s[i - 1]  + a[1]  * s[i - 2]  + a[2]  * s[i - 3]
				  + a[3]  * s[i - 4]  + a[4]  * s[i - 5]  + a[5]  * s[i - 6]
				  + a[6]  * s[i - 7]  + a[7]  * s[i - 8]  + a[8]  * s[i - 9]
				  + a[9]  * s[i - 10] + a[10] * s[i - 11] + a[11] * s[i - 12]
				  + a[12] * s[i - 13] + a[13] * s[i - 14] + a[14] * s[i - 15];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 4; i < sum * 6; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0 && s[i - sum * 2] == 0 && s[i - sum * 3] == 0
						 && s[i - sum * 4] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の六乗の場合
	//--------------------------------------------------------------------------
	var	search6 = function() {
		var	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
		for(var i = 3 * 6; i < sum * 7; i++) {
			var	v = a[0]  * s[i - 1]  + a[1]  * s[i - 2]  + a[2]  * s[i - 3]
				  + a[3]  * s[i - 4]  + a[4]  * s[i - 5]  + a[5]  * s[i - 6]
				  + a[6]  * s[i - 7]  + a[7]  * s[i - 8]  + a[8]  * s[i - 9]
				  + a[9]  * s[i - 10] + a[10] * s[i - 11] + a[11] * s[i - 12]
				  + a[12] * s[i - 13] + a[13] * s[i - 14] + a[14] * s[i - 15]
				  + a[15] * s[i - 16] + a[16] * s[i - 17] + a[17] * s[i - 18];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 5; i < sum * 7; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0 && s[i - sum * 2] == 0 && s[i - sum * 3] == 0
						 && s[i - sum * 4] == 0 && s[i - sum * 5] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の七乗の場合
	//--------------------------------------------------------------------------
	var	search7 = function() {
		var	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
		for(var i = 3 * 7; i < sum * 8; i++) {
			var	v = a[0]  * s[i - 1]  + a[1]  * s[i - 2]  + a[2]  * s[i - 3]
				  + a[3]  * s[i - 4]  + a[4]  * s[i - 5]  + a[5]  * s[i - 6]
				  + a[6]  * s[i - 7]  + a[7]  * s[i - 8]  + a[8]  * s[i - 9]
				  + a[9]  * s[i - 10] + a[10] * s[i - 11] + a[11] * s[i - 12]
				  + a[12] * s[i - 13] + a[13] * s[i - 14] + a[14] * s[i - 15]
				  + a[15] * s[i - 16] + a[16] * s[i - 17] + a[17] * s[i - 18]
				  + a[18] * s[i - 19] + a[19] * s[i - 20] + a[20] * s[i - 21];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 6; i < sum * 8; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0 && s[i - sum * 2] == 0 && s[i - sum * 3] == 0
						 && s[i - sum * 4] == 0 && s[i - sum * 5] == 0 && s[i - sum * 6] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	//--------------------------------------------------------------------------
	// 解の探索を行う：1＋素数の八乗の場合
	//--------------------------------------------------------------------------
	var	search8 = function() {
		var	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1];
		for(var i = 3 * 8; i < sum * 9; i++) {
			var	v = a[0]  * s[i - 1]  + a[1]  * s[i - 2]  + a[2]  * s[i - 3]
				  + a[3]  * s[i - 4]  + a[4]  * s[i - 5]  + a[5]  * s[i - 6]
				  + a[6]  * s[i - 7]  + a[7]  * s[i - 8]  + a[8]  * s[i - 9]
				  + a[9]  * s[i - 10] + a[10] * s[i - 11] + a[11] * s[i - 12]
				  + a[12] * s[i - 13] + a[13] * s[i - 14] + a[14] * s[i - 15]
				  + a[15] * s[i - 16] + a[16] * s[i - 17] + a[17] * s[i - 18]
				  + a[18] * s[i - 19] + a[19] * s[i - 20] + a[20] * s[i - 21]
				  + a[21] * s[i - 22] + a[22] * s[i - 23] + a[23] * s[i - 24];
			s.push(v % p);
		}
		var	t = [];
		for(var i = sum * 7; i < sum * 9; i++)
			if(s[i] == 0 && s[i - sum * 1] == 0 && s[i - sum * 2] == 0 && s[i - sum * 3] == 0
						 && s[i - sum * 4] == 0 && s[i - sum * 5] == 0 && s[i - sum * 6] == 0
						 && s[i - sum * 7] == 0)
				t.push(i);
		if(t.length == 2 * num) output(t);
	};
	var	table = [null, search1, search2, search3, search4, search5, search6, search7, search8];
	//--------------------------------------------------------------------------
	// 再帰的ループ関数
	//--------------------------------------------------------------------------
	function loop(n) {
		for(a[n] = 0; a[n] < p; a[n]++)
			for(a[n + 1] = 0; a[n + 1] < p; a[n + 1]++)
				for(a[n + 2] = 0; a[n + 2] < p; a[n + 2]++)
					if(n + 3 < 3 * m)
						loop(n + 3);
					else
						table[m]();
	}
	//--------------------------------------------------------------------------
	// 例外で深いループを脱出する
	//--------------------------------------------------------------------------
	try {
		loop(0);
	} catch(e) {
		if(f_flag) return true;
	}
	//--------------------------------------------------------------------------
	// ボール配置をソートして出力する
	//--------------------------------------------------------------------------
	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([num, e[i].key, e[i].val].join("\t"));
	//--------------------------------------------------------------------------
	// 解の個数を出力する
	//--------------------------------------------------------------------------
	WScript.Echo(e.length);
	return true;
}
//------------------------------------------------------------------------------
// ボール配置のチェック
//------------------------------------------------------------------------------
function check_ball(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;
}
//------------------------------------------------------------------------------
// オイラーのφ関数
//------------------------------------------------------------------------------
function euler_totient(n) {
	var	r = n;
	for(var i = 2; i * i <= n; i++) {
		if(n % i != 0) continue;
		while(n % i == 0) n /= i;
		r -= r / i;
	}
	if(n > 1) r -= r / n;
	return r;
}

実行例を以下に示す。引数を何も指定しないとヘルプメッセージを表示する。

引数を何も指定しない場合

Chakra GaloisField2.JS
ボールの個数が「１＋素数のべき乗」の場合の解を求めます。

GaloisField2(.js) (オプション) [素数] (指数)

/F　最初の解を発見したら終了します。

素数（と指数）を指定した場合，解をソートして出力する。重複する解は出力しない。なお出力行において最初の 5 はボールの個数（１＋与えた素数のべき乗）であり，続く六個の数値は数列のパラメータ，その次の数列がボールの配置となる。最後の行の 1 は得られた解の個数である。

素数と指数を指定した場合

Chakra GaloisField2.JS 2 2
5       0 0 0 0 1 1     1 3 10 2 5
1

指定可能な指数の範囲は 1～8 である。ちなみに指数の指定を省略すると 1 とみなすが，その場合は GaloisField.js を使用したほうが圧倒的に速い。

JavaScript プログラム GaloisField2.js の実行結果はコチラ

表４　ボールの個数 $n = 1 + p^m$ と計算時間
素数 $p$	指数 $m$	玉の数 $n$	解の数	計算時間[s]
2	2	5	1	0.04
2	3	9	4	0.04
3	2	10	6	0.04
2	4	17	6	0.06
5	2	26	30	0.10
3	3	28	42	0.27
2	5	33	30	0.31
7	2	50	126	2.30
2	6	65	72	7.51
3	4	82	216	28.46
11	2	122	648	28.52
5	3	126	828	161.61
2	7	129	336	157.32
13	2	170	1,560	658.47
3	5	244	1,824	4,975.03
2	8	257	720	7,888.13
17	2	290	3,672	1,248.15
7	3	344	4,248	13,688.70
19	2	362	6,174	17,590.66

3.4 一つの解から他の解を求める方法

シリーズ第６回の記事で紹介したプログラムを少し改良した。

JavaScript プログラム AnotherSolver2.js のソースはコチラ

AnotherSolver2.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("他のボール配置を求めます。");
		WScript.Echo("");
		WScript.Echo("AnotherSolver2(.js) (オプション) [ボール配置] ...");
		WScript.Echo("");
		WScript.Echo("/R　重複解を含めてそのまま出力します。");
		return false;
	}
	//--------------------------------------------------------------------------
	// コマンドライン解析
	//--------------------------------------------------------------------------
	var	ball = [];
	for(var i = 0; i < args.Count; i++) {
		var	n = parseInt(args(i));
		ball.push(n);
	}
	var	r_flag = opts.Exists("R") ? true : false;
	//--------------------------------------------------------------------------
	// ボール配置のチェック
	//--------------------------------------------------------------------------
	if(!check_ball(ball)) {
		WScript.Echo("ボール配置が不正です!!");
		return false;
	}
	//--------------------------------------------------------------------------
	// ボール配置を完全差集合に変換する
	//--------------------------------------------------------------------------
	var	pcds = [];
	for(var i = 0, n = 0; i < ball.length; i++) {
		pcds.push(n);
		n += ball[i];
	}
	var	ball_sum = n;
	//--------------------------------------------------------------------------
	// 別解を探す
	//--------------------------------------------------------------------------
	var	d = [];
	for(var m = 1; m < ball_sum; m++) {
		//----------------------------------------------------------------------
		// 差集合を生成
		//----------------------------------------------------------------------
		var	s = [];
		for(var i = 0; i < pcds.length; i++) {
			var	n = pcds[i] * m % ball_sum; 
			s.push(n);
		}
		s.push(ball_sum);
		s.sort(function(a, b) {
			return a - b;
		});
		//----------------------------------------------------------------------
		// ボール配置に変換
		//----------------------------------------------------------------------
		var	t = [];
		for(var i = 1; i < s.length; i++)
			t.push(s[i] - s[i - 1]);
		//----------------------------------------------------------------------
		// 回転対称形を除く（１のボールを頭出し）
		//----------------------------------------------------------------------
		for(var i = 0; i < t.length; i++)
			if(t[i] == 1) break;
		if(i >= t.length) continue;
		var	u = [];
		for(var j = i, k = 0; k < t.length; k++) {
			u.push(t[j]);
			if(++j >= t.length) j = 0;
		}
		//----------------------------------------------------------------------
		// 左右対称形を除く
		//----------------------------------------------------------------------
		u.push(1);
		if(u[1] > u[u.length - 2]) u.reverse();
		u.pop();
		//----------------------------------------------------------------------
		// ボール配置のチェック＆重複するボール配置を除く
		//----------------------------------------------------------------------
		if(check_ball(u)) {
			var	v = u.join(" ");
			if(r_flag)
				WScript.Echo(v);
			else if(d[v] == null)
				d[v] = m;
		}
	}
	if(r_flag) return true;
	//--------------------------------------------------------------------------
	// ボール配置をソートして出力する
	//--------------------------------------------------------------------------
	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(e[i].val);
	//--------------------------------------------------------------------------
	// 解の個数を出力する
	//--------------------------------------------------------------------------
	WScript.Echo(e.length);
	return true;
}
//------------------------------------------------------------------------------
// ボール配置のチェック
//------------------------------------------------------------------------------
function check_ball(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;
}

実行例を以下に示す。引数を何も指定しないとヘルプメッセージを表示する。

引数を何も指定しない場合

Chakra AnotherSolver2.js
他のボール配置を求めます。

AnotherSolver2(.js) (オプション) [ボール配置] ...

/R　重複解を含めてそのまま出力します。

ボール配置のみを指定した場合，全ての解（指定した解も含む）をソートして出力する。最後の行の 2 は得られた解の個数である。

ボール配置のみを指定した場合

Chakra AnotherSolver2.js 1 2 6 4
1 2 6 4
1 3 2 7
2

オプション /R を指定すると重複解を含めて得られた解を発見順に出力する。なお，オプション /R は使用メモリが少なくて済むので，与えたデータサイズが大き過ぎてメモリ不足になる場合はこのオプションを使用すると良い。

オプション /R を指定した場合

Chakra AnotherSolver2.js 1 2 6 4 /R
1 2 6 4
1 3 2 7
1 2 6 4
1 2 6 4
1 3 2 7
1 3 2 7
1 3 2 7
1 3 2 7
1 2 6 4
1 2 6 4
1 3 2 7
1 2 6 4

この場合，Windows 付属の sort コマンドを使えば重複解を削除できる。

sort コマンドを使って重複解を削除

Chakra AnotherSolver2.js 1 2 6 4 /R | sort /unique
1 2 6 4
1 3 2 7

いつのまにか Windows10 付属の sort コマンドに /unique オプションが追加されていたようだ。下記サイトは Windows Server の情報であるが，クライアント側の Windows10 やもちろん Windows11 でも使用できるようだ。

https://learn.microsoft.com/ja-jp/windows-server/administration/windows-commands/sort

4. まとめ

総括編と言いつつも，これまでの一連のシリーズで紹介してきた自作プログラムのブラッシュアップ版の紹介になってしまった。

理論的な説明については，シリーズ第７回の記事あるいは第８回の記事あたりを参照して欲しいが，下記参考文献に直接当たるのも良いかもしれない。実は James Singer の論文にほぼ全てのことが最初から記載されていたのだ。

5. 参考文献

森博嗣の小説中の問題をRubyで解いた - Qiita
島内剛一，λ倍取りゲーム，数学セミナー1982年1月号，10～14頁，日本評論社
下林山稔，パソコンで魔円陣を，数学セミナー1987年7月号，55～59頁，日本評論社
秋山茂樹，魔円陣と有限幾何，数学セミナー2013年7月号，25～31頁，日本評論社
小林吹代，ガロアの数学「体」入門～魔円陣とオイラー方陣を例に～，技術評論社
Kris Coolsaet, Cyclic Difference Sets
Justin Colannino, Circular and Modular Golomb Rulers
James Singer, A Theorem in Finite Projective Geometry and Some Applications to Number Theory, American Mathematical Society, 43-3 (1938), pp.377-385
David A. James, Magic Circles, Mathematics Magazine, Vol.54, No.3 (1981), pp.122-125