mattyuuの数学ネタ集

世界は数式で溢れている

素数大富豪〜素数大富豪数判定機を作ってみた〜

この記事は、素数大富豪 Advent Calendar 2016 - Adventar 24日目の記事です。23日目はicqk3さんの素数大富豪ver2です。

icqk3さんの素数大富豪 ver.2にて「ラマヌジャン革命」が追加実装されていますが、「ラマヌジャン革命」と共に新たに公式ルールに加わることが決まった「合成数出しにおける指数表記出し」も実装されているようです。仕事が早い!

はじめに

素数大富豪が数学好きの間で静かなブームになっています。「素数大富豪って何ですか?」という方は、本アドベントカレンダー1日目のにせいさんの記事を読んでください。

nisei.hatenablog.com

私は素数大富豪を1回しかやったことがなく、戦略やゲームの中で出会った素数達について語れるレベルではありません。その観点では本アドベントカレンダー素数大富豪の玄人の方たちが存分に語っていますので、ぜひ読んでください。

私はコンピュータを使って面白いことわからないかなぁという観点で素数大富豪 AdventCalendar 2016に2回分登録させていただきました。本記事はその2つ目の投稿で、1つ目は12月6日に投稿しています。こちらも読んでいただけたら幸いです。

mattyuu.hatenadiary.com

素数大富豪数とは

素数の観点から考えると、1より大きい任意の整数は素数合成数かのいずれかになります。そして素数大富豪の観点から考えると、1より大きい任意の整数は素数大富豪数素数大富豪数のいずれかになります。

この記事では素数大富豪数を下記で定義しています。

素数大富豪数
素数大富豪にて、ペナルティを受けることなく手として出しうる数を「素数大富豪数」と呼ぶ。また、1より大きい整数のうち「素数大富豪数」でない数を「非素数大富豪数」と呼ぶ。

まず、素数大富豪素数*1はいずれも素数大富豪数になります。最大素数大富豪素数より大きい素数は、素数大富豪にて手として出すことができないため、全て非素数大富豪数になります。

素数大富豪には「合成数出し」というルールがあるため、素数大富豪数は合成数も含まれることに注意が必要です。例えば公式ルールで解説されている46,793という合成数73\times 641となるため、73641のカードを捨てることで場に出すことができます。そのため46,793素数大富豪数になります。

しかし、128128=2\times 2\times 2\times 2\times 2\times 2\times 2ですが、ジョーカー2枚を2として使っても7枚の2を場に捨てることができません。そのため128は非素数大富豪数になります(実は最小の非素数大富豪数です。)。

なお、本アドベントカレンダー22日目のせきゅーんさんの下記の記事にて、次回のルール改版時に「合成数出しにおける指数表記出し」ルールが公式ルールとして追加されることが予告されました。

integers.hatenablog.com

せきゅーんさんの記事でも言及されていますが、指数表記出しを行うことで128素数大富豪で出せるようになり、晴れて素数大富豪数に昇格する見通しです。なお、指数表記出しルール追加後の最小の非素数大富豪数は2000になります。突然の指名で2000もさぞかし驚いていることでしょう。今度はどうか2000も救ってあげてください。

素数大富豪数判定機

1より大きい整数を素数の観点、素数大富豪数の観点で分類すると、下記の4分類になります。1より大きい任意の整数は下記の分類のどこかただ1つだけに所属しています。

素数であるか否かは、(簡単かどうかは別にして)素因数分解を行うことで判定できます。しかし、素数大富豪数かどうかの判定は簡単でしょうか。

例えば、
\displaystyle
45,838,577,369,109,312

という数を見てこれが素数大富豪数かどうかを判定するのは難しいと思います。

数字列の最後の12の箇所で1のカードと2のカードを出すべきか、12のカードを出すべきかパッとわかりません。素因数に22,22,219が出てくるのであれば2のカードは温存しておくべきで12を出す必要がありそうです。しかし、素因数に121,212,127が出てくるのであれば逆に12を温存しておかないとカードが足りなくなります。

今回、1より大きい整数を入力すると、

  • その数が4つの分類のうちのどの分類になるのか
  • 素数大富豪数の場合に、どのようにカードを出せばいいのか

を出力する素数大富豪数判定プログラムを作成しました*2

本当はどのようなアルゴリズム素数大富豪数を判定しているのかを紹介したかったのですが、「合成数出しにおける指数表記出し」ルール追加後のプログラム修正時等の別の機会にさせていただきます。今回新ルールでの判定ロジックも作りたかったのですが、12月22日に追加されたルールということで時間が足りませんでした。新ルールでは分割数とか考える必要がありちょっと難しそうです。

この素数大富豪数判定機があれば、身の回りに溢れるあらゆる数たちが素数大富豪で活躍できる数であるかどうかがわかります。今回は素数大富豪数判定機を使って、いろいろな数の判定をしましたので、その紹介を行い締めさせていただきます。以下乱文が続きます。。

明日は本アドベントカレンダーの作成者にせいさんによるまとめの記事です。ありがとうございました。

最大素数大富豪メルセンヌ素数

2^n-1の形をした素数メルセンヌ素数といいます。8番目のメルセンヌ素数(2,147,483,647)までは素数大富豪素数であることがわかりました。そして9番目以降のメルセンヌ素数素数大富豪素数でした。そもそもメルセンヌ素数nに対して爆発的に大きくなっていくので、すぐに最大素数大富豪素数より大きくなってしまいます。

最大の素数大富豪数かつメルセンヌ数(最大素数大富豪メルセンヌ素数)は、8番目のメルセンヌ素数である

\displaystyle
2,147,483,647

で、最小の素数大富豪数メルセンヌ素数は(最小のエデンの園メルセンヌ素数)、は9番目のメルセンヌ素数である

\displaystyle
2,305,843,009,213,693,951

でした。なお、エデンの園素数とは素数大富豪で出すことができない素数です。

integers.hatenablog.com

最小のエデンの園双子素数

双子素数というのは差が2である素数の組のことです(せきゅーんさんによると、「数の組は素数とは言えないため、素数双子と呼ぶべき」とのことです。)。

最小の素数大富豪数の双子素数(最小のエデンの園双子素数)は

\displaystyle
70001


\displaystyle
70003

でした。

最小のエデンの園非正則素数

非正則素数とはなんですか?という方は下記をご参照ください。

integers.hatenablog.com

最小の素数大富豪数の非正則素数(最小のエデンの園非正則素数)は

\displaystyle
70009

でした。

フィボナッチ数列素数大富豪数性

フィボナッチ数列11235813というふうに直前の2項の和を次の項とする数列になります。

最小の素数大富豪フィボナッチ数(場に出すことができないフィボナッチ数)は
\displaystyle
75,025=5\times 5\times 3001
でした。

タクシー数

2番目のタクシー数までは素数大富豪数でしたが、それ以降は素数大富豪数合成数でした。

素数大富豪タクシー数

\displaystyle
\begin{split}
{\rm Ta}(1)&=2\\
\\ \qquad
{\rm Ta}(2)&=1729 = 7\times 13 \times 19\\
\end{split}

(1729合成数出ししなくても「ラマヌジャン革命」の数として使用可能です。)

素数大富豪数かつタクシー数

\displaystyle
\begin{split}
{\rm Ta}(3)&=87,539,319 = 3\times 3\times 3\times 7\times 31\times 67\times 223\\
\\ \qquad
{\rm Ta}(4)&=6,963,472,309,248 = 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 3\times 3\times 3\times 7\times 13\times 19\times 31\times 37\times 127\\
\\ \qquad
{\rm Ta}(5)&=48,988,659,276,962,496=2\times 2\times 2\times 2\times 2\times 2\times 3\times 3\times 3\times 7\times 7\times 7\times 7\times 13\times 19\times 43\times 73\times 97\times 157\\
{\rm Ta}(6)&=24,153,319,581,254,312,065,344 = 2\times 2\times 2\times 2\times 2\times 2 \times  3\times 3\times 3 \times 7\times 7\times 7\times 7 \times  13 \times  19 \times  43 \times  73 \times  79\times 79\times 79 \times  97 \times  157
\end{split}

タクシー数とはなんですか?という方は下記をご参照ください。

integers.hatenablog.com

ちなみにせきゅーんさんのタクシー数は素数大富豪数合成数でした。素数大富豪で使用可能です。さすがですね。

\displaystyle
6,058,655,748=2\times 2\times 3\times 3\times 31\times 151\times 157\times 229


integers.hatenablog.com

最大素数大富豪フェルマー

フェルマー数は2^{2^n}+1の形をした整数です。素数とは限りません。

5番目のフェルマー数までは素数大富豪素数でした。

\displaystyle
\begin{split}
{\rm F}(0) &= 2^1 + 1 = 3\\
\\ \qquad
{\rm F}(1) &= 2^2 + 1 = 5\\
\\ \qquad
{\rm F}(2) &= 2^4 + 1 = 17\\
\\ \qquad
{\rm F}(3) &= 2^8 + 1 = 257\\
\\ \qquad
{\rm F}(4) &= 2^{16} + 1 = 65,537\\
\end{split}

そして6番目のフェルマー数は素数大富豪数
\displaystyle
\begin{split}
{\rm F}(5) &= 2^{32} + 1 = 4,294,967,297= 641\times 6,700,417
\end{split}

しかし、7番目のフェルマー数は素数大富豪数合成数になります。

\displaystyle
\begin{split}
{\rm F}(6) &= 2^{32} + 1 = 18,446,744,073,709,551,617=274,177 \times 67,280,421,310,721
\end{split}

それ以降のフェルマー数で素数大富豪素数になるものはありません。よって最大の素数大富豪フェルマー数は、

\displaystyle
4,294,967,297

で、最小素数大富豪フェルマー数(最小の、素数大富豪数かつフェルマー数)は、

\displaystyle
18,446,744,073,709,551,617

になります。

最小の素数大富豪数かつ完全数


\displaystyle
33,550,336=2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 2\times 8,191

でした。

完全数って何?という方は下記をご参照ください。

integers.hatenablog.com

山の高さ

世界的に有名な山の標高はいずれも素数大富豪数合成数でした。意外に実戦で使えそう?

エベレスト(8,848m)
\displaystyle
8,848= 2\times 2\times 2\times 2\times 7\times 79

K2(8,611m)
\displaystyle
8,611=79\times 109

キリマンジャロ(5,895m)
\displaystyle
5,895=3 \times 3\times 5\times 131

モンブラン(4,809m)
\displaystyle
4,809=3\times 7\times 229

富士山標高(3,776m)
\displaystyle
3,776=2\times 2\times 2\times 2\times 2\times 2\times 59

【その他】
下記のような特徴的な合成数素数大富豪数でした。

\displaystyle
\begin{split}
&1,234,567,89=2\times 3\times 3\times 5\times 3,607\times 3,803 \\
\\ \qquad
&123,456,789=3\times 3\times 3607\times 3,803 \\
\\ \qquad
&12,345,678,910,111,213=113\times 125,693\times 869,211,457 \\
\end{split}

私の誕生日も素数大富豪数でした。。。やはり0がネック。

\displaystyle
19,860,207=3\times 67\times 98,807

*1:素数大富豪」に手として出しうる素数を「素数大富豪素数」と呼ぶ。by tsujimotterさん

*2:いつかjavascript等で誰もが使えるように公開できれば良いのですが、javascriptだけでは巨大な整数の素数判定が難しい気がします