回文数の性質について

今日は6/16。616は左から読んでも右から読んでも616。・・・ということで、今回は「回文数」に関する話題を取り上げてみます。


 

 回文数とは

回文数(かいぶんすう;Palindromic number)とは、各位の数を反転させてできる整数と元の整数が同じであるようなものを指します。例えば、$121$や$4385834$などは回文数です。

そもそも「回文」とは、「新聞紙」や「竹やぶ焼けた」のように、順番をひっくり返しても全く同じように読める語や文のことを指しています。整数値についても、そのアナロジーから「回文数」という名前で呼ばれています。英語で回文は “palindrome” であり、回文数は “Palindromic number” と呼ばれています。中国語では日本と全く同じ「回文数」という名称で呼ばれています。

 

 $n$桁の回文数の個数

$n$桁の回文数の個数は

9, 9, 90, 90, 900, 900, 9000, 9000, …

という数列を成します。これはオンライン整数列辞典「OEIS」にA050683として登録されています。回文数自体はOEISのA002113として登録されています。

一般項$a_n$は $$a_n=9 \cdot 10^{\lfloor(n-1)/2\rfloor}$$で与えられ、$$a_{n}=10 a_{n-2}$$という漸化式が成り立ちます。ここで$\lfloor(n-1)/2\rfloor$は床関数で、$(n-1)/2$を超えない最大の整数を表しています。

$2k$ 桁の回文数は、最上位の数が$0$にならないように上$k$桁の数を決めれば自動的に決まります。また、$2k+1$ 桁の回文数は、左右中央の桁の数字を$0$~$9$のうちから選び、最上位の数が$0$にならないように上$k$桁の数を決めれば自動的に決まります。このことから、上記の一般項が導かれます(奇数桁とその次の偶数桁の回文数の個数が同じになるのはこのような理由によります)。

 

 偶数桁の回文数は$11$の倍数

鋭い数学的センスの持ち主であれば、偶数桁の回文数が「左右対称」であることからすべて$11$の倍数であることを見抜いてしまうかもしれません。

例えば、$100001$のように両端の数字が$1$で真ん中に$0$が偶数個だけ挟まっているような整数は$11$で割り切れます。これは$n$を正の整数として $10^{2n-1}+1$ を$11$で割った余りを合同式で考えれば納得できます。あるいは合同式を使わなくても、このような数が$11+99…990$($9$が偶数個)と書き直せることからも、偶数桁の回文数が$11$で割り切れることが説明できます。

偶数桁の回文数はこのような整数に$1$~$9$までの整数を乗じたものを幾つか足し合わせた和になっているので、常に$11$の倍数となります。これより、3桁以上の回文素数はすべて奇数桁(偶数桁の回文素数は$11$のみ)であることが従います。過去に数学検定でこの事実に関する問題が出題されているようです。

※因みに、2021年現在の時点で知られている最大の回文素数は$$10^{474500}+999 \times 10^{237249}+1$$です。上位20位までの回文素数がこちらのサイトにまとめられています。


また、$11$の倍数であるような回文数を数え上げさせる問題が最近のジュニア数学オリンピックに出題されています。

 

正の整数であって、一の位が$0$でなく、一の位から逆の順番で読んでも元の数と等しいものを回文数とよぶ。$10000$以下の正の整数のうち、$11$の倍数であるような回文数はいくつあるか。

(2020年 日本ジュニア数学オリンピック予選 第3問)

» 答えはこちら

正解は$107$個です。

» 閉じる

それから、かなり古いですがもっと難しい問題が算数オリンピックに出題されています。

 

ある$6$桁の回文数は、$95$で割り切れ、しかも、その商も回文数になるという。このような回文数をすべて求めよ。

(1995年 日本算数オリンピック予選 第3問)

» 答えはこちら

正解は$527725$です。因みに、$10^{10}$以下のものは以下の8個のみです。

5225、52725、527725、5277725、52255225、52777725、522505225、527777725

» 閉じる

大学入試だと、これも古いですが2001年の津田塾大の数学に、$11$で割り切れるような$5$桁の回文数のうちで最大のものと最小のものを求めさせる問題が出題されています。オマケ問題として付いていた設問ですが、これに関しては誘導設問を無視した方が寧ろ解きやすいのではないかと思います。

 

 回文数の逆数からなる無限級数は収束する

$1$~$10^k$までの回文数の逆数の和を計算したものを以下に示します。 

上限 $10^k$ 逆数の和
the sum of the reciprocals
$10$ 2.8289682539682537
$10^2$ 3.0861471861471856
$10^3$ 3.3190020006509102
$10^4$ 3.3421302129563510
$10^5$ 3.3651662022380453
$10^6$ 3.3674689702500697
$10^7$ 3.3697715736297990
$10^8$ 3.3700018324036383
$10^9$ 3.3702320909393553

回文数の逆数からなる無限級数は大体 $3.370283…$ という値に収束することが知られています。ただし、無限級数が収束するからといって回文数が有限個しかない訳ではありません。回文数は無数に存在します。

※参考:A118031 Decimal expansion of the sum of the reciprocals of the palindromic numbers

※逆数の和はプログラムで計算しています。以下はJulia言語でのコード例です。あまり数学的な方法ではないですが・・・。

# sum of the reciprocals of the palindromic numbers
function palindromic_rcplsum()
    sum = 0
    for m = 1:10^5
        rev = parse(Int,reverse(string(m)))
        if rev == m
            sum += 1/rev
        end
    end
    println(sum)
end
palindromic_rcplsum()

 

 全ての整数は高々3つの回文数の和で表せる

2017年に投稿された “Every positive integer is a sum of three palindromes” という論文によれば、5進法以上の記数法上では全ての整数が高々3つの回文数の和で表せることがアルゴリズムとともに示されています。$0$も回文数に含んでいるので自明な組は多いのですが、例えば$23805$であれば

のように3つの回文数の和で表せます。気になる方は “Sum of 3 Palindromes” というページで遊んでみてはいかがでしょう。

なお、”Sums of Palindromes: an Approach via Automata” という別の論文によれば、2進法~4進法の場合は高々4つの回文数で表せるそうです。

※「高々3つの回文数の和で表せる」と主張しているだけで一意性については何も保証していません。実際、「3つの回文数」として適する回文数の組は多くの場合、複数通り存在しています。

参考:
【論文】Every positive integer is a sum of three palindromes
【論文】Sums of Palindromes: an Approach via Automata
(右側の “PDF” (スマホなら”PDF”か”Download PDF”) をクリックすれば論文の内容が読めます)
【動画】
Every Number is the Sum of Three Palindromes – Numberphile

 

「リクレル数」と「196問題」

ある整数に対して各位の数字を反転させてできる数を「逆順数」と呼ぶことにします。ただしこれは一般的な名称ではないので注意して下さい。

ある整数に対して、自身とその逆順数との和を求める操作のことを「リクレルプロセス」と呼びます。例えば、$56$なら$$56 + 65 = 121$$となり、$125$なら$$125 + 521 = 646$$となります。これが1回のリクレルプロセスに相当します。

多くの数はリクレルプロセスを繰り返し適用すると、いずれは回文数になります。特に、1桁と2桁の数字は全て、リクレルプロセスを繰り返すと最終的に回文数になることが知られています。

※リクレルプロセスは以下のように計算できます。Julia言語でのコード例を示しておきます(最大1000回で打ち切り)。この例では$195$をリクレル関数に代入しています。

# Lychrel function
function Lychrel(n)
    count = 0
    for m = 1:1000 # 回数上限
        rev = parse(BigInt,reverse(string(n)))
        if rev == n
            count = m
            break
        else
            println(n)
            n += rev
        end
    end
    println("---------------\n", n, " : ", count-1)
end
Lychrel(195)   # 任意の整数

# 195
# 786
# 1473
# 5214
# ---------------
# 9339 : 4

ここで、何回リクレルプロセスを繰り返しても回文数にならない整数のことを「リクレル数」と呼びます。しかしこれはあくまでも定義でしかなく、十進数におけるリクレル数の存在は証明されていません。つまり「十進数のリクレル数は存在するのか?」という問いは数学の未解決問題なのです。

※$2$進数や$16$進数など、基数が$2$の累乗となっている記数法についてはリクレル数の存在が証明されています。他にも$11$進数、$17$進数、$20$進数、$26$進数について、それぞれリクレル数の存在が証明されています。

十進数の場合は証明ができていないだけで、リクレル数の候補は幾つか知られています。例えば、$196$などはリクレル数であると予想されています。

十進数における$196$は最小のリクレル数の候補であるため、リクレル数か否かについて特に注目されています。$196$がリクレル数か否かを判断する問題には「196問題」と特別に名前が付けられています。数十億回の反復後でも未だに回文は得られていないようです。リクレル数の存在を証明する一般的な方法を思い付いた方は是非とも論文にして発表して下さい・・・。

Romain Dolbeau氏のページからソースコードをダウンロードすれば「196問題」の分散コンピューティングに協力できるみたいです。

※「196問題」は「コラッツ予想」と似たような未解決問題と言えます。仕組み自体は簡単に理解できるのに、あっという間に未解決問題が登場してしまうのが数論の面白いところですね。この辺りの内容は幾らでも掘り下げられそうです。


 

“回文数の性質について” への7件の返信

  1. 回文数というタイトルを見て,眠れない夜中に計算してしまいました.偶数桁の回文数が11の倍数であることは割合簡単にわかりましたが,奇数桁の回文数で1と0だけのものは11の剰余が2と9だけになりますね.だからなんだという話ですが.ちなみに2+9=11です.なんか理由がありそう?

  2. M.E.T.A. さん

    お久しぶりです。
    こちらに直接書き込んで頂くのは初めてですね!
    ありがとうございます(笑)

    コメントを受けて少し計算してみました。
    「奇数桁の回文数で1と0だけのもの」について、11の剰余を9桁の回文数まで調べてみると以下のようになります。

    101 : 2
    10001 : 2
    10101 : 3
    11011 : 0
    1000001 : 2
    1001001 : 1
    1010101 : 4
    1011101 : 3
    1100011 : 0
    1101011 : 10
    1110111 : 2
    100000001 : 2
    100010001 : 3
    100101001 : 0
    100111001 : 1
    101000101 : 4
    101010101 : 5
    101101101 : 2
    101111101 : 3
    110000011 : 0
    110010011 : 1
    110101011 : 9
    110111011 : 10
    111000111 : 2
    111010111 : 3
    111101111 : 0

    もう少し先まで11の剰余を調べてみると、10101010101で6、1010101010101で7、11010101011で8となります。
    …という訳なので、各位の数字が1と0のみからなる奇数桁の回文数の11の剰余が2と9に限るということは無く、むしろ0~10まで全て登場するようです。
    私の方でコメントの意図を取り違えているようであれば教えて下さい…。

    ところで、このような形の回文数に対して、剰余のセットが限られるような奇数の法は5の倍数だけでしょうか?
    mod 1000 以下で調べても例外が見つからないので恐らくそうなのだろうとは思いますが、一般の場合に関する証明は知りません。
    もしアイデアをお持ちの方がいればコメントして頂けると幸いです。

  3.  ごめんなさい.
     言葉が足りませんでした.というか,完全にミス投稿です.冷静に考えず書いてしまった,とんでもない間違いで,すみません.
     寝床で考えたのは,奇数桁の回文数のいわばパーツとして1と0で構成される数で,101とか10001とか,最高位と第1位のみが1で間がすすべて0の回文数(基本回文数としておきます)が,11についての剰余が2になること,もうひとつは,回文数ではないのですが,1010とか,100010とか,先ほどの基本回文数を10倍したものは,11についての剰余が9になることを書くつもりでした.さらに,基本回文数を100倍すると11についての剰余は2に戻り,1000倍すると9になる,一般に10の偶数乗(0乗も含む)倍すると剰余が2に,10の奇数乗倍すると剰余が9になます.
     だから,「1と0で構成される奇数桁の回文数」というところは大間違いです.
     それと,基本回文数のうち1だけは例外で,剰余が1です.
     (1を10の偶数乗倍すると剰余は1,10の奇数乗倍すると剰余は10ですね)
     上で説明した数を要素とすると,任意の回文数は基本回文数1つと基本回文数の10^n倍の和に分解されることになります(あたりまえですが)
     たとえば,11011=10001+1010(つまり,基本回文数10001と基本回文数101の10倍の和)と考えると,11011が11で割り切れるのは自明ですが,10001は剰余が2,1010が剰余9ですので,その和は11で割り切れることになります.1も基本回文数ですので,たとえば11111=10001+1010+100
    とできますが,11についての剰余は10001は2,1010は9で,100は1です.2+9+1=12ですから,11111の剰余は1(これもこんなこと考えるまでもなくすぐわかる話ですが)
     なんか,書いてるうちにつまらないことに見えてきてしまいました.
    すみません.恥ずかしいです.
     あと,以上の話にからんで,11の倍数判定法で,各桁の数を足したり引いたりするものがありますが,これで11についての剰余を計算することができます(もしかしたらご存知かもしれませんが).3の倍数判定法でも,各桁の和を3で割ったものの剰余が元の数の剰余と一致する,というのと似た感覚ですが,11の剰余の場合,奇数桁のものはそのまま剰余になりますが,偶数桁のものは剰余の逆数になります.これを使うと11についての剰余を楽にもとめられる(なんの役に立つのやら)わけです.余談でした.

    1. M.E.T.A. さん

      補足して頂き、ありがとうございます。
      「両端のみ$1$で間がすべて$0$の奇数桁の回文数」ということでしたか。ようやく合点がいきました。

      等比数列の和の公式から$$\dfrac{10^{2n}-1}{10^2-1}=\underbrace{101 \ldots 101}_{2n-1\text{桁}}$$を利用すると、$$10^{2n}+1=99 \times \underbrace{101 \ldots 101}_{2n-1\text{桁}}+2$$を得るので、奇数桁の「基本回文数」について$11$の剰余は常に$2$となることが理解できます。

      また、$10 \equiv -1 \pmod{11}$ なので、この形の回文数の末尾にゼロが増えるたびに剰余が$2$と$-2$($\equiv 9$)を行ったり来たりすることも理解できます($10 \equiv -1 \pmod{11}$ は$11$の倍数判定法の根拠でもありますね)。

      以上のことをまとめると、$1$と$0$で構成される $2k+1$ 桁の回文数について、下 $k+1$ 桁のみを観察すれば$11$の剰余が直ちに分かります。つまり、下 $k$ 桁までの各位の数に対して、奇数桁の位に$1$があれば$2$を加算し、偶数桁の位に$1$があれば$-2$を加算し、$k+1$ 桁に$1$があれば $k+1$ の偶奇によって$\pm 1$を加算すれば剰余が求められます。

      例えば、$N_1=10101110101$ という回文数では$$\small \begin{array}{cccccccccc}N_1 = \color{red}1 & 0 & \color{blue}1 & 0 & \color{green}1 & 1 & \color{green}1 & 0 & \color{blue}1 & 0 & \color{red}1 \\ & & & & & \overset{\large \text{↑}}{-1} & \overset{\large \text{↑}}{2} & & \overset{\large \text{↑}}{2} & & \overset{\large \text{↑}}{2} \end{array}$$ $$\begin{align} \to N_1 & \equiv -1+2+2+2 \\ & \equiv 5 \pmod{11}\end{align}$$と求められ、$N_2=11101110111$ という回文数では$$\small \begin{array}{cccccccccc}N_2 = \color{red}1 & \color{purple} 1 & \color{blue}1 & 0 & \color{green}1 & 1 & \color{green}1 & 0 & \color{blue}1 & \color{purple} 1 & \color{red}1 \\ & & & & & \overset{\large \text{↑}}{-1} & \overset{\large \text{↑}}{2} & & \overset{\large \text{↑}}{2} & \overset{\large \text{↑}}{-2} & \overset{\large \text{↑}}{2} \end{array}$$ $$\begin{align} \to N_2 & \equiv -1+2+2-2+2 \\ & \equiv 3 \pmod{11}\end{align}$$のように剰余が求められます。

      これで M.E.T.A. さんの主張を正しい形でフォローできた気がします。

  4. やっと,まともにお伝えでしたようで,感謝いたします.
    寝ぼけた頭で考えた結果,とんでもないご迷惑をおかけしました.
    でも,久しぶりに真夜中の眠れぬ夜の楽しみになりました.
    また,楽しい話題をどうかご提供ください.

    失礼しました.

  5. ピンバック: 回文数の研究
  6. ピンバック: 回文数の研究

pencil へ返信する コメントをキャンセル

メールアドレスが公開されることはありません。 が付いている欄は必須項目です