0. はじめに
森博嗣氏の小説「笑わない数学者」に登場するビリヤード問題について下記のシリーズ記事で取り扱ってきた。
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(1)～導入編
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(2)～計算機を使う
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(3)～計算量オーダーを考える
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(4)～世界記録に挑む
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(5)～未解決問題に挑む
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(6)～答え合わせ編
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(7)～解法の謎に迫る
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(8)～謎は全て解けた
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(9)～巡回平面凄過ぎる
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(10)～40年前のBASICプログラムに敗北する
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(11)～40年越しの回答
- 今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(12)～作図のヒミツ
一般化したビリヤード問題については，魔円陣（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 の実行結果はコチラ
| 玉の数 | 計算時間[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 の実行結果はコチラ
| 素数 $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 の実行結果はコチラ
| 素数 $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