高速に暗算で素数判定する方法を晒してみる

そういえば、最近めっきり暗算で素数判定をしていません。それどころか生活の中で電卓を使う機会が少しずつ高まっている実感があり、いよいよ歳を重ねたことを意識せざるを得ない日々を過ごしています。

 

かつては、車の運転中に眠くなったときに前を走っている車のナンバーを素数判定して、4桁の素数を見つけた時に自然と上がるテンションを利用して眠気を覚ましたりなどよくしたものですが、最近では車を運転する機会も減り、そもそも日中眠くなることも少なくなり、余計に素数判定から遠い生活を送っています。

 

さて、そんな僕ではありますが、いざ素因数分解をすると「速っ!」と驚かれることがしばしばあります。特に速いつもりは無いのですが、素数素人の方々から見ると割りと速いのかもしれません。そこで、今回の記事では「僕が4桁の自然数を素因数分解する手順」を赤裸々に語ってみたいと思います。一体誰が得をするのかわかりませんが、昨今の素数ブーム(※)を見るに、意外とニーズがあろうと踏んで書くことにしました。

(※ そんなものはありません)

 

なお、普段は素数に興味の無いような顔をしているのに、素数の話をするとちょっと楽しそうにする人っていますよね。僕は彼らのことを「隠れ素数好き」と呼んでいますが、実は世の中には隠れ素数好きが多いことを僕は知っています。「素数のことをあまりよく知らないから、興味はあるけど素数好きを名乗れない…(モジモジ)」という恥じらいが邪魔をしているのかもしれませんが、そんなものは捨てて、是非素数好きを名乗りましょう。

 

 

閑話休題。

 

 

では、僕が行っている(4桁以下の自然数に対する)素因判定の暗算アルゴリズムを紹介します。

 

 

1. 100以下の素数を全て(25個)暗記する。

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

の25個ですが、基本的には九九に出てこない奇数は素数の可能性が高く、間違えやすいのは91(7*13)くらいでしょうか。他は素数ではないことが自明なものばかりです。まぁとりあえずこれらは暗記です。(暗記しないと計算すべき回数が増えてしまうので、損してしまいます。)

 

これらの素数を見かけたら「あ、これは素数だ。なぜなら覚えているから。」でおしまいですので、以降は100以上の自然数に対して素数判定を試みるものとします。

 

 

2. 偶数と5の倍数は無視。

当たり前ですね。

 

 

3. 3の倍数は無視。

これも当たり前ですが、ある自然数nが3の倍数かどうかを見分けるには「各桁の和が3の倍数の時に限り、nは3の倍数」という事実を使います。例えば9729という自然数であれば、9+7+2+9=27という計算をするだけで、「あぁ、3の倍数だな」と判定できます。

実際には、脳内では、両端の9は3の倍数なので無視して、7+2のみ計算すれば十分です。

 

 

4. 7の倍数か否かを判定する。

ここで少し難易度が上がりましたね。でも実は簡単です。一般的に割り算を暗算でやるのは大変なことだとは思いますが、一方で「割った余りがゼロか否かのみを判定する」ことは実はそんなに大変ではないのです。例えば、8591という自然数が7で割り切れるかどうかを考えてみましょう。まず、7000(7の倍数)を引いて1591について考えれば良いことがわかります。なぜなら、任意の整数から7の倍数を加減しても、7で割った余りは変わらないからです。同様に、1591から1400(7の倍数)を引いて191とします。次に、210(7の倍数)から191を引いて19として、19は7の倍数ではないので、結論として8591は7の倍数ではないと判断できます。

最後の方で210から191を引いたのは7の倍数を加減しているわけではありませんので余りは変わり得ますが、余りがゼロか否かは不変ですので、問題ありません。このテクニックを使うと素数判定が速くなります。

 

 

5. 11の倍数か否かを判定する。

これは7の倍数よりは簡単で、判定したい自然数の奇数桁目の和偶数桁目の和が11の倍数かどうかを判定すれば良いだけです。

例えば4829は、4+2=6、8+9=17、となり、6と17の差は11の倍数なので、4829は11の倍数と判定できます。

 

 

6. 13の倍数か否かを判定する。

7の倍数の時と同様に、足し算と引き算だけで判定します。例えば7559という数字は、7800(13の倍数)から引いて241、260(13の倍数)から引いて19、19は13の倍数ではないので、結果7559は13の倍数ではないと判定できます。この方法であれば、13の倍数か否かの判定が3秒もかからずに計算可能です。

 

7. 以降、17、19、23…と順に97までの素数について、倍数か否かを判定する。

もはやゴリ押しです。ただ、素数判定したい自然数の平方根以下の素数についてのみ考えれば十分です。例えば、2017を素数判定しようと思ったら43まで割れば良いので、2,3,5,7,11,13,17,19,23,29,31,37,41,43の14回の倍数判定をすれば良く、上記のように簡単に倍数判定できる2,3,5,11を除けば、たった10回の倍数判定をすれば素数判定ができてしまうのです。

もし平方根が正しく求められなくて47で割ってしまっても、無駄ではありますが問題はありません。50以上の素数で割る必要が無いことは、50の2乗が2500で2017より大きいことからすぐに判断できるかと思います。

実際にやってみると、2017は

(2,5)2の倍数でも5の倍数でもない。

(3)2+1+7=10なので3の倍数ではない。

(7)2100から引いて83、83は7の倍数ではない。

(11)2+1=3、7との差は4なので11の倍数ではない。

(13)1300を引いて717、650を引いて67、67は(素数なので)13の倍数ではない。

(17)1700を引いて317、340から引いて23、23は(素数なので)17の倍数ではない。

(19)1900を引いて117、95を引いて22、22は19の倍数ではない。

(23)2300から引いて283、230を引いて53、53は(素数なので)23の倍数ではない。

(29)2900から引いて883、870を引いて13、よって29の倍数ではない。

(31)1860を引いて157、155を引いて2、よって31の倍数ではない。

(37)2220から引いて203、222から引いて19、よって37の倍数ではない。

(41)2050から引いて33、よって41の倍数ではない。

(43)2150から引いて133、129を引いて4、よって43の倍数ではない。

 

以上より、素数であることがわかります。これらの計算は掛け算と足し算引き算のみを使っているに過ぎないため、割り算をやるよりは高速に素数判定できます。

 

 

 

というわけで、以上が僕の素数判定方法でした。もしもっと効率的に暗算する方法があれば、是非コメントやご連絡いただけると嬉しいです。(本当は1万以下の素数を全て暗記したいなぁとは思っているのですが…。)

15分でできるサーバーレス死活監視

Webサービスの死活監視をするためだけに別途サーバーを用意すると、その死活監視用のサーバーが死んでたらどうしようとビクビクして夜も寝られなくなります。そこでサーバーレスにすればその不安もわりと減るよね、という話は色々なところでされているわけですが、それをなるべく簡単に実現しようということで方法をメモがてら記しておきます。

 

今回の構成を端的にまとめると、

  • AWS Lambdaを利用する
  • Lambdaへのデプロイにはchaliceを利用する
  • 監視対象の情報はiniファイルに記述する
  • iniファイルはS3に配置する
  • CloudWatch Eventsによって定期的にLambdaを実行する

という感じです。

  

では早速作業してみましょう。AWSの各種サービスの扱いに慣れていれば15分もかからないと思います。

 

1. 事前準備

% sudo pip install chalice
% cat ~/.aws/config
[default]
region = ap-northeast-1
aws_access_key_id = <YOUR ACCESS KEY>
aws_secret_access_key = <YOUR SECRET KEY>

 

2. プロジェクトの作成/ソース配置/ひとまずデプロイ

% chalice new-project serverless-health-checker
% cd serverless-health-checker/
% ls -a
./  ../  .chalice/  .gitignore  app.py  requirements.txt
% git clone https://github.com/phero/serverless-health-checker-src.git
% ln -sf serverless-health-checker-src/* .
% chalice deploy
Initial creation of lambda function.
Updating IAM policy.

The following actions will be added to the execution policy:

logs:PutLogEvents
logs:CreateLogGroup
logs:CreateLogStream

Would you like to continue? [Y/n]: Y
Creating deployment package.
Lambda deploy done.
API Gateway rest API already found.
Deleting root resource id
Done deleting existing resources.
Deploying to: dev
https://xxxxxx.execute-api.ap-northeast-1.amazonaws.com/dev/

この時点で上記末尾のURLにアクセスしてみると何やらごちゃごちゃとエラーが表示されますが、これで正常です。

 

3. AWS Lambdaの設定

3-1. Lambdaの設定画面からserverless-health-checker(いつの間にか作成されているはずです)をクリックします。

f:id:phero:20170125213137p:plain

 

3-2. Codeのタブから環境変数(Environment variables)を入力します。

SLACK_CHANNEL 通知する先のSlackのチャネル名。"#"から始めるのと、事前にチャネルを作成しておくことをお忘れなく。
SLACK_WEBHOOK Slack Incoming WebhookのURL
SLACK_USERNAME 任意の名前でOK
S3_CONFIG_KEY_NAME 今回はconfig.ini決め打ちでOK
S3_CONFIG_BUCKET_NAME 上記のconfig.iniを置くS3のバケット名

f:id:phero:20170125213754p:plain

 3-3. TriggersのタブからAdd triggerをクリックし、

f:id:phero:20170125214009p:plain

3-4. CloudWatch Events - Scheduleを選択し、

f:id:phero:20170125214055p:plain

3-5. 死活監視をする間隔(下図の例では1分毎)を入力し、Submitボタンをクリックします。

f:id:phero:20170125214232p:plain

3-6. 最後にSaveボタンをクリックします。(これ忘れがちなので要注意です)

f:id:phero:20170125233322p:plain

 

4. S3へのiniファイルの配置

以下のような内容でconfig.iniというテキストファイルを作成します。

[DEFAULT]
status = 200
timeout = 5 [My Web Site 1]
url = <監視したいURL> [My Web Site 2]
url = <監視したいURL>

それをS3のバケット(S3_CONFIG_BUCKET_NAMEで指定したバケット)にconfig.iniという名前で配置してください。

 

5. S3へのアクセス権限の設定

5-1. IAMの設定ページからロールを確認すると serverless-health-checker というロールがこれまたいつの間にか作成されているので、それをクリックし、

f:id:phero:20170125215958p:plain

5-2. 「ポリシーをアタッチ」のボタンをクリックし、

f:id:phero:20170125220129p:plain

5-3. AmazonS3ReadOnlyAccessを選択し、画面右下の「ポリシーのアタッチ」ボタンをクリック。

f:id:phero:20170125220256p:plain

 

6. 動作確認

さきほどごちゃごちゃとエラーが表示されていた https://xxxxxx.execute-api.ap-northeast-1.amazonaws.com/dev/ のページにもう一度アクセスし、先ほどconfig.iniで指定したサイトのURLなどが表示されていれば作業完了です。

 

ためしにconfig.iniの内容を

[DEFAULT]
status = 200
timeout = 5
[My Web Site 1]
url = <監視したいURL>
timeout = 0.001
[My Web Site 2]
url = <監視したいURL>

などと変更し、わざとタイムアウトするようにしてみると、Slackに

f:id:phero:20170125223418p:plain

のようなメッセージが書き込まれるかと思います。

 

というわけで、サーバーレスの死活監視システムの構築方法でした。chaliceとても使いやすくて良いですね。

 

 

2017年年始のご挨拶

明けましておめでとうございます。

 

昨年は子供が保育園に通い始めたこともあり、それなりにバタバタとしていることが多かったような気がしますが、周りの方々のご理解やご協力のおかげで無事に1年を過ごすことができました。皆様には心より御礼申し上げます。

 

また、仕事上でも良い出会いに恵まれ、9月より株式会社クラウドリアルティという会社に勤めているのですが、ここのメンバーがひたすら優秀で個性に富んでおり、楽しく刺激的な日々を送っております。エンジニアやデザイナーを鋭意募集中ですので、一緒に働いてやってもよいぞという方はお気軽にご連絡いただければと思います。

 

それでは、今年もどうぞよろしくお願いいたします。

DjangoからGmail経由でメール送信する際の手順

Python+Djangoでの開発時にプログラムからメールを送信する際に設定すべきことがいくつかあるので、まとめておきます。(ほぼ自分用の備忘録ですが。)

Djangoとか関係なしにプログラムからGmail経由でメールを送信したいだけの方は下記の1と2のみ実施すれば大丈夫です。

 

1. Gmailアカウントを作成(もちろん既存のものでもOK)

これは説明不要なので省略。

 

2. Gmailのセキュリティ関連の設定を変更

(1) Gmailにログインした状態で、画面右上のアカウントアイコンをクリックしてからアカウントをクリック。

(2) ログインとセキュリティをクリック。

(3) 2段階認証プロセスをクリックしてから、有効にします。その際、電話番号を入力してPINコードを受け取る必要があります。

(4) 前の画面( https://myaccount.google.com/security )に戻り、アプリパスワードをクリック。

(5) 端末を選択からその他(名前を入力)を選択し、好きな名称を入力します。

(6) 下記のように16桁のアルファベットが4桁ごとに区切られて表示されているのでこれをメモします。(「メモしたり誰かと共有したりしないでください」とか書いてありますが、もしGoogle先生の言うことを遵守したい方は16桁を暗記してくださいね☆)

f:id:phero:20161026095048p:plain

(7) 動作確認として、以下のコードを実行してみます。

メールが届けば、これでGmail側の設定は完了です。

 

3. settings.pyにメール関連の設定を追加

下記の項目をsettings.pyに追記します。

  

以上でおしまいです。

AutoHotKeyで幸せになれる設定 vol.1

Windowsユーザーを見かける度に「AutoHotKeyいいよ! AutoHotKeyいいよ!」と啓蒙し続けて6年以上が経ちました。非エンジニアの方でAutoHotKeyを愛用してくれるようになった方が1人だけいるのが唯一にして最大の成果です(ちょっと寂しい)。

 

AutoHotKeyとはなんぞや、という方は下記の2つのポストをお暇な時にでも御覧ください。Macユーザーの方はそっとブラウザを閉じるか、AutoHotKeyのソースコードをMacやLinuxに移植して世界をより幸せにする挑戦をするか、お手元のMacを叩き壊してWindowsPCを購入し直すのがおすすめです。

 

 

さて、日々手元のAutoHotKeyのスクリプトを自分好みに改良し続けながら業務を1%ずつ効率化している僕ですが、この度「あぁ、これはなんて便利なんだ!」というショートカットに気付いてしまったので、それをシェアするためだけにこのポストを書いています。

 

その設定がこちらです。

2つの.ahkファイルがありますが、いずれか1つをお好みで採用すれば良いと思います。

 

これは何かというと、「クリップボードに英文がコピーされた状態で【変換キー + T】を押すと、Bing翻訳(あるいはGoogle翻訳)のWebページが開いて日本語の翻訳が見られる」というショートカットです。

 

例えば

AutoHotkey is a free, open source macro-creation and automation software utility that allows users to automate repetitive tasks. It is driven by a custom scripting language that is aimed specifically at providing keyboard shortcuts, otherwise known as hotkeys. 

 という文章がクリップボードにある状態で【変換キー + T】を押すと、Bing翻訳ならこんな画面が表示されます。

f:id:phero:20161005093141p:plain

 

Google翻訳ならこんな感じになります。

f:id:phero:20161005093226p:plain

 

画像中の日本語を読むとわかると思いますが、Bing翻訳がかなり優秀なのでBing翻訳を使うことをおすすめしておきます。

 

これで英語の文章を確認する作業が1%以上効率化できることは間違いないので、興味のある方は是非AutoHotKeyを試してみていただければと思います。

早生まれの子供は人権を侵害されているかもしれない

ちょっと過激なタイトルですが、誇張ではなく本当にそう感じています。なんの話かというと、保育園の話です。


早生まれではない子のことを「遅生まれ」というらしいですが、あまり馴染みがない言葉なので、本記事においては遅生まれの子のことを簡単のために「普通の子」と呼ぶことにします。別に早生まれの子が普通じゃないとは思っていませんので、その点はご了承ください。



さて、普通の子は以下のようなプロセスを経て保育園に入園します。

~ 普通の子の入園プロセス ~

  1. 産まれる。
  2. すくすく育つ。
  3. 次に初めて訪れた4月に保育園に入る。


一方、早生まれの子供は、

~ 早生まれの子の入園プロセス ~

  1. 産まれる。
  2. あっという間に4月が到来するので保育園には入れない。
  3. すくすく育つ。
  4. 翌年の4月に保育園に入る。


というプロセスで入園します。




ほとんどの認可保育園が4月に入園を受け付けるのですが、それまでに早生まれの子供は保育園に預けても大丈夫な状態まで育ちません。保育園によって「満◯ヶ月になっていないと受け入れ不可能」というのが異なり、例えばこんな感じだったりするのですが、まず生後数週間の子供は預けられません。というのも、赤ちゃんというのは産まれて1ヶ月の間はまともに外出すらできなくて、1ヶ月くらい経ってからやっと少しずつ日光を浴びられたり外にベビーカーで連れ出したりできる状態に育っていくものなので、保育園の立場からしても、産まれて3週間しか経ってないような子供を預かるなどというリスクの高いことはやりたくないでしょうし、それは当然のことです。



何が言いたいのかと言うと、つまり早生まれの子は0歳で迎えた4月時点では保育園に入るチャンスが無く、1歳になって迎えた4月に認可保育園にやっと入れる可能性があるということです。


一方、普通の子は0歳で迎えた4月時点で保育園に入れる可能性があり、そこで入れなくても1歳で迎えた4月時点でまた保育園に入れる可能性があるということです。



早生まれになってしまったがために、認可保育園に入園できる機会の数に差が出てしまうのは平等権の侵害ではないのでしょうか?弁護士ドットコムに相談してみようかな…)


うちの子はまさに早生まれで、先日ちょうど全ての認可保育園に断られました。妻は育児休暇中ですが、育児休暇も無限に取れるわけではありません。こんなに子育てがしづらい世の中では安心して子供を産めませんし、少子高齢化の流れから脱することも難しいのではないかと思います。


なお、入園できる機会の数が少ないだけではなく、「1歳児の募集人数は0歳児の募集人数より少なく、しかも応募人数は多い(※)」という状況もあり、不平等に拍車をかけています。(※自治体によりますが)


「4月入園だけではなく10月にも同人数入園できるようにする」とか「入園希望を出すのが初めての子供を優先する」とか、何かしらの対策があっても良いのではないかなと思います。



ちょっと余談にはなりますが、

  • 片親だと入園しやすい
  • 世帯年収が低いと入園しやすい
  • その地域に長く住んでると入園しやすい
  • 共働きだと入園しやすい

とか、色々な変数によって入園のしやすさが変わります(ポイント制になってます)。この中の「世帯年収が低いと入園しやすい(ポイントが高い)」というのもすごく理不尽だと思います。現状、「世帯年収が高い人ほど入園できず、かつ入園できた場合にも保育料が高額になる」のですが、差をつけるのって保育料だけで良くないですかね? 入園できる確率まで下げるのはちょっと酷いんじゃないかなぁと。僕みたいに「年収がズギャーンと下がる転職」をした場合、1年前の世帯年収が判断基準になるので、お金は無いわ保育園入れないわでかなりつらいです。




というわけでまとめると、これから子供を産もうとされている方は是非、

  • 子供が早生まれにならないように計画する・頑張る・運のよさを上げる
  • 子供が産まれる前後に年収を下げるような転職はしない

の2点、くれぐれもお気を付けください。



保育園に入りたい! 2016年版(日経BPムック) (日経BPムック 日経DUALの本)

保育園に入りたい! 2016年版(日経BPムック) (日経BPムック 日経DUALの本)

集合内の任意の2要素の差の二乗の総和

先日、Facebook社が年1回開催しているプログラミングコンテスト(以下、プロコン)である HackerCup というものに参加しました。自分はプロコンガチ勢ではなく趣味でたまに参加する程度なのですが、恥ずかしながらこのHackerCupの存在を今まで知らず、今年初めて参加してみたのでした。


QualificationRound(予選)、Round1,Round2、Round3、FinalRoundと続く中、自分は残念ながらRound2で敗退してしまったのですが、そのRound2で出題された問題の中で使える面白いテクニックを知るにあたりそこはかとなくテンションがあがったので、紹介したいと思います。プロコンガチ勢であれば当たり前のように使っているであろうテクニックらしいですが、自分は今回初めて知ったので、少しでも多くの人にこのテクニックが伝わればいいな、と。またプロコンに興味が無い人が少しでも興味を持ってくれればいいな、と。あるいは世の中に存在する遅いコードが一部でも高速になればいいな、と。そんな思いで書くことにします。(っていうか、珠玉のプログラミングとかハッカーのたのしみとかプログラミングコンテストチャレンジブックとかに書いてありそうな話題ですけど、気にしないことにします。)



では早速ですが問題です。

N個の整数、

 \displaystyle X_1, X_2, X_3, ... X_N

があります。

この中から任意の2つを選ぶ方法は

 \displaystyle \begin{eqnarray}{}_N C _2\end{eqnarray} = \frac{N * (N - 1)}{2}

通りありますが、その全ての選び方で選んだ2つの整数の差の2乗の総和を求めなさい。ただし、総和は相当大きな数値になるので、総和を 1000007(=10^6 + 7)で割った余りを求めなさい。


制限として、各値は

 \displaystyle 2 \leq N \leq 1,000,000

 \displaystyle -100,000,000 \leq X_i \leq 100,000,000 (1 \leq i \leq N)

を満たすものとします。


なお、入力ファイルは、1行目にNの値、2行目からN+1行目にX1からXNが1行に1つずつ記されているものとします。

入力ファイルサンプル1

3
-1
0
1

サンプル1の正解は、 \displaystyle (-1 - 0)^2 + (-1 - 1)^2 + (0 - 1)^2 = 6となります。

入力サンプル2

5
293842
238424
174234
924234
532800

サンプル2の正解は 181270 です。


さて、この時この入力ファイル(サイズ約9MB)に対して正解を求められますか?というのが今回の問題になります。N=1,000,000です。

この問題を見て「あぁアレね」とピンと来ていないエンジニアの方は、是非考えてみてください。多分楽しいので。もしあなたがエンジニアではなければ、身近にいるエンジニアに出題してみるのも面白いかもしれません。




以下、解説です。

続きを読む