2018-12-19

10の記事

整数整数-10

$10$ といえば

$1^1+2^2+3^3+4^4+5^5+6^6+7^7+8^8+9^9+10^{10}=10405071317$

が素数であることを思い出します。

さて、数学の問題を二つ出題します。

問１ $n=pq$ ( $p, q$ は素数)であるとき、 $p+q$ と $p-q$ がともに素数となるような $n$ を全て求めよ。

問２正整数 $k$ に対して、 $k$ 番目の素数を $p_k$ と表すことにする。このとき、

$n^2=p_n+p_{2n}$

が成り立つような $n$ を全て求めよ。

敬具

2018-12-19

arcsin^2のテイラー展開

和算

この記事は日曜数学会のAdvent Calendarの17日目の記事です。

adventar.org

数日前、日曜数学会ミニが仙台で開催されました。この記事はそこでのライトニングトークの内容に基づいています。

和算の内容を含んでいますが、私は専門家ではなく十分な文献調査をしたわけでもないため、間違いや勘違いを多く含んでいると思われます。間違いが分かり次第その都度修正致しますが、ご了承いただけますと幸いです。

建部賢弘

建部賢弘(1664-1739)は和算家であり、『綴術算経』(1722年)に円周率の累遍増約術を用いた計算が書かれています。彼の術で小数第41位まで正確に求めることができます*1。

直径 $1$ の円に内接する正 $2^k$ 角形の周の長さを $l_k$ とするとき、 $\lim_{k \to \infty}l_k=\pi$ が成り立ちます。 $l_k$ を円周率の近似とすることは昔からなされていて、初等幾何学的に

$\displaystyle l_{k+1}=\sqrt{2^{k+1}\left(2^k-\sqrt{4^k-l_k^2}\right)}$

という漸化式の成立がわかるため、これを利用して円周率の近似計算をすることが原理的には可能です。ルドルフは正 $2^{62}$ 角形の周の長さを計算して円周率を小数第35桁まで計算したそうです。

一方、関孝和は $l_k$ までのデータしか与えられなくとも、残りの $l_{k'}$ ( $k' > k$ )の値を上手く近似的に補完することによって収束を加速させる増約術を開発しました(関の使ったデータと手法では円周率を小数第18位まで求められます)。

建部は関の増約術を繰り返し適用する累遍増約術を編み出しています。まず、 $l_1, \dots, l_{10}$ をあらかじめ計算しておきます。これを用いて

$\displaystyle \varepsilon_k:=\frac{l_{k+1}-l_k}{l_k-l_{k-1}}$

を $k=2, \dots, 9$ で計算します。その数値をみると、 $\varepsilon_k$ は $k \to \infty$ で $1/4$ に収束することが強く期待されます。

$\begin{align}l_k&=l_9+(l_{10}-l_9)+(l_{11}-l_{10})+\cdots +(l_k-l_{k-1})\\ &=l_9+(l_{10}-l_9)(1+\varepsilon_{10}+\varepsilon_{10}\varepsilon_{11}+\cdots +\varepsilon_{10}\varepsilon_{11}\cdots\varepsilon_{k}) \end{align}$

なので、 $\varepsilon_{10}$ 以降を $1/4$ と置き換えることによって

$\displaystyle \pi ≒ l_9+(l_{10}-l_9)\sum_{i=0}^{\infty}\frac{1}{4^i}=\frac{1}{3}(4l_{10}-l_9)$

と考えられます。これが増約術です。ここで終わらずに円周率の近似列

$\displaystyle l_k^{(1)}:=\frac{1}{3}(4l_{k+1}-l_k) \quad (k=1, \dots, 9)$

に対して同様の増約術を適用します。すると、 $\varepsilon_k^{(1)}$ は $1/4^2$ に収束することがみてとれ、

$\displaystyle \pi ≒ l_8^{(2)}:=\frac{1}{15}(16l_{9}^{(1)}-l_8^{(1)})$

を得ることができます。以下、同様に増約術を繰り返すことによって(累遍増約術)、円周率の近似

$\displaystyle \pi ≒ l_1^{(9)}$

に到達し、正しく計算すれば円周率の小数第41位まで正確に近似します([1])。

次に、円の弧長 $s$ を矢の長さ $h$ と直径 $d$ を用いて表すという問題を考えます。

f:id:integers:20181218180817p:plain:w300

ここで、弧 $ACB$ の長さを $s$ とし、 $CD$ を矢と呼んで、その長さを $h$ としています。建部は $d=10, h=10^{-5}$ のときに弧 $ACB$ を六十四等分して、定半背冪 $\left(\frac{s}{2}\right)^2$ を累遍増約術で計算しました。その結果、

$\displaystyle \left(\frac{s}{2}\right)^2=0.00010000003333335111112253969066667282347769479595875\cdots$

を得ています。建部はこれが

$\displaystyle \left(\frac{s}{2}\right)^2=1\times 10^{-4}+\frac{1}{3}\times 10^{-10}+\cdots$

と級数展開されると見抜き、続く項の係数も零約術(=連分数展開)を用いることによって発見しました。例えば

$\displaystyle \left(\frac{s}{2}\right)^2-\left(1\times 10^{-4}+\frac{1}{3}\times 10^{-10}\right)=a\times 10^{-16}$

として( $10^{-6}=h/d$ )、 $a$ を連分数展開して近似分数を求めると

$\displaystyle \frac{1}{5}, \frac{1}{6}, \frac{2}{11}, \frac{3}{17}, \frac{5}{28}, \frac{8}{45}, \frac{34565}{194428}, \dots$

となっており、 $8/45$ が係数であろうと見当をつけます。続けて

$\displaystyle \left(\frac{s}{2}\right)^2-\left(1\times 10^{-4}+\frac{1}{3}\times 10^{-10}+\frac{8}{45}\times 10^{-16}\right)=b\times 10^{-22}$

として、 $b$ を連分数展開して近似分数を求めると

$\displaystyle \frac{1}{8}, \frac{1}{9}, \frac{3}{26}, \frac{4}{35}, \frac{40175}{351531}, \dots$

となっており、 $4/35$ が係数であろうと考えます。このようにして、建部は

$\displaystyle \left(\frac{s}{2}\right)^2=1\times 10^{-4}+\frac{1}{3}\times 10^{-10}+\frac{8}{45}\times 10^{-16}+\frac{4}{35}\times 10^{-22}+\frac{128}{1575}\times 10^{-28}+\frac{128}{2079}\times 10^{-34}+\cdots$

なる展開を得ました*2。更に、一般には

$\displaystyle s^2=4hd\left(1+\frac{1}{3}\cdot\frac{h}{d}+\frac{8}{45}\cdot\left(\frac{h}{d}\right)^2+\frac{4}{35}\cdot\left(\frac{h}{d}\right)^3+\frac{128}{1574}\cdot\left(\frac{h}{d}\right)^4+\frac{128}{2079}\cdot\left(\frac{h}{d}\right)^5+\cdots\right)$

となっていることを理解します。最後に建部は綴術によって

$\displaystyle \frac{1}{3}, \ \frac{8}{45}, \ \frac{4}{35}, \ \frac{128}{1574}, \ \frac{128}{2079}, \dots$

が

$\begin{align}&\frac{2^2}{3\cdot 4}, \quad \frac{2^2\cdot 4^2}{3\cdot 4\cdot 5 \cdot 6}, \quad \frac{2^2\cdot 4^2\cdot 6^2}{3\cdot 4\cdot 5 \cdot 6\cdot 7 \cdot 8}, \ \\ &\frac{2^2\cdot 4^2\cdot 6^2\cdot 8^2}{3\cdot 4\cdot 5 \cdot 6\cdot 7 \cdot 8\cdot 9 \cdot 10}, \quad \frac{2^2\cdot 4^2\cdot 6^2\cdot 8^2\cdot 10^2}{3\cdot 4\cdot 5 \cdot 6\cdot 7 \cdot 8\cdot 9 \cdot 10\cdot 11 \cdot 12}, \dots\end{align}$

となっていることを見抜きます。そうして、建部は無限級数展開

$\displaystyle s^2=4hd\left(1+\frac{2^2}{3\cdot 4}\cdot\frac{h}{d}+\frac{2^2\cdot 4^2}{3\cdot 4\cdot 5 \cdot 6}\cdot\left(\frac{h}{d}\right)^2+\frac{2^2\cdot 4^2\cdot 6^2}{3\cdot 4\cdot 5 \cdot 6\cdot 7 \cdot 8}\cdot\left(\frac{h}{d}\right)^3+\cdots\right)$

に到達しました。

$\angle COB=\theta$ とすると弧長の公式より

$\displaystyle \frac{s}{2} = \frac{d}{2}\theta$

であり、一方

$\displaystyle h=\frac{d}{2}-\frac{d}{2}\cos \theta= \sin^2\frac{\theta}{2}$

なので、

$\displaystyle s^2=4d^2\left(\arcsin\left(\sqrt{\frac{h}{d}}\right)\right)^2$

なる関係があります。また、

$\displaystyle \frac{2^2\cdot 4^2\cdots (2n-2)^2}{3\cdot 4 \cdot 5 \cdots (2n)}=\frac{4^{n-1}( (n-1)!)^2}{2^{-1}\cdot (2n)!}=\frac{2\cdot 4^{n-1}}{n^2\binom{2n}{n}}$

なので、 $\sqrt{\frac{h}{d}}=x$ とおくことによって、建部の式は $\arcsin^2$ のテイラー展開

$\displaystyle 2(\arcsin x)^2 = \sum_{n=1}^{\infty}\frac{(2x)^{2n}}{n^2\binom{2n}{n}}$

に他ならないことがわかりました。この発見はEulerより15年早いとのことです。 $x=1/2$ を代入すれば

$\displaystyle \sum_{n=1}^{\infty}\frac{1}{n^2\binom{2n}{n}}=\frac{\pi^2}{18}$

が得られます。

現代的な導出

$|x| < 1$ とする。

$\displaystyle \int_0^1\frac{\mathrm{d}t}{1-x^2+x^2t^2}=\frac{1}{x\sqrt{1-x^2}}\arctan\left(\frac{x}{\sqrt{1-x^2}}\right) = \frac{\arcsin x}{x\sqrt{1-x}^2}$

なので、

$\displaystyle \frac{\arcsin x}{\sqrt{1-x^2}}=\sum_{n=0}^{\infty}\left(\int_0^1(1-t^2)^n\mathrm{d}t\right)x^{2n+1}$

を得る。Chu-Vandermondeの恒等式

$\displaystyle \sum_{k=0}^n\frac{(-n)_k(b)_k}{(c)_kk!}=\frac{(c-b)_n}{(c)_n}$

に $b=\frac{3}{2}, c=\frac{1}{2}$ を代入することによって

$\displaystyle \sum_{k=0}^n\frac{(-1)^k\binom{n}{k}}{2k+1}=\frac{(2n)!!}{(2n+1)!!}$

となるので*3、

$\displaystyle \int_0^1(1-t^2)^n\mathrm{d}t = \int_0^1\sum_{k=0}^n(-1)^k\binom{n}{k}t^{2k}\mathrm{d}t=\sum_{k=0}^n\frac{(-1)^k\binom{n}{k}}{2k+1}=\frac{(2n)!!}{(2n+1)!!}$

と計算できる。従って、

$\displaystyle \frac{\arcsin x}{\sqrt{1-x^2}}=\sum_{n=0}^{\infty}\frac{(2n)!!}{(2n+1)!!}x^{2n+1}$

を得た。

$\displaystyle \frac{\mathrm{d}(\arcsin x)^2}{\mathrm{d}x}=\frac{2\arcsin x}{\sqrt{1-x^2}}$

なので、

$\begin{align} 2(\arcsin x)^2 &= 4\int_0^x\frac{\arcsin t}{\sqrt{1-t^2}}\mathrm{d}t = 4\int_0^x\left(\sum_{n=0}^{\infty}\frac{(2n)!!}{(2n+1)!!}t^{2n+1}\right)\mathrm{d}t \\ &=2\sum_{n=1}^{\infty}\frac{(2n-2)!!}{n\cdot (2n-1)!!}x^{2n} = \sum_{m=1}^{\infty}\frac{(2x)^{2n}}{n^2\binom{2n}{n}}\end{align}$

となり、所望のテイラー展開が示された。

参考文献

[1] 小川束, 円理の萌芽–建部賢弘の円周率計算–, 数理解析研究所講究録, 1019巻 (1997), 77–97.
[2] 村田全, 建部賢弘の数学とその思想, 科学図書館.
[3] 小松彦三郎, 綴術算経の異本と成立の順序, 数理解析研究所講究録, 1130巻 (2000) 229–244.

*1:建部が実際に記載した数値は第40位までが正しいらしいです。また、本に書かれている方法で $l_k^2$ について計算を実行すると第37位までしか求められないらしいです。

*2: $128/1575$ あたりから何番目の近似分数を採用するかが明確でなくなってきます。この辺については[3]で勉強できそうです。綴術算径には幾つかのヴァージョンがあってもっと数値を計算しているものもあるとのこと。

*3:二重階乗 - INTEGERS

2018-12-18

限定素数大富豪

素数大富豪

この記事は素数大富豪Advent Calendarの16日目の記事です。

adventar.org

おかげさまで私が考案したトランプゲーム『素数大富豪』は忘れ去られることなく、今もプレイヤーを増やし続けながら盛り上がっていると実感します。素数大富豪を愛する皆様に本当に感謝しています。

素数大富豪の研究が進むと色々と見えてくることがあり、例えば先手がかなり有利なゲームのようです。そこで、マモさんは先手有利を軽減するための遊び方を提言してくださっております。

先手有利を軽減するプレイ方法の紹介 - まもめも

他にも、ルール自体をある程度変更した素数大富豪で遊ぶことを提言してくださっている方もおられます。ruia_primeさんのb進素数大富豪やicqk3さんのガウス素数大富豪などがあります。

この記事では私も新しい素数大富豪の遊び方を一つ提案しようと思います。その名も『限定素数大富豪』。

発想の経緯

オリジナルの素数大富豪の発想の経緯は

integers.hatenablog.com

に書きました。また、最近になって梟老堂さんの『素数大富豪Lv. 0』が販売されました。

まずはこれらのゲームの分析を行いたいと思います。

素数大富豪は大富豪をベースとして考案されたゲームですが、出来上がったゲームはゲーム進行の型に限っても大富豪とは異なる要素を幾つか含んでいます(山札の存在や複数枚出しにおける十進法読みなど)。このようなゲームの型に基づいたゲームを『素数大富豪型ゲーム』と呼ぶことにしましょう。つまり、『素数大富豪型ゲーム』というトランプゲームの分類を新たに作り、素数大富豪と素数大富豪Lv. 0はともに素数大富豪型ゲームに属すというわけです。

素数大富豪は『素数大富豪型ゲーム』であって、更に『素数の暗記・博打要素』を持ったゲームとなっています。これは『素数コレクター』になるという新しい楽しみも生み出しました。大きい素数を知っているほどゲームに有利になるため、暗記が得意な人や素数大富豪で勝てるようになりたい人はどんどん大きい素数を覚えていっており、大会上位のプレイヤーは既に7枚出し以上を標準装備しつつあります(素数の暗記要素)。また、必ずしも勝つことにはこだわらないが、大きい素数と出会い、面白い語呂合わせを発見することを喜びとするような人々も現れました(素数の博打(=出会い)要素)。

一方で、暗記は基本的にはゲーム中に行うことではないため、(手札の引きが運なのは大富豪型である以上仕方ないですが、与えられた手札を用いてどういう戦略を取るかという)純粋な頭脳戦として遊ぼうと思ったときにたくさん暗記している人とそうでない人の間に大きな格差が生まれてしまいます。 $1001$ チェックなどの特殊な戦略があってそれはそれで面白いのですが、暗記格差が大きいとあまり有効ではありません。この辺の悩みはもりしーさんの記事にも書かれています。(多くの人間がそうだと思いますが)暗記が苦手な人にとっては、たとえ戦略を立てるのが上手であったとしても、素数大富豪はあまり強くなれないゲームとなってしまいます。

このようなある種のデメリットがありながら、素数大富豪のルールをこのようにデザインした理由は『ゲームで扱える素数の個数』が非常に多いことに多大なる魅力を感じたためです。素数好きとしてこの点で素数大富豪のルールに満足し、ゲーム性におけるデメリットの排除は必要に応じて素数大富豪の派生を作っていただければよいと判断しました。

素数大富豪Lv. 0はそうして作られた派生ゲームと見ることができます。『素数大富豪型ゲーム』でありながら、プレイヤー間格差を少なくするために『素数の暗記・博打要素』を著しく減らすことに成功しています。他にも素数大富豪はトランプゲームなので偶数が手札にたくさんあると初心者のうちは捌きにくいといった問題がありましたが、素数大富豪Lv. 0はカードの枚数も調整されています。また、カードデザインもとても素晴らしいです。ですが、ここでは『素数の暗記・博打要素』がどのように変更されたかをもう少し詳しく見ていきます。

『素数の暗記要素』は『ゲームで扱える素数の個数』を単純に減らすことによって実現されています。素数大富豪Lv. 0では基本的には一枚出しか二枚出ししかできず、カードの特殊効果で三枚出しを一部許しています。三枚出しができる場合も各カードが一桁でなければならないという制限を設けることによって三桁を超えることがありません(この制限がなければ三枚出しで六桁まで可能になってしまう)。ちなみに素数大富豪Lv. 0で出せる最大の素数は $1913$ です。一方で、扱える素数の個数が少なくても例えば三桁の素数を全て覚えている人は多くないでしょうから暗記要素(という素数大富豪の一つの楽しさ)が完全になくなったわけではありません。

『素数の博打要素』は『素数の暗記要素』が減ったことによって連動して減っています。また、各カードにヒントが書いてあるので更に減ります。それでも、ヒントが奇数である場合は「右からつけるのか」・「左からつけるのか」という運要素があります。このように博打要素(という素数大富豪の一つの楽しさ)も完全になくなったわけではありません。ちなみに素数大富豪では $n$ 枚出しで間違えると $n$ 枚手札が増えるというペナルティがありました。エゴサなどしているとこの点についてもっといい方法があったのではという指摘をよく見ます。ペナルティといいつつ手札を増やす戦略にもなりますし、オリジナルのルールは現行のままでよいと考えていますが、初心者向けにはペナルティを一律一枚とするというケースもよくあってペナルティが少なくてもゲームは可能です。素数大富豪Lv. 0では思い切ってペナルティなしとなっています(なお、10のカードがペナルティの特殊効果を持っている)。

素数大富豪Lv. 0はこのように『素数の暗記・博打要素』を減らしたゲームになっていますが、そのことによって『素数大富豪型ゲーム』の戦略性の部分が際立っています。なので、素数大富豪の持つ独特なフレイバーを味わいつつ対戦ゲームとして十分に楽しめる仕上がりになっていると感じます。

素数大富豪Lv. 0はもちろん素数コレクターには物足りないものとなっていますが、それは『素数の暗記・博打要素』のもつデメリットを減らすために作られたゲームである以上仕方のないことですし、『Lv. 0』は初心者向けなので、そこから興味を持っていただいた方には素数大富豪を遊んでもらうというのが本来の目的の一つでもあります。

素数大富豪Lv. 0をやってみて、私は『素数大富豪型ゲーム』のもつ戦略ゲーとしての面白さを再認識しました。素数大富豪は素数を暗記したらそれで最強というわけではありません。暗記の度合いによってプレイヤー間格差は生じますが、暗記レベルが同じプライヤー同士の戦いにおいては『戦略』も非常に重要になります。というのも、与えられた手札に対して組める素数は一般にたくさんあるので、どれが最善の出し方であるかを短時間で判断するのはとても頭を使うのです。

一方で、素数大富豪Lv. 0は三枚出しまでしかできないために、素数大富豪の『素数大富豪型ゲーム』としての面白さが一部失われているとも言えます。そこで私は次のような欲求に駆られました。

『素数の暗記・博打要素』をなくし『素数大富豪型ゲーム』の戦略性を著しく際立たせた頭脳ゲームでありながら、にもかかわらず『ゲームで扱える素数の個数』は膨大である

ようなゲームを作りたい。12/10の朝にこのように思って電車の中で考えたのが『限定素数大富豪』です。副産物的ゲーム要素としてトレーディングカードゲームが持つコレクト要素やデッキ構築の楽しみのような要素があると思っています。

ルール

前置きが長くなってしまいましたが、テストプレイができていないので細かい調整ができていません(申し訳ございません)。なので、ここではゲームのアイデアだけを述べさせていただきます。

大きな特徴：各対戦毎に出すことのできる数の集合 $S$ を用意する。

集合 $S$ は三毎出し以上で出せる素数 $N$ 個と合成数出しで出すことの出来る合成数とその素因数分解データの組 $M$ 個からなります。( $N$ と $M$ は調整次第としますが、例えば $N=50$ や $M=10$ はどうでしょう*1。)

各プレイヤーは $S$ の元が書かれた紙(または画面)を手元に置いてそれを参照しながらプレイします。基本的には素数大富豪と同じルールですが、カードの出し方を次のように変更します。

二枚出し以下とラマヌジャン革命については変更なし。
それ以外の数については $S$ に書かれている数しか(成立手としては)出せない。

カードの大きさと枚数は正しいが上記以外の出し方で場にカードを出した場合はとりあえずペナルティとしておきましょう(手札を増やしたい場面があると思うので)。

ルールは以上です。 $S$ の作り方としては例えば次のようなものが考えられると思います。

各プレイヤー $i$ が集合 $S_i$ を用意し、 $S:=\bigcup_iS_i$ とする。
二人対戦の場合、 $S$ は後手が用意する。
$S$ をランダム生成するプログラムを用意する。

1. 2. の場合、素数コレクト要素やTCGのデッキ構築の楽しみがあると思います。2. は先手有利を軽減できるかもしれません。また、『限定素数大富豪』には $S$ を作成する面倒がありますが、3. が出来ればそれはかなり軽減できるでしょう。

基本的な数を除いて出せる数が $S$ に制限されることから『限定』素数大富豪という名前にしました。付けた後にカイジの『限定ジャンケン』の存在を思い出しました。
また、合成数出しという特殊ルールを忘れた上で、 $S$ を素数に限定しなければ『ランダム大富豪』のようなゲームも作ることは出来ます。

*1:桁を増やすレベルでもっと多い方がいいかもしれません。また、「 $A$ 枚出し以下では少なくとも $B$ 組以上ずつ」というな調整も必要でしょう( $QK$ のような強さを持つものが量産されかねないため)。下の1. による方法で $S$ を定める場合は「 $B$ 組未満ならばそれらは棄却」のようにしてもいいかもしれません。