onewanのメモ帳

数式が書きたくて始めたブログ。twitter IDは @onewan

素数大富豪の並び替え

先日は、札幌で素数大富豪研究会に参加しました。幹事の方々の準備が万全で、研究会の冊子も充実したものになっておりました。次回の開催も決定したということで、喜ばしい限りです。

さて、研究会で話を聞いているうちに、素数大富豪の並び替えを行うWebサイトを作ろうと思い立ち、まずはプログラムを作りました。Google Colaboratoryであれば、7桁程度（たとえば、2468TQA）の並び替え素数も一瞬で出ます。

このプログラムをBrythonで動かしてみたのですが、どうやらインタプリタではなくて、JavaScriptにJIT コンパイルをしてから動かしているので、動作が重すぎて使えませんでした。眠い。

また後日、JSで書き直すか、別の方法を試して公開します。

素数大富豪ほぼ最大の合成数

昨日、今日と博物ふぇすてぃばるに参加して、素数大富豪の考案者である関真一朗氏の講演を聞き、素数大富豪をプレイしてきました。

関さんは本当に素数愛に溢れた方です。足し算しかしらない子供にも懇切丁寧に素数大富豪の遊び方を説明されていました。あの姿勢は見習いたいですね。

さて、素数大富豪をプレイする傍ら、素数大富豪ブースでカステラさん、はなぶさんから聞いた話を基に、合計で53枚使う合成数出しに関してプログラムを書いて求めてみました。

方針は、99887766544332{KKQQQJJTTA}Aの{}内を並び替えて素数を作り、

99887766544332{KKQQQJJTTA}T = 99887766544332{KKQQA2JJTTA}A * 2* 5

を出すことです。ただし、TとQは5枚のうちのいずれかがジョーカーになります。

これが本当に最大かどうかは証明していないので分かりませんが、ほぼ最大の合成数出しになるのでは。

プログラムは以下のGitHubに上げています。間違ってたら教えて下さいね。

競技プログラミングに手を出してみた (AtCoder Beginners Selections)

先日、とある集まりでAtCoderという競技プログラミングのコンテストの存在を教わった。

最近、Twitter界隈でも競プロという言葉が飛び交っていたので、言葉自体は知っていたが、実際に問題を見るとなかなか面白い。

まずはコンテストに挑戦する前に、以下の初心者用の問題をやると良いと言われたので、全部解いてみた。

AtCoder Beginners Selection - AtCoder

コードは以下に上げてあります。

Twitterにも書いたけど、競技プログラミングは、アルゴリズムの学習になる、他人の綺麗なコードが参考になる、最低限の実装を行う事でプログラミングへの精神的な壁を取り払える、楽しい、などの効果があると思う。

ルベーグ積分入門

藤田先生の『「集合と位相」をなぜ学ぶのか』で、ルベーグ積分について触れられていたので、テレンス・タオの『ルベーグ積分入門』を読み返してみた。

ルーベグ積分とは

高校などで習うリーマン積分では上手く定義しきれない対象に対する積分を、ルベーグ積分で上手く定義しています。

リーマン積分可能性はジョルダン可測性に深く関係しています。有界集合に限定したとしても、すべての集合がジョルダン可測という訳ではありません。例えば、一辺が1の正方形の有理数点の集合 $[0, 1 ]^{2} \cap \mathbb{Q}^{2}$ と、一辺が1の正方形から有理数点を除いた集合 $[0, 1 ]^{2} \setminus \mathbb{Q}^{2}$ は、共にジョルダン外測度は1、ジョルダン内測度は0となり、ジョルダン可測とならない。

そこで、ルベーグ測度とルベーグ可測性を、ジョルダン測度とジョルダン可測性から拡張する訳ですが、可測性の方はジョルダンが内測度と外測度の極限が一致する場合と定義したのに対して、外測度から定義することになります。

ルベーグ外測度

ジョルダン外測度は、任意の有界集合 $E \subset \mathbb{R}^{d}$ に対して、有限個の直方体で覆うのに対して、ルベーグ外測度では、可算個の直方体で覆うというもの。

${\displaystyle m^{*} (E) := \inf_{\cup_{n=1}^{\infty} B_{n} \supset E; B_{1}, B_{2}, \dots : 直方体} \Sigma_{n=1}^{\infty} | B_{n} | }$

ルベーグ可測性

集合 $E \subset \mathbb{R}^{d}$ がルベーグ可測であるとは、任意の $\epsilon$ > 0 に対して、 $m^{*} (U \setminus E) \le \epsilon$ となるような E を含む開集合 $U \subset \mathbb{R}^{d}$ が取れることをいう。もし E がルベーグ可測であれば、 $m(E) := m^{*} (E)$ のことをE のルベーグ測度と呼ぶ。

参考文献

[1] ルベーグ積分入門(第２刷), 著:テレンス・タオ, 監訳: 舟木直久, 訳:乙部厳己, 2017.02.10

素数大富豪３枚出し素数

前回、ミラー・ラビン素数判定法をPythonで実装して遊んでみたと書きましたが、そもそもは素数大富豪の３枚出し素数を列挙してみようと思って実装していたのでした。

結果は、以下のGitHubに上げました。コードの多重ループを増やせば、4枚出し、5枚出し、6枚出し、7枚出しにも対応出来ます。

GoogleのColaboratoryは、PCの環境設定をせずにクラウド上で手軽にPythonのコードが動かせるから便利ですね。

ミラー・ラビン素数判定法

素数判定のアルゴリズムとして高速なミラー・ラビン素数判定法をPythonで実行してみた。実行環境は、最近Deep Learningでお世話になっているColaboratory*1を利用してみた。

驚きの速さでした。

これは、Colaboratoryの動作環境に寄るものも大きいと思いますが、664桁で数秒とか速すぎない？

素数	桁数	おおよその計算時間
2¹²⁷⁹ -1*2	386桁	1秒
2²²⁰³ -1*3	664桁	4秒

コード

えいやで書いたので汚いですが、こんなコードです。
f:id:sosuu-daifugoh:20180624025030p:plain

参考文献

コードを書くのに以下のページを参考にしました。
ミラー–ラビン素数判定法 - Wikipedia qiita.com

*1:Googleが提供しているクラウドサービス。

*2:15番目のメルセンヌ素数。

*3:16番目のメルセンヌ素数。

JDLA G検定合格しました

6/16(土)に受験した日本ディープラーニング協会のジェネラリスト検定(通称、JDLA G検定)の合格通知を受け取りました。

http://www.jdla.org/news/detail/20180126001/

試験1週間前に受験を思い立って、そこから「AI白書2017」と「人工知能は人間を超えるか」を購入し、1週間で読み切ろうと思ったものの、購入してみると、前者の分量がべらぼう過ぎました。1割くらい読んでこれを全部精読するのは無理だと悟ったのは、試験前日でした。

そこからは"試験対策"にシフトしました。何故なら、この検定、結構受験料が非常に高いので、折角受けるなら合格だけはしておきたいと考えたからです。

"試験対策"は、どういうものかというと、主に情報収集に尽きます。ネットで第一回試験の問題傾向をググり、用語の意味を問う問題が多いと分かったので、機械学習関係の最近トレンドとなっている用語を検索してまとめました。

後は、深層学習の実装的な話ですが、こちらは最近「ゼロから作るディープラーニング」を進めていた事と、自身が数理系の出身であるため、特に問題ありませんでした。

とはいうものの、合格ギリギリの点数だったことは明らかなので、合格者として恥ずかしくないように、これから、もっときちんと勉強していきたいと思います。