リクレル数 – Wikipedia
リクレル数（Lychrel number）とは、桁を前後反転させたものと自身との和を求め（この操作をリクレルプロセスと呼ぶ）、得られた値について同様の操作を繰り返したときに回文数にならない自然数のことである。このプロセスは、これに関連する最も有名な数に因んで「196アルゴリズム」と呼ばれることもある。十進数におけるリクレル数の存在はまだ証明されていないが、196などの多くの数がヒューリスティクス[1]や統計的根拠に基づいてリクレル数であることが予想されている。リクレル(Lychrel)という名前は、ウェイド・ヴァンランディンガム(Wade VanLandingham)が、自身のガールフレンドのファーストネームであるシェリル(Cheryl)のアナグラムから名付けたものである[2]。
リクレルプロセス[編集]
リクレルプロセスとは、桁を反転させた物と自身との和を求める操作である。例えば、56なら 56 + 65 = 121 、125なら 125 + 521 = 646 のようになる。いくつかの数は、リクレルプロセスを繰り返す（得られた数字についてリクレルプロセスを適用する）と回文数になる。最終的に回文数になるものは、リクレル数ではない。1桁と2桁の数字は全て、リクレルプロセスを繰り返すと最終的に回文数になる。
10,000以下の数字の約80%は4ステップ以内、約90%は7ステップ以内に回文数になる。ここでは、リクレル数ではない数の例をいくつか挙げる。
- 56 は、1ステップで回文数になる: 56+65 = 121
- 57 は、2ステップで回文数になる: 57+75 = 132, 132+231 = 363
- 59 は、3ステップで回文数になる: 59+95 = 154, 154+451 = 605, 605+506 = 1111
- 89 は、24ステップで回文数となり、最終的な値は8813200023188である。10,000以下の数では、多くの数が最終的に回文数となることが知られている。
- 10,911 は、55ステップで28桁の回文数4668731596684224866951378664になる。
以下は、回文数になるまでのステップ数が多い非リクレル数の世界記録である。
- 1186060307891929990 は、261ステップで119桁の回文数44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544になる。これは、2005年にジェイソン・ドーセット(Jason Doucette)のアルゴリズムとプログラムを用いて求められたもので、当時の世界記録となった。
- 2017年1月23日、ロシアの学生のAndrey S. Shchebetovが、119桁の回文数に到達するまでに261ステップを要する最初の126個の数列を発見したと自身のウェブサイトで発表した。この数列は、OEISでA281506として発表された。この数列の最小の数は、ドーセットが2005年に発見した既知の数であり、それ以外の125個は今回新たに発見されたものである。2017年5月12日までにこの数列は108864個まで拡張された。数列の最後の数は1999291987030606810だった。
- 2019年4月26日、Rob van Nobelenは、回文数になるまでのステップ数が多い非リクレル数の世界記録を更新した。発見した数は12000700000025339936491で、288ステップを経て142桁の回文数に到達する。OEIS数列A326414には、現在知られている288ステップの非リクレル数19353600個が含まれている。
回文数を形成することが知られていない最小の数は196であり、これは最小のリクレル数の候補である。
リクレル数の桁が反転してできた数もリクレル数である。
プロセスの形式的定義[編集]
n を自然数とするとき、b進数（ただし b > 2）のリクレル関数
を次のように定義する。
- Fb(n)=n+∑i=0k−1dibk−i−1{displaystyle F_{b}(n)=n+sum _{i=0}^{k-1}d_{i}b^{k-i-1}}
ここで、
k=⌊logbn⌋+1{displaystyle k=lfloor log _{b}{n}rfloor +1}は、数 n のb進数における桁数であり、
- di=nmodbi+1−nmodbibi{displaystyle d_{i}={frac {n{bmod {b^{i+1}}}-n{bmod {b}}^{i}}{b^{i}}}}
は、各桁の値である。
Fbi+1(n)=2Fbi(n){displaystyle F_{b}^{i+1}(n)=2F_{b}^{i}(n)}のような自然数 i が存在しない場合、数 n はリクレル数である。ここで、
Fi{displaystyle F^{i}}
は
F{displaystyle F}
の
i{displaystyle i}
回目の反復合成写像である。
十進数のリクレル数[編集]
2進数や16進数などの基数が2の累乗となっているものについてはリクレル数が存在する（リクレルプロセスを繰り返しても回文数にならない数が存在する）ことが証明されている[3]が、基数が10、すなわち十進数については、そのような証明は見つかっていない。
196などはリクレル数ではないかと予想されているが、十進数の中でリクレル数であることが証明されているものは存在しない。リクレル数であることが予想されている数は、非公式に「候補リクレル数」(candidate Lychrel numbers)と呼ばれている。候補リクレル数の最初の数個は以下の通りである（オンライン整数列大辞典の数列 A023108）。
- 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997
太字は、リクレル種子数(Lychrel seed numbers)（下記参照）の疑いがあるものである。ジェイソン・ドーセット、イアン・ピーターズ(Ian Peters)、ベンジャミン・デプレ(Benjamin Despres)のコンピュータプログラムにより、他の候補リクレル数が発見された。Benjamin Despresのプログラムは、17桁以下のリクレル種子数の候補を全て特定した[4]。ウェイド・ヴァンランディンガムのサイトでは、発見されたリクレル種子数の候補の桁数ごとの総数をリストアップしている[5]。
ブルートフォース法は、ジョン・ウォーカーによって最初に導入され、反復動作を利用するために改良されてきた。例えば、Vaughn Suiteは、各反復の最初と最後の数桁だけを保存するプログラムを考案し、反復全体をファイルに保存しなくても、何百万回もの反復で桁パターンのテストを実行できるようにした[6]。しかし、これまでのところ、リクレルプロセスの反復を回避するアルゴリズムは開発されていない。
スレッド、種子数、親族数[編集]
スレッド(thread)とは、ジェイソン・ドーセットの造語で、リクレルプロセスの反復を経て、回文数につながる場合もあれば、そうでない場合もある数列のことを指す。与えられた種子数(seed number)とそれに関連する親族数(kin number)は、同じスレッドに収束する。スレッドには元の種子数や親族数は含まれず、収束した後の両者に共通する数のみが含まれる。
種子数は、リクレル数のサブセットであり、回文数を生成しない各スレッドの最小の番号である。種子数は、回文数そのものであってもよい。種子数の最初の3つは上のリストで太字で示されている。
親族数は、リクレル数のサブセットであり、種子数を除くスレッドの全ての数、または1回の反復の後に与えられたスレッドに収束する任意の数が含まれる。この用語は1997年にKoji Yamashitaによって導入された。
196（十進数）は最小の候補リクレル数であるため、最も注目されている。196がリクレル数か否かを求める問題（回文数になるまで196のリクレルプロセスを繰り返すこと）は「196問題」と呼ばれる[7]。
1980年代、196問題はマイクロコンピュータのホビイストの注目を集めた。ジム・バターフィールドらによる検索プログラムが、いくつかの大衆向けコンピュータ雑誌に掲載された[8][9][10]。
ジョン・ウォーカーは、リクレルプロセスを繰り返し、その都度回文数かどうかをチェックするCプログラムを書き、1987年8月12日にSun 3/260ワークステーションでプログラムを動かし始めた。このプログラムはバックグラウンドで優先度を低くして動作し、2時間ごとにファイルに復元ポイントを書き出し、システムがシャットダウンされると、これまでに到達した数と反復回数を記録した。システムがシャットダウンされるたびに、最後の復元ポイントから自動的に再起動した。約3年間稼働した後、1990年5月24日に100万桁に到達したため、以下のメッセージと共にプログラムは終了した。
- Stop point reached on pass 2,415,836.
- Number contains 1,000,000 digits.
196は2,415,836回の反復を経て100万桁の数にまで成長していたが、回文数にはならなかった。ウォーカーは、最後の復元ポイントとともに自分の発見をインターネット上で公開し、これまでに到達した数を使っての探索の再開を他の人に呼びかけた。
1995年、ティム・アービン(Tim Irvin)とラリー・シムキンス(Larry Simkins)は、マルチプロセッサのコンピュータを使って、わずか3か月で200万桁にまで到達したが、回文数にはならなかった。その後、ジェイソン・ドーセットもこれに続き、2000年5月には1250万桁に到達した。ウェイド・ヴァンランディンガムは、ドーセットのプログラムを使用して1,300万桁に到達した。これは、カナダの子供向け科学雑誌「Yes Mag: Canada’s Science Magazine for Kids」に掲載された記録である。2000年6月以降、ヴァンランディンガムは様々な愛好家が書いたプログラムを使って桁数を更新し続けている。2006年5月1日には3億桁（5～7日に1回100万桁のペース）を達成している。2011年にはRomain Dolbeauが分散処理を使用して[11]10億回の反復計算を行い413,930,770桁に到達し、2015年2月には10億桁に到達した[12] 。未だに回文数には到達していない。
他の候補リクレル数、879, 1997, 7059 についても同じブルートフォース法によるリクレルプロセスの繰り返し計算が行われているが、これらについても未だに回文数には到達していない[13]。
他の基数[編集]
2進数では、10110（10進数で22）は、4ステップ後に10110100、8ステップ後に1011101000、12ステップ後に101111010000となる。一般的に4nステップ後には、最上位の桁から”10″、n+1個の”1″、”01″、n+1個の”0″となる数となり、リクレル数であることが証明されている。これらの数字はいずれも回文数ではない。
リクレル数は11, 17, 20, 26, およびすべての2の累乗の基数に存在することが証明されている[14][3][15]。
各基数において、リクレル数（またはその候補数）の最小の数は次のとおりである（オンライン整数列大辞典の数列 A060382）。
| b | b進数の最小のリクレル数またはその候補 （括弧内は十進数での値） |
|---|---|
| 2 | 10110 (22) |
| 3 | 10211 (103) |
| 4 | 10202 (290) |
| 5 | 10313 (708) |
| 6 | 4555 (1079) |
| 7 | 10513 (2656) |
| 8 | 1775 (1021) |
| 9 | 728 (593) |
| 10 | 196 (196) |
| 11 | 83A (1011) |
| 12 | 179 (237) |
| 13 | 12CA (2701) |
| 14 | 1BB (361) |
| 15 | 1EC (447) |
| 16 | 19D (413) |
| 17 | B6G (3297) |
| 18 | 1AF (519) |
| 19 | HI (341) |
| 20 | IJ (379) |
| 21 | 1CI (711) |
| 22 | KL (461) |
| 23 | LM (505) |
| 24 | MN (551) |
| 25 | 1FM (1022) |
| 26 | OP (649) |
| 27 | PQ (701) |
| 28 | QR (755) |
| 29 | RS (811) |
| 30 | ST (869) |
負数への拡張[編集]
リクレル数は、各整数を表すために符号付桁表現を使用することにより、負の整数に拡張することができる。
- ^ O’Bryant, Kevin (2012年12月26日). “Reply to Status of the 196 conjecture?”. Math Overflow. 2020年8月17日閲覧。
- ^ “FAQ”. 2006年12月1日時点のオリジナルよりアーカイブ。2020年8月17日閲覧。
- ^ a b Brown, Kevin. “Digit Reversal Sums Leading to Palindromes”. MathPages. 2020年8月17日閲覧。
- ^ VanLandingham, Wade. “Lychrel Records”. p196.org. 2011年8月29日閲覧。
- ^ VanLandingham, Wade. “Identified Seeds”. p196.org. 2011年8月29日閲覧。
- ^ “On Non-Brute Force Methods”. 2006年10月15日時点のオリジナルよりアーカイブ。2020年8月17日閲覧。
- ^ 西山豊. “回文数と196”. 2020年8月17日閲覧。
- ^ “Bits and Pieces”. The Transactor (Transactor Publishing) 4 (6): 16–23. (1984). https://archive.org/details/transactor-magazines-v4-i06 2014年12月26日閲覧。.
- ^ Rupert, Dale (October 1984). “Commodares: Programming Challenges”. Ahoy! (Ion International) (10): 23,97–98. https://archive.org/details/ahoy-magazine-10.
- ^ Rupert, Dale (June 1985). “Commodares: Programming Challenges”. Ahoy! (Ion International) (18): 81–84,114. https://archive.org/details/ahoy-magazine-18.
- ^ Swierczewski, Lukasz; Dolbeau, Romain (June 23, 2014). “The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest”. International Supercomputing Conference. Leipzig, Germany. http://www.isc-events.com/isc14_ap/presentationdetails.htm?t=presentation&o=264&a=select&ra=sessiondetails
- ^ Dolbeau, Romain. “The p196_mpi page”. www.dolbeau.name. 2020年8月17日閲覧。
- ^ “Lychrel Records”. 2016年9月2日閲覧。
- ^ See comment section in A060382
- ^ “Letter from David Seal”. 2017年3月8日閲覧。
Recent Comments