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

はじめに

…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 であると解釈すると、いろいろ都合がいいことがわかります。その理由をいくつか挙げてみます。

理由１．10倍して1を加えると元に戻る

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

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

理由２．9倍して1を加えると0になる

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

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

理由３．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 の性質が出てくるのです。正の整数だったはずなのに、負の小数になってしまうのですから、不思議ですね

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

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

補足２．
全ての有理数が循環無限整数で表現できるわけではないようです。例えば 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進数 - Wikipedia

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

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

p-進世界へようこそ [PDF]（山崎隆雄、筑波大学）

おおお！ 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 です。

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

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

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

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

Trimorphic numbers

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

@saito_ta 面白そうなお話のところネタばれぽいですが…。検索すると https://t.co/h685AVeg5K ( trimorphic num ) が出てきますね。10進 x^2=1 は x^2≡1 mod 10^n にあたり、x^3≡x でもあるのですね。
— angel-p57 (@angel_p_57) 2015, 8月 26

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

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

Trimorphic number - Wikipedia, the free encyclopedia

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

ゴルフへの出題

1. 出題しました

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

Square root of 1 in mod 1e300 （現在は post mortem です。）

問題の内容は、「所定の300桁の値を出力せよ。その値は、2乗すると 10³⁰⁰ での剰余が 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桁だけを出力するようにしてもいいのですが、じつは、剰余を 10³⁰⁰ ではなくて 2×10³⁰⁰ で求めることでも題意の通りに一意に定まります。さらに、上述の想定解法において、1桁ずつ探索する際に、「下N桁が1」の代わりに「2×10^Nでの剰余が1」という条件を採用すれば、候補を常に1つに絞ることができて探索の必要がなくなり、実装を大幅に簡略化できます。

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

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

#!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 が遅いことはわかっていたのですが、これほどとは。自分出題の問題の解き方がわからないのですから、困りました。

#anagol http://t.co/wyB3kPBe0v 出題者が言うのもナニだけど、これPerlでまともに解けるのかな。ていうか、Perlの多倍長なんでこんなにオッソイの？
— 齊藤 (tails) (@saito_ta) 2015, 9月 14

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

3. Trimorphic numbers の一般項

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

A224476 - OEIS

とりあえず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 で解けました！

@saito_ta なるほどできた… てゆかこれ良問じゃね！？
— 齊藤 (tails) (@saito_ta) 2015, 9月 16

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 - n³) / 2
= (3(a + e) - (a + e)³) / 2
= (3a + 3e - (a³ + 3a²e + 3ae² + e³)) / 2
= (a(3 - a²) + 3(1-a²)e - 3ae² - e³) / 2

ここで a² = 1 (mod 10³⁰⁰) ですから、

= (2a + 3ae² - e³) / 2
= a + (3ae² - e³) / 2

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

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

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

まとめ

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

追記１

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

gmk.hatenablog.jp

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

追記２

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

ange1.hateblo.jp

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

追記３

漸化式 $(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$ を乗算するようにして利用されます。