Code golf 反省メモ（Square root of 1 in mod 1e300）（Ruby（というか数学））
挑戦した問題
http://golf.shinh.org/p.rb?Square+root+of+1+in+mod+1e300golf.shinh.org
要約
標準入力から与えられる３桁の数を下３桁に持つ自然数で、その平方数の10300での剰余が1となるようなものを求める。
ソースコード
自分の解答(62)
a=5;b=10**n=300;n.times{a=a*a%b};p [b-1,b-a=a*2-1,a][getc%3%3]
- A224473の数列の一般項を求める式をそのまま実装しています。（Rubyでは冪剰余を効率良く求める短いメソッドが無さそう（opensslをrequireする必要がありそう）なので、冪乗を求めつつ剰余を都度求める方針を採っています）
Ruby１位の方（mitchs様）の解答(41)の吟味
p (eval'n='+gets+'n-=n*n/2*n;'*8)%10**300
上記コードで問の解答が求まることについて
- nは常に奇数になる（自明では無い）ので、n-=n*n/2*nはn=(3*n-n**3)/2と等しくなります。
- n=(3*n-n**3)/2を繰返しても、nの平方数について常に10k（k>3）での剰余が１となっているので、n%1000がgetsの値となっていることは簡単に示せます。
- キモはn=(3*n-n**3)/2を繰返すごとに、nの平方数の10mでの剰余が1となるようなmが増加していき、8回の繰り返しでm>300となる点です。
ヌルい証明ですが、以下のように大体mは倍々で増加していくようです。
- 問の条件を満たす数は複数（２つ）ありますが、上述のように10m（m>300）での剰余が１となる前提であればそのうち１つに定まるので特に面倒な処理は必要ありません。
そもそも上記のコードに至る発想について
- 上記のコードで解答が得られることは納得できたのですが、そもそもn=(3*n-n**3)/2の漸化式をどのように発想できるのかはまだよく分かっていません。
出題者のtails様の解説エントリの中では「ちょっと試行錯誤」と表現されていますが、なかなか「ちょっと」でここに至れません。。。 - 問の背景には「無限小数」というものが有るようなので、tails様のエントリを改めてじっくり読んでみようと思います。上記で「nの平方数の10mでの剰余が1となるようなmが増加して」いくとまどろっこしく表現している部分が、すっきりと「収束」の概念で説明されています。
今後の Code golf に向けた反省
- より単純な漸化式に帰着できないか考えてみる。（言うは易し行うは難し……）
- 今回で言うとA224473の第300項を求める必要は無かった（300より大きいmについて第m項を求めればよい）ため、一般項を求めずに済む方法を考えてもよかった。
- 出題者の方がtwitterをやっている場合、直近ログを漁って出題背景を妄想すると、問題についてより深い考察ができるかも。
