No. 410 「出会い」ショートコード解説

はじめに

yukicoder コンテストで出題された問題 No. 410 「出会い」のショートコード(2016年8月13日現在)の解説です。

問題ページ: http://yukicoder.me/problems/no/410

ショートコード: http://yukicoder.me/submissions/110735

問題の概要

入力:

A B
C D

が与えられる(A,B,C,Dは整数)。(abs(A-C)+abs(B-D))*0.5 の値を出力せよ。

私の答案

tr - _|dc -e?sx?sy-d*vlxly-d*v+.5*p

35 bytes です。言語は Bash です。 tr と dc を呼び出しています。 dc は先日 yuki さんにお願いして導入してもらい、使えるようになりました。

dc とは?

逆ポーランド形式の無限精度の計算が行える卓上計算機」だそうです(出典: http://kazmax.zpp.jp/cmd/d/dc.1.html)。今日では、 RubyPython で精度を気にすることなく整数演算ができますが、かつて Perl の時代にはそういうわけにはいきませんでした。なまじっか Perl が使えてしまうせいで RubyPython を覚える気になれない私は、 dc にはまだまだお世話になっています。

コードの解説

まず、 tr - _ で、入力に含まれる - (マイナス)を全て _ (アンダースコア)に変換しています。これは、 dc の入力においては - (マイナス)は二項演算子であり、負号は _ (アンダースコア)で表すことになっているからです。(一方、出力においては負号は - (マイナス)です。つまり、 dc は自分が出力する数値を解釈できないという謎仕様です。)

次に、負号を変換した入力を dc に渡しています。 -e は perlruby の -e と同じで、スクリプトの直接指定です。そのスクリプトをトークンに分解すると、次のようになります。

? sx ? sy - d * v lx ly - d * v + .5 * p

? は、入力を1行読んで実行する、です。最初の ? で入力の A B が読まれ、次の ? で C D が読まれることになります。読まれた値は、スタックにプッシュされます。

sx は、スタックをポップして変数 x に格納する、です。最初の ? の実行後のスタックは A B ですので、 sx で x には B が入り、スタックは A だけになります。同様に、 sy で y には D が入り、スタックは A C になります。

- d * v という一連の命令が2回出てきます。 d はスタック先頭の値の複製、 v は(非負の)平方根です。つまり、スタック先頭の2つの値の差を2乗してその平方根を求めていますので、差の絶対値が得られます。

lx ly は、変数 x と y の値(つまり B と D )をスタックにプッシュします。

+ .5 * で、これらを足して 0.5 倍しています。 .5 *2 / のほうが短そうですが、デフォルトで商が整数になってしまうので、ここではうまくいきません。

p で結果を出力しています。

おわりに

解説の配信のとき、説明が必要っぽい雰囲気だと思ったので、書いてみましたが、いかがだったでしょうか。全く需要がない気もしますが、果たして最後まで読んでくれた人はいるのでしょうか。

gnupack 版 Emacs で IME の on/off に合わせてカーソルの色を変える方法

gnupack 版 Emacs とは

本家 GNU が配布している WindowsEmacs バイナリは、 IME が on のときに

  • 入力中の文字が画面に表示されない
  • C-x b などのキーシーケンスで b が IME に吸われる

などといった不具合があるため、日本語環境ではまともに使うことができません。(なお Emacs 自体が独自の辞書を備えた入力メソッド機能を内蔵しており、そちらを使えば上記の問題は起こりませんが、せっかく IME があるのだからそれを使いたいですよね。)

そこで、 gnupack というプロジェクトが、上記の問題を解決するパッチを当てた Emacs を独自にビルドし配布しています。これのお世話になっている人は多いと思います。私もそうです。

gnupack プロジェクト日本語トップページ - OSDN

(ところで、 gnupack が現在(2016年5月)単体で配布している最新の Emacs は 24.2 と若干古いのが気になります。今後も是非とも本家に追随するか、もしくは上記の問題を解消するパッチを本家に取り込んでもらうようにしてもらえると嬉しいです。なお Cygwin を含むフルパッケージのほうには Cygwin でビルドされた Emacs 24.5.1 が含まれているようですので、そちらを使えということかもしれませんが、 Emacs だけのために Cygwin を丸ごともう1セット導入するというのもなかなか厳しいものがあります。)

IME の on/off に合わせてカーソルの色を変える

例えば IME が on のときだけ Emacs のカーソルが赤くなるようにすると、とても快適です。これについて gnupack 版での設定方法を説明します。(なお MuleMeadow とは設定方法が異なります。また、以下の方法は本家 GNU 配布版 Emacs では使えません。)

やることは以下の3つです。いずれも ~/.emacs.d/init.d に書いておくといいと思います。

1.入力メソッドIME に設定

(setq default-input-method "W32-IME")

初期設定では default-input-method"japanese" に設定されているので "W32-IME" に変更します。この "W32-IME" という入力メソッド名は本家 GNU 配布版には存在しないものです。これを設定することにより、入力メソッドとして IME が使われるようになります。 C-\ (初期設定で toggle-input-medhod コマンドが割当てられている)を押して IME の on/off が切り替わるのを確かめてみてください。

2. [kanji] キーイベントの有効化

(global-set-key [kanji] 'toggle-input-method)

初期設定では [kanji] には ignore が割り当てられているので変更します。これを設定しなくても「半角/全角」キーを押せば IME の on/off は当然切り替わりますが、これを設定することにより、「半角/全角」キーを押して IME の状態を切り替えたときに、次に説明するフックが呼ばれるようになります。また [kanji] キーイベントは「半角/全角」キーを押したときだけでなく、例えば言語バーをマウスでクリックして IME の状態を切り替えたときなどにも発生するため、このときにもフックが呼ばれるようになります。

3.フックの登録

(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

IME が on になったときと off になったときにそれぞれ呼ばれるフックです。ここでカーソルの色を変えています。上記では IME が on のときに赤、 off のときに青ですが、好みに応じて変更してください。

まとめ

以下のコードをあなたの ~/.emacs.d/init.d の最後にコピペして下さい。

(setq default-input-method "W32-IME")
(global-set-key [kanji] 'toggle-input-method)
(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

幾何の問題

知っていればそのまんまですが、知らないと驚くと思います。(私は知らなかったので驚きました。ていうか、答えはわかっていますが解き方がわかりません。)

問題

\(t>0\) とし、点 \(P\) の座標を \((t,\dfrac{1}{2t})\) とします。

2点 \(A,B\) の座標をそれぞれ \((1,1),(-1,-1)\) とします。

このとき、 \(BP-AP\) を求めてください。

(\(BP\)は点\(B\)と点\(P\)との距離、\(AP\)は点\(A\)と点\(P\)との距離。その差を求めてください。)

解説

そうなのです!最初に「知っていればそのまんま」と書きましたが、「逆数のグラフが双曲線であることを」知っていれば、ということです。いや、ちっとも知りませんでした。

なるほど! \(\sqrt{b}-\sqrt{a}\) の形なので、有理化の要領で \(\sqrt{b}+\sqrt{a}\) を掛けたりしてみましたが、複雑化する一方でうまくいきませんでした。まるっと自乗してしまえばいいんですね。素晴らしいです。

解答

\[\begin{align}BP-AP &= \sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2} \\ (BP-AP)^2 &= \left(\sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2}\right)^2 \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\sqrt{\left((t-1)^2+(\dfrac{1}{2t}-1)^2\right)\left((t+1)^2+(\dfrac{1}{2t}+1)^2\right)} \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\left(t^2+(\dfrac{1}{2t})^2\right) \\ &= 4 \end{align}\]

よって \( |BP-AP| = 2 \) 。

\(t > 0 \) より \( BP-AP > 0 \) なので \( BP-AP = 2 \) 。

…ということのようです。合ってるかな?

1 から始めて 3x+1 と 4x+1 で生成される数の問題

ふと思い付いた問題ですが、自分ではよくわかりませんので、誰か解いて答えを教えてください。

\(x\) の初期値を \(1\) とします。
\(x\) に対して、次の操作 A または B を選んで、適用します。
A : \(x\) を \(3\) 倍してから \(1\) を加えます。(\(x:=3x+1\))
B : \(x\) を \(4\) 倍してから \(1\) を加えます。(\(x:=4x+1\))
これを任意の回数繰り返します。

例えば、最初に操作 B を行い(\( 1 \times 4 + 1 = 5 \))、次に操作 A を行うと(\( 5 \times 3 + 1 = 16 \))、 \(x\) の値は \(16\) になります。
これを、「 \(16\) の生成列は BA である」と表現します。

別の例として、 \(10000\) の生成列は ABBABBA です(確かめてみてください)。

ここで問題です。

異なる2つの生成列を持つような数は存在するでしょうか?
存在する場合には、例を示してください。
存在しない場合には、それを証明してください。

追記:寄せられた考察(2015年12月9日)

上記の問題に対して、何人かの方から、様々なアプローチの考察を頂きました。ありがとうございます。頂いた順に、結論だけ簡単にまとめて掲載します。(私の解釈に基づいて記載しているため、元々の表現と異なっていたり、結論自体が異なっているものもありますが、ご了承ください。また、最終的な結論の正しさが確認できないものについて、正しいと考えられる中間段階の結論を記載しているものもあります。)

  1. 最後の共通部分を取り除いた2つの異なる生成列の一方は A で終わり、もう一方は B で終わるため、生成される数は奇数である。
    ―― roiti (@roiti46)
  2. 最後の共通部分を取り除いた2つの異なる生成列を持つ数を \(36\) で割った余りは \(13\) である。
    ―― %20 (@henkoudekimasu)
  3. 2つの異なる生成列を持つ数は、4億以下には存在しない。
    ―― ろくかん松 (@rokukan)
  4. 最後の共通部分を取り除いた2つの異なる生成列の一方は AAAAAA で終わり、もう一方は BBB で終わる。
    ―― %20 (@henkoudekimasu)
  5. A のみからなる生成列と B のみからなる生成列とが同じ数を生成することはない。
    ―― %20 (@henkoudekimasu)
  6. 最後の共通部分を取り除いた2つの異なる生成列の一方は BBB で終わるので、生成される数を \(64\) で割った余りは \(21\) である。したがって、もう一方の生成列の最後の A の行う前の値を \(64\) で割った余りは \(28\) となる。
    ―― ぴろず (@p_shiki37)
  7. \( A = \begin{pmatrix} 3 & 1 \\ 0 & 1 \end{pmatrix} , B = \begin{pmatrix} 4 & 1 \\ 0 & 1 \end{pmatrix} \)
    と表現でき、これらを用いた2つの生成列を \( S_1 , S_2 \) とすると、
    \( {S_1}^{-1} S_2 = \begin{pmatrix} a & 1-a \\ 0 & 1 \end{pmatrix} \) の形になる。
    ―― ぬ (@nu4nu)
  8. 操作 A を \(3x+1\) の代わりに \(2x+1\) にした場合には、二進数で表した時に、 A は右に 1 を追加する操作、 B は右に 01 を追加する操作になるため、異なる生成列が同じ数を生成することはない。
    ―― roiti (@roiti46)
  9. 元の問題は、「\(n \ge 1 \) で定義される2つの異なる非負整数列 \( \{p[n]\},\{q[n]\} \) と正整数 \(X,Y \) であって、次を満たすものが存在するか」と同値。
    • \(p[1]=0,q[1]=1\) (「最後の操作が同じでない」と対応)
    • \( p[n+1]-p[n] \in \{0,1\} \) ( \(q\) も同様)
    • \( \sum_{k=1}^{X} 3^{p[k]} 4^{k-p[k]} = \sum_{k=1}^{Y} 3^{q[k]} 4^{k-q[k]} \)
    よって \( \#\{k|p[k]=0\} \equiv 0 \) mod \(3\) などが示される。
    ―― かならい (@sugarknri)

また、以下は私自身の考察です。

\(x\) の初期値を \(0\) にした場合、自明な解 A \(=\) B \(=1\) があります。
また、初期値を \(2\) にした場合、 ABAAAA \(=\) BBBBB \(=2389\) という解が見付かります(なので、解が存在しない証明で、初期値に依存せずに、このケースを含んでしまっているものは、誤りであることがすぐにわかります)。
初期値を他の自然数にした場合も含めて、これら以外に解は見付かっていません。

 

『シンプル・ライフゲーム』に参加した記念(解説なし)

CodeIQ で出題された『シンプル・ライフゲーム』というコードゴルフに参加しました。

codeiq.jp

Perl と C で最短を取ることができました。 Perl は初日からガチで臨んだので、全言語最短が取れて良かったです。 C は締切前日に気まぐれで始めて、ちゃんと競えないタイミングで最短を更新してしまったので、申し訳なかったです。

締切後に解答を公開したところ、 Perl の解説を angel さんが書いてくださいました! いつもながら的確でわかりやすいです。しかも、私のコードからさらに 3 文字も縮めています。

ange1.hateblo.jp

そして、 C の解説を、出題者の ozy さんが直々に書いてくださいました! 三連休の全てに仕事が入っている中、合間を縫って書いてくださったとのことです。

d.hatena.ne.jp

さらに、 CodeIQ MAGAZINE の公式の解説記事で、貴重な文字数をかなり割いて、 Perl の解説を書いてくださいました!「10の極意」など、魅せ方がさすがです。自分のコードなのに、ほほうと思ってしまいましたw

codeiq.jp

以上、 Perl も C も、 angel さんと ozy さんにすっかり解説していただいたので、私から付け足すことは何もありません。ありがとうございます!

 

『デスコロC #1』の感想

はじめに

デスコロC #1』で優勝しました!

codeiq.jp

前回が最終回だった tbpgr さんの『デスマコロシアム』シリーズを引き継いで、新たに ciel さんの『デスコロC』シリーズが始まりました。企画の内容は前シリーズとほとんど変わっていないはずですが、出題者が交代した影響は想像以上に大きいようで、全く違った雰囲気になっています。一言で言うと、超ガチです。スーパーガチです。その理由は、主に次の2点です。

  1. 『デスマコロシアム』シリーズ最大の特徴であった、役によるバトルが、バッサリとカットされ、一切の運要素が排除されています。
    • 前シリーズでは、コード長と言語ペナルティがトップに届いていなくても、僅差ならバトルでの逆転に期待することができましたし、大差でも「デスマーチ」による一発逆転が用意されていました。これにより、誰もが優勝の可能性を持って参加できました。
    • 今シリーズでは、純粋にコード長と言語ペナルティだけで競うため、トップに1ポイントでも負けていれば、絶対に優勝できず、絶望するしかありません。逆に言うと、トップの人はトーナメントの組み合わせにかかわらず優勝が約束されています。
  2. 出力文字列が、かなり複雑なものになっています。もはや、コーディングの工夫だけではどうにもならず、知識、考察、閃きなどの総合力が試されます。

また、途中経過が毎日ではなく数日おきだったり、ツイートのまとめが行われなかったりしたことも、ストイックさを醸し出す要因になっていたと思います。

私は、初日に2桁バイトのコードを提出し、そのまま最後までアベベのごとく独走状態でした。初日に提出した時点では、暫定トップに立ってみたもののすぐに追いつかれて後はガチゴルフ勝負、といういつもの展開を予想していたのですが、意外な展開となってしまいました。

私の解答

print/.$/gfor sort map/.{999}/?$_=$'.$&:y/9Zz0-z/Aa0-z/<s/s$/sNtUUVb/,(A^eUVb)x3822

Perl (83) です。3822回ループを回していますが、このうち先の2822回で1000文字のデータを生成し、後の1000回で1文字ずつローテートさせながら、ソートして出力しています。

問題の解説

この問題の出力文字列は、ある文字列をブロックソート(BWT)した結果になっています。短いコードを書くためには、このことに気付かなければなりません。

どうすればこれがブロックソートだと気付くのでしょうか? 出力文字列を見てまず気付くのは、同じ文字が連続して現れるなど、ある程度の規則性があることです。もちろん、今までのデスマコロシアムの出力文字列にも規則性がありました。今回違うのは、規則性がありながらも、具体的に調べていくと、細かい部分が不規則になっていて、これをそのままコードに落とすのは困難だということです。

次に気付くべきは、文字列の先頭付近にある、あからさまに怪しい $ の文字です。いかにも何かの終端を表していそうです。ところで、上記の Wikipedia の記事によると、ブロックソートの変換後のデータは「ccoaa, 3」のように、変換後の文字列と開始位置の組で表されています。しかし、変換前の文字列に終端文字を付加しておけば、開始位置の情報を別途持たなくても、変換後の文字列に埋め込まれた終端文字の位置から特定することができ、実際にそのような実装も存在します。

したがって、

  • ブロックソートの結果は同じ文字が連続する傾向がある
  • ブロックソートをするときには終端文字を付加することがある

この2つを知っていれば、もしかしてブロックソートかな? と気付くことができます。

推測ができたところで、実際にブロックソートであることを確認してみます。まず、出力文字列に現れる文字の出現頻度を、ASCIIコード順に調べると、次のようになります。

文字頻度
$ 1
0 16
1 16
2 16
3 16
4 17
5 17
6 15

次に、出力文字列を、先頭から、この頻度に従って切り分けてみます。

文字頻度文字列
$ 1 b
0 16 PP00$zzzuuuVVUUU
1 16 QQ11000vvvWWWVVV
2 16 RRR22211wwXXXWWW
3 16 SSS333222xxYYYXX
4 17 TTT444333yyyZZZYY
5 17 UUU555444zzzaaZZZ
6 15 VV66555000bbaaa

ちょうどいい位置で切れていますね。ブロックソートで間違いなさそうです。

次に、ブロックソートする前の文字列の生成ですが、結果記事によると、「線形合同法っぽい方法で生成」できるようです。これは全く気付きませんでした(○○○○○=「ROT13」かな?とか思っていました)。もし気付いていたら、もっと違ったコードになっていたかもしれませんね。私のコードでは、この文字列を6文字単位のローテートと解釈して、 y と s を使ってなんとか生成しています。

(2015/11/7追記)「線形合同法っぽい方法」の部分について、 angel さん(アイコンが急にかわいくなった!)が詳しく考察されています。

ange1.hateblo.jp

ところで、ブロックソートは、データを縮めるための前処理として行われるものですが、今回はコードを縮めるためにわざわざ圧縮元のデータに遡るところが面白いと思いました。下手をしたら、圧縮データを埋め込んで逆符号化したほうが短くなるなんてことにもなりかねないわけで、うまくバランス調整されていると感じました。

f:id:saito_ta:20151105224407p:plain

まとめ

今回の問題はかなり難易度が高かったようで、題意通りに解けた人がわずかしかいなかったとのことですが、私としては、今までの問題よりパズル的な要素が強くて、とても楽しめました。

ciel さん、出題及び集計お疲れ様でした。次回も楽しみにしています。

 

「無限整数」について考えたこと

はじめに

…111111 のように、無限桁の数字が並ぶ整数、「無限整数」の性質について、以前より興味がありました。なお、ここでの「無限整数」というのは私の造語であり、数学的には別の用語を用いてもっと精緻な議論がされているのだろうと思います(私は数学の素人です)。

f:id:saito_ta:20150922154814p:plain
「無限整数」のイメージ(右端が一の位)

実数の表記法に、無限小数というものがあります。例えば 1/3 = 0.333333… というやつです。また、円周率 π = 3.141592… も無限小数ですね。これらは、桁が細かくなるほうに無限に続いているので、値の大きさがイメージできます。先の円周率なら、大体 3.14 くらい、ということです。 3.14 より大きくて 3.15 より小さい、ともいえます。

f:id:saito_ta:20150922161648p:plain

では、「無限整数」の場合はどうでしょうか。万の位、億の位、兆の位、…と桁が大きくなるほうに無限に続いているため、値の大きさをイメージすることはできません。でも、先の …111111 の場合は、例えば、 10 で割ったら 1 余りそうだ、といった性質が見て取れます。単に無限大とするよりは、もっと考察の対象となる性質がありそうです。

そこで、以下では、「無限整数」というものが意味を成すと仮定して、その性質について考えてみます。

循環無限整数

無限小数には循環無限小数と非循環無限小数があって、循環無限小数のほうが考えやすいですね。必ず有理数であるなど、良い性質があります。

そこで、「無限整数」についても、まずは「循環無限整数」を考えてみることにします。例として、冒頭に挙げた …111111 という数を考えてみます。少し考えてみると、この数は -1/9 であると解釈すると、いろいろ都合がいいことがわかります。その理由をいくつか挙げてみます。

理由1.10倍して1を加えると元に戻る

…111111111111
↓10倍する
…1111111111110
↓1を加える
…1111111111111
↑元に戻った!

つまり、 x = …111111 とすると、 10x+1 = x が成り立ちます。よって x = -1/9 です。え、桁が増えてるって? まあ、無限桁が1桁増えたところで変わらないでしょう。

理由2.9倍して1を加えると0になる

…111111111111
↓9倍する
…999999999999
↓1を加える
…000000000000
↑全桁が0になった、ということは0だ!

つまり 9x+1=0 です。よって x = -1/9 ですね。え、無限の彼方に、繰り上がった0でない値があるだろうって? まあ、無限の彼方なら無視してもいいでしょう。

理由3.1/9を加えた値が、10倍(100倍、1000倍)しても不変

大胆にも、無限小数 0.111111… を加えてしまいます。

  …111111 + 0.111111…
= …111111.111111…
  ↑10倍しても、100倍しても、変わらない。ってことは0だね!

つまり、 x+1/9=10(x+1/9) よって x = -1/9 です。少々乱暴ですが。

このように、 …111111 という値にいろいろと変形を試みてみると、一貫して -1/9 の性質が出てくるのです。正の整数だったはずなのに、負の小数になってしまうのですから、不思議ですね

特に理由3は乱暴ながら面白くて、例えば …123123123 というような、複数桁が循環するような循環無限整数についても、同様に 0.123123123… = 123/999 を加えれば 0 になるので、 …123123123 = -123/999 ということがすぐにわかります。このことから、純粋な(循環節のみからなる)循環無限整数は、 -1 より大きく 0 以下の有理数に対応しているということがわかります。循環無限整数の性質が、すっかりわかってしまいました。

補足1.
では正の有理数は無限整数でどう表現できるのかというと、単純に普通の整数を加えればいいのです。例えば 8/9 = 1 + (-1/9) = 1 + …111111 = …111112 です。

補足2.
全ての有理数が循環無限整数で表現できるわけではないようです。例えば 1/2 は、どう頑張っても表現できません(非循環無限整数でも表せません)。

非循環無限整数

循環無限整数の性質はわかりましたから、あとは数字が循環しない「非循環無限整数」について考えたいと思います。

無限小数の場合、数字を適当に無限に並べたものであっても、値の大きさがイメージできるので、何らかの一つの値として認識できる気がします。しかし、無限整数の場合、数字を適当に無限に並べても、大きさはイメージできませんし、上述の循環無限整数に対する考察も無力っぽいので、果たしてその数の並びが何らかの値を表すものなのかどうかさえ、よくわかりません。数字を循環しないように規則的に並べたもの(例えば …100001000100101)についても同様です。

そこで、アプローチを変えて、「無限整数で表現できるとすれば非循環になるはずの数」を考えてみることにします。ここで、循環無限整数は必ず有理数になることが上記の考察でわかっていますから、もし無理数が無限整数で表現できれば、それは非循環になるはずです。対偶というやつですね(「叱られなければ勉強しない 」←→「勉強すれば叱られる」)。

2の平方根は無限整数では表現できない

まず、最も簡単な無理数と考えられる √2 (2の平方根)を考えてみることにします。2乗して2になるような無限整数を、一の位から上位に向かって1桁ずつ決定していけば良さそうです。しかし、この試みは、一の位でいきなり失敗します。2乗して10で割った余りが2になるような1桁の数は、存在しないのです。図らずも、「無限整数は2の平方根を表現することができない」ことが示されてしまいました。

1の平方根は?

ふと、では 1 の平方根ならどうだろうか? と思って確かめてみたところ、4つの無限整数が出てきました。

2乗して 1 になる無限整数のを探すプログラム(Perl スクリプト)は、次の通りです。このプログラムでは、一の位から上位に向かって51桁求めて、それらの下50桁をユニークに出力しています。

use bigint;
@a=('');
for $n (1..51) {
    for $a (@a) {
        for $d (0..9) {
            $t = $d.$a;
            if ($t**2%10**$n == 1) {
                push @b, $t;
            }
        }
    }
    @a=@b, @b=();
}
/./,++$a{$'} for @a;
print $_,"\n" for keys %a;

結果は次の通りです。

00000000000000000000000000000000000000000000000001
99999999999999999999999999999999999999999999999999
85153153538207781991786760045215487480163574218751
14846846461792218008213239954784512519836425781249

循環無限整数が2つと、非循環無限整数が2つ、出てきました。意味のありそうな非循環無限整数が発見された、記念すべき初めての例です!

これら4つの数のうち、最初の …000001 は普通の整数の 1 なので2乗して 1 になるのは当然、次の …999999 も -1 なのでまあ当然です。問題は、2つの非循環無限整数の意味というか正体です。どうやら互いに正負の関係にあるようですが、それ以外の素性がさっぱりわかりません。どういう数なのでしょう。ともあれ貴重な手掛かりなので、もう少し探ってみることにします。

p進数

ところで、数学の世界には、p進数というものがあるらしいです。

どうやら、p進数と「無限整数」はかなり似たもののようですが、p進数は p を素数に限定しているようです。一方、「無限整数」は暗黙に10進数を仮定しているため、p進数ではないということになります。このウィキペディアの記事によると、 p が素数でない場合には「2つの 0 でない p-進数の積が 0 になってしまうことや、逆数が存在しないことがある。」とのことなので、2乗して 1 になる無限整数が …001 と …999 以外に見つかったのも、10が素数でないことと関係しているのかもしれません。

もう一つ、手掛かりとなりそうな論文を見つけました。

おおお! 3進数では、なんと -2 の平方根が表現できるようです。p進数と実数とでは表現できる数の範囲が異なっていて、有理数はそれらの共通部分に含まれる、ということのようです。

1の平方根とpq進数

いろいろなn進数で 1 の平方根を探してみたところ、どうやら、 n が素数の場合(つまりp進数)や n が素数の冪乗の場合には ±1 しか出てこないのに対して、 n が異なる素数 p, q の積で表される場合には、10進数で確かめたときのように、 ±1 以外にもう1組出てくるようです。さらに、30進数のように n が3つの異なる素数の場合には、4組8個出てきます。どうやら、10進数のあの …751 という数は、2と5の狭間に紡ぎ出された数のようです。でも、どのように紡ぎ出されているのか、相変わらずわからないままです。

7進数での1の立方根

さらに実験を続けていくと、7進数では1の立方根(3乗すると 1 になる数のこと)が3つ出てくることに気付きました。

00000000000000000000000000000000000000000000000001
43214516604202226653431432053116412125443426203642
23452150062464440013235234613550254541223240463024

…001 は当然として、後の2つは何でしょうか? 10進数の 1 の平方根のときと似ているようですが、これらは微妙に正負の関係にはなっていないようで、和が 0 でなく -1 になっています。一方を x とすると、他方は -x-1 です。

ところで、立方根ですから x3 = 1 です。これを式変形すると、
x3 - 1 = 0
(x - 1)(x2 + x + 1) = 0
となります。もしかしたら、 x2 + x + 1 = 0 の解ではないでしょうか? 和が -1 になることは確かめられているので、あとは積を確かめます。サクッと dc でやってみます。

$ dc -e '7o7i??*p'
43214516604202226653431432053116412125443426203642
23452150062464440013235234613550254541223240463024
1420511032411144133256606146615413653451402652230000000000000000000000000000000000000000000000000001

やはり、 1 になりました! 和が -1 で積が 1 ですから、 x2 + x + 1 = 0 の解と係数の関係を満たします。7進数の 3 つの立方根の正体が判りました。

何やら重要な手掛かりを得た気がします。ということは、10進数の4つの平方根も、これと同じように x2 - 1 = 0 の何らかの別解になっているのでしょうか? しかし、これ以上考えが進みません。

Trimorphic numbers

そんな折、 angel さんから、 trimorphic numbers というものを教えていただきました。

ほほう… って、私が「1の平方根」と呼んでいるもの(を数列化したもの)の一般項が示されているではありませんか! 「2と5の狭間に紡ぎだされた」というのは、どうやらある程度当を得ていたようです。

ちなみに、 trimorphic number というのは、3乗した数の下位の桁が元の数(の全桁)と同じになるもののようで、例えば 25 なんかもそうです。

Trimorphic number - Wikipedia, the free encyclopedia

なので、 angel さんのご教示のとおり「1の平方根」は trimorphic number ですが、逆は必ずしも成り立ちません。どちらかというと、より特定性の高い「1の平方根」のほうが、この数(数列)を良く表していると思うのですが…。

ゴルフへの出題

1. 出題しました

ここまでに考えたことのまとめのつもりで、いつもお世話になっている Anarchy Golf に、 1 の平方根を求める問題を出題しました。

問題の内容は、「所定の300桁の値を出力せよ。その値は、2乗すると 10300 での剰余が 1 になる。その値の下3桁が入力で与えられる。」というものです。出力すべき「所定の値」は、解答者からは見えますが、解答者が提出するコードからは見えません。入力は3種類あります(751, 249, 999)。要するに、無限整数での 1 の平方根について、それぞれ、下300桁を求めてください、ということです。

出題時の想定解法としては、下4桁目(千の位)から上位に向かって1桁ずつ探索していく、というものでした。N桁目を求めるときには、N-1桁目まで求めた値の先頭に 0 ~ 9 の数字をそれぞれ付加してみて、2乗して下N桁が1になるものを選ぶ、という方法です。この想定のもと、300桁もあれば埋め込むよりも真面目に実装した方が短くなるかな、くらいに(ろくに検証もせずに)思って出題しました。

ざっと見たところ、 rolf さんの Python(135) がこの想定解法通りのようです。

なお、問題文には蛇足的に「これらの条件だけではその値が一意に決定しないかもしれない。」とも書いてあります。どいういうことかというと、上記の条件では最上位の桁に2通りの自由度があって、例えば 49999…999999 も条件を満たしてしまいます。これに対しては、 上記の rolf さんのコードのように最上位の桁の数字で正解を判別してもいいですし、1桁多く求めてから下300桁だけを出力するようにしてもいいのですが、じつは、剰余を 10300 ではなくて 2×10300 で求めることでも題意の通りに一意に定まります。さらに、上述の想定解法において、1桁ずつ探索する際に、「下N桁が1」の代わりに「2×10Nでの剰余が1」という条件を採用すれば、候補を常に1つに絞ることができて探索の必要がなくなり、実装を大幅に簡略化できます。

2. 想定解法で解けない!

というわけで、自分の問題に Perl で提出してみました。上述の想定解法です。もちろん、 2×10N での剰余を利用した、探索不要バージョンです。

#!perl -p
use bigint;
for$n(4..300){
    for$d(0..9){
        $_=$t,last if($t=$d.$_)**2%(2*10**$n)<2
    }
}

ところが、なんと、3回の実行の合計で8秒ほどかかってしまいます。文字数を犠牲にして 2*10**$n の部分をループの外に出したりしてみましたが、ほとんど効果がありませんし、 bmodpow も試しましたが、却って遅くなる始末です。また、最後のテストケース(999)では 9 が明らかに最頻出なので 9 を先に試したほうが速いのは確かですが、そもそも最初のケースで timeout してしまっています。

Perl の bigint が遅いことはわかっていたのですが、これほどとは。自分出題の問題の解き方がわからないのですから、困りました。

ところが、しばらくして問題ページを見てみたら、 mitchs さんと llhuii さんが見事 Perl で解いているではありませんか! なにかうまいやり方があるようです。

3. Trimorphic numbers の一般項

ここで思い出したのが、 angel さんに教えていただいた、あの trimorphic numbers の一般項の式です。

とりあえず1番のケース(751)だけであれば、この一般項の式を使って次のように書けます。

use bigint;
print+(2*16->bmodpow(5**299,1e300)-1)%1e300

少し考えると、次のように短縮できることがわかります(若干遅くなります)。

use bigint;
print 2*2->bmodpow($x=5e299,$x)-1

45文字です。いい感じです。

と思ったのですが、やはりこれも激烈に遅いのです。3秒ほどかかってしまいます。文字数を犠牲にして高速化するにしても、到底及びません。 

4. 桁の数字を直接求める

最初に提出しようとした想定解法のコードでは、各桁に 0 ~ 9 の数字をそれぞれ当てはめて試してみましたが、そうではなくて、この数字を直接求められないでしょうか?

1番目のテストケース(751)について、想定解法のコードの挙動を観察してみると、次のようなことがわかりました。すなわち、N-1桁目までの数の2乗のN桁目以上の部分を20で割った余り(なぜか必ず偶数なので10通り)が、N桁目の数字の 0 ~ 9 に直接対応している、ということです。具体的には、下表のように対応しています。

余り 0 2 4 6 8 10 12 14 16 18
N桁目 0 9 8 7 6 5 4 3 2 1

具体例として、「751」の次の桁を求めてみます。751を2乗して564001。4桁目以上の部分は564で、これを20で割った余りは4。4に対応する数字は8なので、「8751」となります。

冷静に考えてみれば、この事実は2乗の二項展開から導くことができます。「なぜか必ず偶数」なのは、出題の節で説明した「2通りの自由度」と同じ話であり、要するに奇数になるほうは探索で行き詰まるのです。

また、2番目と3番目のテストケース(249, 999)は、20で割った余りとN番目の数字との対応関係が1番目のテストケースの場合と異なりますが(下表)、それ以外は同じです。

余り 0 2 4 6 8 10 12 14 16 18
N桁目 0 1 2 3 4 5 6 7 8 9

なぜ対応関係が異なるのかは、やはり2乗の二項展開を考えればわかります。一の位の数字がそのまま乗率となって影響しているのです。

さて、これをそのまま(テストケースの場合分けを含んだまま)コードに落としてみます。次のようになります。

#!perl -p
use bigint;
for$n(3..299){
    $_=$_**2/10**$n/(/9$/?2:-2)%10 .$_
}

ところで、この場合分け(/9$/?2:-2 のところ)は、一の位が乗率になって生じているのですから、だったら $_ を掛けてやるだけでよさそうです。つまり、2乗ではなく、3乗にします。

#!perl -p
use bigint;
for$n(3..299){
    $_=$_**3/-2/10**$n%10 .$_
}

だいぶスッキリした形になりました。実行時間を計ってみると 2.5s と、間に合っています。やった、とうとう Perl で解けました!

5. 桁の制限を外したら二次収束!

ところで、上記のコードは下位から1桁ずつ数字を決定していっていますが、この一度に決定できるのが1桁だけという制限はどこから来ているのでしょうか? どうも考え当たりません。

そこで、試しに、1桁ずつの制限を外してみることにしました。具体的には、結果を %10 して先頭に付加する代わりに、 %10 せずに全桁をそのまま $_ に足し込んでやります。ちょっと試行錯誤してみたところ、「3倍から3乗を引いて2で割る」と辻褄が合うようです。

use bigint;
$n=<>; $n=($n*3-$n**3)/2%1e300 for 1..8; print $n;

(これは最終提出した50文字のコードを多少読みやすく書き直したものです。)

驚くべきことに、先程まで300回回していたループが、たったの8回で済んでしまっています。どういうことでしょうか。

0:                                                751 (3桁)
1: 99999999999999999999999999999999999999999788218751 (6桁)
2:                          4749331894286163574218751 (12桁)
3: 24281580101871438384291806045215487480163574218751 (24桁)
4: 11153153538207781991786760045215487480163574218751 (48桁)
5: 85153153538207781991786760045215487480163574218751 (96桁)

これは、ループごとの値の変化を表したものです(下50桁のみ)。赤の部分が、数字が合っている桁です。1回回るごとに、合っている桁数が2倍になっています。そう、二次収束しているのです! まるでニュートン法のようです。

先程の漸化式を調べてみましょう。「3倍から3乗を引いて2で割る」、つまり $n=($n*3-$n**3)/2 の部分です。これは、真の値を a 、現在の n の真の値からの誤差を e すなわち n = a + e とすると、

(3n - n3) / 2
= (3(a + e) - (a + e)3) / 2
= (3a + 3e - (a3 + 3a2e + 3ae2 + e3)) / 2
= (a(3 - a2) + 3(1-a2)e - 3ae2 - e3) / 2

ここで a2 = 1 (mod 10300) ですから、

= (2a + 3ae2 - e3) / 2
= a + (3ae2 - e3) / 2

となり、確かに2次以上の誤差しかなくなることがわかります。

ところで、ニュートン法では x ← x - f(x)/f'(x) のように微分を用いて収束させていきます。本問は「1の平方根」、つまり2乗して1になる数を求めているので、 f(x) = x2 - 1 です。あの3次式は x - f(x)/f'(x) の形になっていないのは明らかであり、従って、ニュートン法ではありません。では何なのでしょうか。

試しに、 f(x) を積分してみると、 F(x) = x3/3 - x + C となります。なんと、あの3次式は (F(n) - F(0)) × (-3/2) に一致します。これは単なる偶然なのか、それとも何か理由があるのか? もう少し考えてみたいところですが、私の数学力ではちょっと持て余しそうです…。

まとめ

勝手に思いついた「無限整数」というものについて、素人なりにいろいろと考えてみました。その過程において、いろいろ得るものがあったように思います。多分、群論とかその辺りを勉強すればもっと体系的な理解ができるのでしょうけれど、遊びとしてはひとまずこれで満足です。

追記1

GOTO M. さんが、ゴルフ問題の考察を書いてくださいました。ありがとうございます!

gmk.hatenablog.jp

「ちょっと試行錯誤」ではここに至れないというご指摘がありますが、1桁ずつ求めていたロジックからの変形で、特に苦労した記憶がないんですよね… 当然できると思ってやったらできた、という感じで。二次収束するとは思っていませんでしたが。

追記2

angel さんが、数学的側面の解説を書いてくださいました。ありがとうございます!

ange1.hateblo.jp

いやー、さすがです。10進無限整数における1の平方根については、これで丸裸ですね。開平算の図もとてもわかりやすい。はてなブログで MathJax 使えるんですね。こうかな? \[x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\] おおできた。

追記3

漸化式 \((3x-x^3) / 2\) の正体がわかりました。これは、(実数の)平方根の逆数を求めるときのニュートン法の漸化式です。

\[f(x) = \frac{1}{x^2} - a \Longrightarrow x - \frac{f(x)}{f'(x)} = \frac{3x-ax^3}{2}\]

上式において \(a=1\) です。

ちなみに、この方法では除算が不要なため、 \(\sqrt a\) を求める際、まずこの方法で \(1/\sqrt a\) を求めておいてから、その結果に \(a\) を乗算するようにして利用されます。