金野裕希

どうぶつしょうぎの完全解析プログラムを改造した3三将棋の完全解析プログラムを、一般の9マス将棋に対応させた。

https://github.com/9-square-shogi/dobutsu

dobutsu.hの26行目から31行目の初期局面を変更し、make && ./makeAllState && ./makeWinLoseで任意の駒の種類の9マス将棋を完全解析できる。

make checkStateして、init.txtに局面を入力し、./checkState init.txtで特定の局面の解析結果を表示できる。

makeWinLose.ccの連続王手の千日手を反則とする処理にバグがあるかもしれない。

初期局面を変更せずに、次のようなシェルスクリプトをdobutsuディレクトリと同じディレクトリで実行すると、約9時間半で3～6駒(玉を除けば1～4駒)の9マス将棋を全パターン完全解析し、最長手数の局面を求められる。(gem install partitionsが必要)

#!/bin/bash
for p in $(ruby -rpartitions -e ‘(1..4).each{|n| n.partitions{|p| [*p, *[0]*(7 – p.length)].permutation.uniq.each{|p| puts p.join("") } } }’)
do
echo $p &&
cp -r dobutsu $p &&
cd $p &&
perl -0777 -i -pE ‘s/0000000/’$p’/’ dobutsu.h &&
make -s &&
time ./makeAllState &&
time ./makeWinLose > output.txt &&
time ./longestWin > longest.txt 2>&1 &&
cd .. &&
mv $p $(perl -E ‘($_ and print qw(r b g s n l p)[$i], $_), $i++ for reverse split //, "’$p’"’)
done

6駒以下の9マス将棋の最長手数の局面は、以下の角金銀歩の67手の局面のようである(左右反転を同一として2通りあるうちの1つで、先手の持ち駒は金、後手の持ち駒は角)。

-GI . +OU
. . .
. +FU-OU
0000100
0000010
+

このプログラムでは遅すぎて、個々の9マス将棋はなんとか完全解析できるものの、7駒の9マス将棋は2、3日では全パターン完全解析できなかった。

n駒の9マス将棋の駒の種類の組合せの数は、玉以外の7種類の駒から(n – 2)個を選ぶ重複組合せとなるので、

7H(n – 2) = (n + 4)C6 = (n + 4)C(n – 2)

と表せるようだ。

Wolfram Alphaによると、n ≥ 2での値は次のようになる。

1, 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, …

まとめブログに完全数を連続する自然数の和で表したら最後の数はメルセンヌ数になることは証明できるかと書いてあった。

そんなことは証明されているだろうと思ってwikiを見たら、確かに

偶数の完全数は、1から連続する正の整数の和で表せる。
例:
6 = 1 + 2 + 3,
28 = 1 + 2 + 3 + 4 + 5 + 6 + 7,
496 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + … + 31
言い換えると、N(偶数の完全数)は2^p – 1番目の三角数である

と書いてあった。

最近無意味な数学の問題を考えるのにハマっているので、このことを証明してみた。

以下ではnを正の整数、pを素数とする。

完全数とは、約数関数をσ(n)として
σ(n) = 2n
を満たすnである。

メルセンヌ数とは
M(n) = 2^n – 1
の形をした正の整数で、
ここでは素数であるもの(メルセンヌ素数)を意味するものとする。
M(n)が素数ならば、nも素数であることが知られている。

メルセンヌ素数M(p) = 2^p – 1番目の三角数は、等差数列の和(ガウスの公式)1 + 2 + … + n = n(n + 1)/2にn = 2^p – 1を代入して

T(2^p – 1)
= 1 + 2 + … + (2^p – 1)
= (2^p – 1)･2^p/2
= (2^p – 1)･2^(p – 1)

と表せる。

この数の正の約数は、(2^p – 1)が素数である前提と、2^(p – 1)が2の累乗数であることから、

1, 2, 2^2, …, 2^(p – 1),

およびこれらの数に(2^p – 1)を掛けた数

(2^p – 1), 2･(2^p – 1), 2^2･(2^p – 1), …, 2^(p – 1)･(2^p – 1)

となる。これらの総和は、等比数列の和により

σ((2^p – 1)･2^(p – 1))
= 1 + 2 + 2^2 + … + 2^(p – 1)
+ (1 + 2 + 2^2 + … + 2^(p – 1))(2^p – 1)
= (1 + 2 + 2^2 + … + 2^(p – 1))･2^p
= (2^p – 1)･2^p

となる。

すなわち、(2^p – 1)･2^(p – 1)は正の約数の総和がそれ自身の2倍に等しいので、完全数である。

逆の証明は思いつかなかったが、英語版Wikipediaに載っていた。

上記の証明も約数関数の乗法性を利用すればよかった。

偶数の完全数とメルセンヌ素数が一対一対応することは、ユークリッド・オイラーの定理と呼ばれるらしい。