リクレル数のソースを表示

{{unsolved|数学|十進数のリクレル数は存在するのか?}}
'''リクレル数'''（Lychrel number）とは、桁を前後反転させたものと自身との和を求め（この操作を'''リクレルプロセス'''と呼ぶ）、得られた値について同様の操作を[[反復法 (数値計算)|繰り返し]]たときに[[回文数]]にならない[[自然数]]のことである。このプロセスは、これに関連する最も有名な数に因んで「[[196]]アルゴリズム」と呼ばれることもある。[[十進数]]におけるリクレル数の存在は[[数学の未解決問題|まだ証明されていない]]が、196などの多くの数が[[ヒューリスティクス]]<ref>{{cite web |last=O'Bryant |first=Kevin |date=26 December 2012 |title=Reply to ''Status of the 196 conjecture?'' |website=[[Math Overflow]] |url=https://mathoverflow.net/q/117277 |accessdate=2020-08-17}}</ref>や統計的根拠に基づいてリクレル数であることが予想されている。リクレル(Lychrel)という名前は、ウェイド・ヴァンランディンガム(Wade VanLandingham)が、自身のガールフレンドのファーストネームであるシェリル(Cheryl)の[[アナグラム]]から名付けたものである<ref>{{Cite web|url=https://www.p196.org/faq.html|archiveurl=https://web.archive.org/web/20061201050326/https://www.p196.org/faq.html|url-status=dead|archivedate=2006-12-01|title=FAQ|accessdate=2020-08-17}}</ref>。

== リクレルプロセス ==
リクレルプロセスとは、桁を反転させた物と自身との和を求める操作である。例えば、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 は、[http://www.jasondoucette.com/pal/89 24ステップ]で回文数となり、最終的な値は''8813200023188''である。10,000以下の数では、多くの数が最終的に回文数となることが知られている。
*10,911 は、[http://www.jasondoucette.com/pal/10911 55ステップ]で28桁の回文数''4668731596684224866951378664''になる。

以下は、回文数になるまでのステップ数が多い非リクレル数の世界記録である。
*1186060307891929990 は、[http://www.jasondoucette.com/pal/1186060307891929990 261ステップ]で119桁の回文数''44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544''になる。これは、2005年にジェイソン・ドーセット(Jason Doucette)のアルゴリズムとプログラムを用いて求められたもので、当時の世界記録となった。
*2017年1月23日、ロシアの学生のAndrey S. Shchebetovが、119桁の回文数に到達するまでに261ステップを要する最初の126個の数列を発見したと自身のウェブサイトで発表した。この数列は、OEISで[[oeis:A281506|A281506]]として発表された。この数列の最小の数は、ドーセットが2005年に発見した既知の数であり、それ以外の125個は今回新たに発見されたものである。2017年5月12日までにこの数列は108864個まで拡張された。数列の最後の数は''1999291987030606810''だった。
*2019年4月26日、Rob van Nobelenは、回文数になるまでのステップ数が多い非リクレル数の世界記録を更新した。発見した数は''12000700000025339936491''で、[http://jasondoucette.com/pal/12000700000025339936491 288ステップ]を経て142桁の回文数に到達する。OEIS数列[[oeis:A326414|A326414]]には、現在知られている288ステップの非リクレル数19353600個が含まれている。

回文数を形成することが知られていない最小の数は[[196]]であり、これは最小のリクレル数の候補である。

リクレル数の桁が反転してできた数もリクレル数である。

=== プロセスの形式的定義 ===
''n'' を自然数とするとき、''b''進数（ただし ''b'' > 2）の'''リクレル関数''' <math>F_{b} : \mathbb{N} \rightarrow \mathbb{N}</math> を次のように定義する。
:<math>F_{b}(n) = n + \sum_{i = 0}^{k - 1} d_i b^{k - i - 1}</math>
ここで、<math>k = \lfloor \log_{b}{n} \rfloor + 1</math>は、数 ''n'' の''b''進数における桁数であり、
:<math>d_i = \frac{n \bmod{b^{i+1}} - n \bmod b^i}{b^i}</math>
は、各桁の値である。<math>F_{b}^{i + 1}(n) = 2 F_{b}^{i}(n)</math> のような自然数 ''i'' が存在しない場合、数 ''n'' はリクレル数である。ここで、<math>F^i</math> は <math>F</math> の <math>i</math>回目の[[反復合成写像]]である。

== 十進数のリクレル数 ==
[[2進数]]や[[16進数]]などの基数が2の累乗となっているものについてはリクレル数が存在する（リクレルプロセスを繰り返しても回文数にならない数が存在する）ことが証明されている<ref name="brown">{{cite web |last=Brown |first=Kevin |title=Digit Reversal Sums Leading to Palindromes |website=MathPages |url=https://www.mathpages.com/home/kmath004/kmath004.htm|accessdate=2020-08-17 }}</ref>が、基数が10、すなわち[[十進数]]については、そのような証明は見つかっていない。

[[196]]などはリクレル数ではないかと[[予想 (数学)|予想]]されているが、十進数の中でリクレル数であることが証明されているものは存在しない。リクレル数であることが予想されている数は、非公式に「候補リクレル数」(candidate Lychrel numbers)と呼ばれている。候補リクレル数の最初の数個は以下の通りである（{{OEIS|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桁以下のリクレル種子数の候補を全て特定した<ref>{{cite web |last=VanLandingham |first=Wade |title=Lychrel Records |website=p196.org |url=http://www.p196.org/lychrel_records.html |access-date=2011-08-29 |archive-url=https://web.archive.org/web/20160428155517/http://www.p196.org/lychrel_records.html |archive-date=2016-04-28 |url-status=dead }}</ref>。ウェイド・ヴァンランディンガムのサイトでは、発見されたリクレル種子数の候補の桁数ごとの総数をリストアップしている<ref>{{cite web |last=VanLandingham |first=Wade |title=Identified Seeds |website=p196.org |url=http://www.p196.org/lychrel_seeds.html |access-date=2011-08-29 |archive-url=https://web.archive.org/web/20160428161428/http://www.p196.org/lychrel_seeds.html |archive-date=2016-04-28 |url-status=dead }}</ref>。

ブルートフォース法は、{{仮リンク|ジョン・ウォーカー (プログラマ)|en|John Walker (programmer)|label=ジョン・ウォーカー}}によって最初に導入され、反復動作を利用するために改良されてきた。例えば、Vaughn Suiteは、各反復の最初と最後の数桁だけを保存するプログラムを考案し、反復全体をファイルに保存しなくても、何百万回もの反復で桁パターンのテストを実行できるようにした<ref>{{cite web |title=On Non-Brute Force Methods |url=http://home.cfl.rr.com/p196/math%20solutions.html |archiveurl=https://web.archive.org/web/20061015175443/http://home.cfl.rr.com/p196/math%20solutions.html |archivedate=2006-10-15|accessdate=2020-08-17}}</ref>。しかし、これまでのところ、リクレルプロセスの反復を回避するアルゴリズムは開発されていない。

== スレッド、種子数、親族数 ==
スレッド(thread)とは、ジェイソン・ドーセットの造語で、リクレルプロセスの反復を経て、回文数につながる場合もあれば、そうでない場合もある[[数列]]のことを指す。与えられた種子数(seed number)とそれに関連する親族数(kin number)は、同じスレッドに収束する。スレッドには元の種子数や親族数は含まれず、収束した後の両者に共通する数のみが含まれる。

種子数は、リクレル数のサブセットであり、回文数を生成しない各スレッドの最小の番号である。種子数は、回文数そのものであってもよい。種子数の最初の3つは上のリストで太字で示されている。

親族数は、リクレル数のサブセットであり、種子数を除くスレッドの全ての数、または1回の反復の後に与えられたスレッドに収束する任意の数が含まれる。この用語は1997年にKoji Yamashitaによって導入された。

==196問題==
196（十進数）は最小の候補リクレル数であるため、最も注目されている。196がリクレル数か否かを求める問題（回文数になるまで196のリクレルプロセスを繰り返すこと）は「196問題」と呼ばれる<ref>{{Cite web|和書|url=http://yutaka-nishiyama.sakura.ne.jp/math2010j/196_j.pdf|title=回文数と196|author=[[西山豊]]|accessdate=2020-08-17}}</ref>。

1980年代、196問題はマイクロコンピュータのホビイストの注目を集めた。[[ジム・バターフィールド]]らによる検索プログラムが、いくつかの大衆向けコンピュータ雑誌に掲載された<ref name="transactor406">{{cite journal
  |author=<!-- Staff writer; no byline -->
  |year=1984
  |title=Bits and Pieces
  |journal=[[The Transactor]]
  |publisher=[[Transactor Publishing]]
  |volume=4
  |issue=6
  |pages=16–23
  |url=https://archive.org/details/transactor-magazines-v4-i06
  |accessdate=26 December 2014
}}</ref><ref name="ahoy1984">{{cite journal |last=Rupert |first=Dale |date=October 1984 |title=Commodares: Programming Challenges |publisher=Ion International |journal=[[Ahoy!]] |number=10 |pages=23,97–98 |url=https://archive.org/details/ahoy-magazine-10}}</ref><ref name="ahoy1985">{{cite journal |last=Rupert |first=Dale |date=June 1985 |title=Commodares: Programming Challenges |journal=[[Ahoy!]] |publisher=Ion International |number=18 |pages=81–84,114 |url=https://archive.org/details/ahoy-magazine-18}}</ref>。

ジョン・ウォーカーは、リクレルプロセスを繰り返し、その都度回文数かどうかをチェックする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が[[分散処理]]を使用して<ref>{{cite conference |last1=Swierczewski |first1=Lukasz |last2=Dolbeau |first2=Romain |date=June 23, 2014 |title=The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest |conference=[[International Supercomputing Conference]] |location=[[Leipzig, Germany]] |url=http://www.isc-events.com/isc14_ap/presentationdetails.htm?t=presentation&o=264&a=select&ra=sessiondetails }}</ref>10億回の反復計算を行い413,930,770桁に到達し、2015年2月には10億桁に到達した<ref>{{cite web |last=Dolbeau |first=Romain |authorlink=Romain Dolbeau |title=The p196_mpi page |website=www.dolbeau.name |url=http://www.dolbeau.name/dolbeau/p196/p196.html|accessdate=2020-08-17}}</ref> 。未だに回文数には到達していない。

他の候補リクレル数、879, 1997, 7059 についても同じブルートフォース法によるリクレルプロセスの繰り返し計算が行われているが、これらについても未だに回文数には到達していない<ref>{{cite web|title=Lychrel Records |url=http://home.cfl.rr.com/p196/lychrel+records.html |archive-url=http://web.archive.bibalex.org/web/20031205093936/http://home.cfl.rr.com/p196/lychrel+records.html |archive-date=December 5, 2003 |url-status=dead |access-date=September 2, 2016 }}</ref>。

==他の基数==
2進数では、10110（10進数で22）は、4ステップ後に10110100、8ステップ後に1011101000、12ステップ後に101111010000となる。一般的に4''n''ステップ後には、最上位の桁から"10"、''n''+1個の"1"、"01"、''n''+1個の"0"となる数となり、リクレル数であることが証明されている。これらの数字はいずれも回文数ではない。

リクレル数は11, 17, 20, 26, およびすべての2の累乗の基数に存在することが証明されている<ref>See comment section in {{OEIS2C|id=A060382}}</ref><ref name="brown"/><ref>{{cite web |title=Letter from David Seal |url=http://www.mathpages.com/home/dseal.htm |access-date=2017-03-08 |archive-url=https://web.archive.org/web/20130530003702/http://mathpages.com/home/dseal.HTM |archive-date=2013-05-30 |url-status=dead }}</ref>。

各基数において、リクレル数（またはその候補数）の最小の数は次のとおりである（{{OEIS|id=A060382}}）。
{|class="wikitable"
|-
!''b''
!''b''進数の最小のリクレル数またはその候補<br>（括弧内は十進数での値）
|-
|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)
|}

==負数への拡張==
リクレル数は、各整数を表すために{{仮リンク|符号付桁表現|en|signed-digit representation}}<!-- [[符号付数値表現]]ではない -->を使用することにより、負の整数に拡張することができる。

==脚注==
{{Reflist}}

==関連項目==
* [[回文数]]

==外部リンク==
*{{OEIS el|sequencenumber=A023108|name=Positive integers which apparently never result in a palindrome under ...|formalname=Positive integers which apparently never result in a palindrome under repeated applications of the function f(x) = x + (x with digits reversed)}}
*[http://www.fourmilab.ch/documents/threeyears/threeyears.html John Walker] – Three years of computing
*[http://www.fourmilab.ch/documents/threeyears/two_months_more.html Tim Irvin] – About two months of computing
*[http://www.jasondoucette.com/worldrecords.html Jason Doucette – World records] – 196 Palindrome Quest, Most Delayed Palindromic Number
*[http://users.tmok.com/~pla/Lychrel/Lychrel.shtml Benjamin Despres]
*[https://web.archive.org/web/20061104023524/http://www.p196.org/ 196 and Other Lychrel Numbers] by Wade VanLandingham
*{{MathWorld|urlname=196-Algorithm|title=196-Algorithm}}
*[http://www.mathpages.com/home/kmath004/kmath004.htm MathPages – Digit Reversal Sums Leading to Palindromes]
*[https://www.youtube.com/watch?v=bN8PE3eljdA   NumberPhile]

{{DEFAULTSORT:りくれるすう}}
[[Category:数学に関する記事]]
[[Category:整数の類]]
[[Category:回文]]
[[Category:数学のオープンプロブレム]]