インテジャーズ

INTEGERS

数、特に整数に関する記事。

44488:ハッピー数

44488, \ 44489, \ 44490, \ 44491, \ 44492はハッピー数です。44488n, n+1, n+2, n+3, n+4が全てハッピー数となるような整数nのうち、最小のものです。

Smith数に関する記事では自然数の各桁の数を足すという操作を考えました。
integers.hatenablog.com

ここでは、自然数の各桁の数の2乗を足し合わせる操作を考えます。この操作を繰り返して1に到達するとき、その自然数のことをハッピー数と言います。

例えば、7\to 49\to 97\to 130\to 10\to 1 より7はハッピー数です(7は素数なので更にハッピー素数と呼ばれます)。

一方、4→16→37→58→89→145→42→20→4 となって、この後無限ループに陥るため、4はハッピー数ではありません。このような数をアンハッピー数と言います。

1000以下のハッピー数は

\begin{align}&1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, 103, 109, \\
&129, 130, 133, 139, 167, 176, 188, 190, 192, 193, 203, 208, 219, 226, 230, 236, 239, \\
&262, 263, 280, 291, 293, 301, 302, 310, 313, 319, 320, 326, 329, 331, 338, 356, 362,\\
&365, 367, 368, 376, 379, 383, 386, 391, 392, 397, 404, 409, 440, 446, 464, 469, 478, \\
&487, 490, 496, 536, 556, 563, 565, 566, 608, 617, 622, 623, 632, 635, 637, 638, 644, \\
&649, 653, 655, 656, 665, 671, 673, 680, 683, 694, 700, 709, 716, 736, 739, 748, 761, \\
&763, 784, 790, 793, 802, 806, 818, 820, 833, 836, 847, 860, 863, 874, 881, 888, 899, \\
&901, 904, 907, 910, 912, 913, 921, 923, 931, 932, 937, 940, 946, 964, 970, 973, 989, \\
&998, 1000\end{align}

であり、このうち、ハッピー素数は

\begin{align}&7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193, 239, 263, 293, 313, 331, 367, 379, \\
&383, 397, 409, 487, 563, 617, 653, 673, 683, 709, 739, 761, 863, 881, 907, 937\end{align}

と35個あります。

ハッピー数の名前の由来はよくわかっていないようです。ハッピー数が自然数全体でどれくらいの割合を占めるかはまだ決定されていませんが、数値実験的には1/7程度がハッピー数のようです。つまり、比較的ハッピー数の方が出現頻度が低く、出会えると少しハッピーな気分になるかもしれません(?)。

実は、各桁の2乗和を計算する操作を繰り返したとき、どんな自然数であっても最終的には1になるか4のループに入ります:

命題 ハッピー作用素H \colon \mathbb{N} \to \mathbb{N}
\displaystyle H\left( \sum_{i=0}^ka_i\cdot 10^{i} \right) := \sum_{i=0}^ka_i^2
によって定める(kは非負整数で、0 \leq i \leq kに対して、a_i0以上9以下の自然数)。
また、D:=\{1, 4, 16, 20, 37, 42, 58, 89, 145\}とする。このとき、任意の自然数nに対して、ある非負整数k_0が存在して、任意の整数k\geq k_0に対してH^k(n) \in Dとなる。
ただし、\displaystyle H^0:=\mathrm{id}_{\mathbb{N}}, \ H^k:=\underbrace{H\circ \cdots \circ H}_{k} (kは自然数)。

証明. nd\geq 4桁の整数とする。このとき、

H(n)\leq 81d < 10^{d-1}\leq n

であるから、nHを作用させると減少することがわかる。つまり、どんな整数であっても、ハッピー作用素を作用させ続けることにより3桁以下の自然数にすることが出来る。従って、問題は3桁以下の自然数を全て調べることに帰着される。nを3桁の自然数とする。このとき、

H(n)\leq T(999)=243

なので、Hを一回作用させることにより、243以下にすることが出来る。100\leq n\leq 243のとき、

H(n) \leq H(199)\leq 163.

100\leq n \leq 163のとき、

H(n) \leq H(159)=107.

100\leq n \leq 107のとき、

H(n) \leq H(107)=50.

こうして、2桁以下の場合に帰着された。2桁以下の場合に、必ず14のループになることを確認する。

既に確認済の数に辿り着いた場合は即座にその次の数の確認に移る(Dの元については確認済であることに注意。また、数の入れ替えや0が含まれる数についてはHを作用させても結果が変わらないので、それらも確認済とみなす(例: H(81)=H(18), \ H(20)=H(2))):

\begin{align}&1, \\
&2→4, \\
&3→9→81→65→61, \\
&4, \\
&5→25→29→85, \\
&6→36→45→41→17→50, \\
&7→49→97→130→10, \\
&8→64→52, \\
&9, \\
&10, \\
&11→2, \\
&12→5, \\
&13→10, \\
&14, \\
&15→26→40, \\
&16, \\
&17, \\
&18, \\
&19→82→68→100, \\
&20, \\
&21→5, \\
&22→8, \\
&23→13, \\
&24, \\
&25, \\
&26, \\
&27→53→34→25, \\
&28, \\
&29, \\
&30, \\
&31, \\
&32→13, \\
&33→18, \\
&34, \\
&35, \\
&36, \\
&37, \\
&38→73, \\
&39→90, \\
&40, \\
&41, \\
&42, \\
&43, \\
&44→32, \\
&45, \\
&46, \\
&47→65, \\
&48→80, \\
&49, \\
&50, \\
&51, \\
&52, \\
&53, \\
&54, \\
&55→50, \\
&56, \\
&57→74, \\
&58, \\
&59→108, \\
&60, \\
&61, \\
&62, \\
&63, \\
&64, \\
&65, \\
&66→72, \\
&67→85, \\
&68, \\
&69→117→51, \\
&70, \\
&71, \\
&72, \\
&73, \\
&74, \\
&75, \\
&76, \\
&77→98, \\
&78→113→11, \\
&79, \\
&80, \\
&81, \\
&82, \\
&83, \\
&84, \\
&85, \\
&86, \\
&87, \\
&88→128→69, \\
&89, \\
&90,\\
&91, \\
&92, \\
&93, \\
&94, \\
&95, \\
&96, \\
&97, \\
&98, \\
&99→162→41.\end{align}

こうして、2桁以下の自然数はHを繰り返し作用させた後、14のループに到達することが証明された。 Q.E.D.

あるk_0が存在してH^{k_0}(n) \in Dという条件だけならD=\{1, 4\}でもよかったわけですが、k \geq k_0なる全てのkに対してH^k(n) \in Dという性質を後で用います。これはHDに作用していることから分かります。

ハッピー数とアンハッピー数がそれぞれ無数に存在することは次のように簡単にわかります: 任意の非負整数nに対して10^nはハッピー数(H(10^n)=1)であり、2\cdot 10^nはアンハッピー数である(H(2\cdot 10^n)=4)。

一方、冒頭に述べた例のような連続するハッピー数は珍しい存在に思われます(冒頭に述べたような列を長さ5の連続ハッピー数列と呼ぶことにしましょう)。これに対し、El-SedyとSiksekは任意の長さの連続ハッピー数列が存在することを2000年に示しました:

定理 (El-Sedy, Siksek) 任意の自然数mに対し、ある自然数l_0が存在して、l_0+1, l_0+2, \dots, l_0+mが全てハッピー数となる。

冒頭の例は5個連続ハッピー数でしたが、例えば、1億個連続してハッピー数が並んでる場所を発見できます。

以下、この定理を

E. El-Sedy and S. Siksek, On happy numbers, Rocky Mountain J. Math., 30(2000), 565-570.

に基づいて証明します。彼らの証明は構成的で、次の補題が最も重要です:

補題 任意の u \in Dに対して、l+uがハッピー数となるような自然数lが存在する。

証明は後回しにして、とりあえずこの補題を認めることにします。

定理の証明. 1\leq i \leq mなる全てのiに対してH^k(i) \in Dとなるような自然数kをとる(上で証明した命題によりこのようなkが存在することがわかる)。

また、1\leq i \leq m, 0 \leq j\leq kなる任意のi, jに対して10^d > H^j(i)となるような自然数dをとる(\# \{H^j(i) \mid 1\leq i \leq m, 0 \leq j \leq k\} < \inftyより、このようなdがとれることがわかる)。

さて、l_0, \dots, l_kl_kl_{k-1}→…→l_0という順番で次のように定める:

  • まず、補題のlをとって、 l_k:=lとする。
  • 次に、0\leq j\leq k-1なるjに対してl_{j+1}が定まっているときに、l_jl_j:=10^dl_{j+1}^{\prime}と定める。ただし、l_{j+1}^{\prime}H(l_{j+1}^{\prime})=l_{j+1}を満たすようなものとする(Hが全射であることはH(\underbrace{1\cdots 1}_{n})=nよりわかる。l_{j+1}^{\prime}の取り方は一意とは限らないが、一つ勝手に選ぶものとする)。

このように \{l_j \}を定めるとき、H(l_j)=l_{j+1} (0\leq j \leq k-1)が成り立つ。また、 n < 10^dを満たす自然数nに対してH(l_j+n)= l_{j+1}+H(n)が成り立つこともわかる(0\leq j \leq k-1)。従って、dの取り方より、

H^k(l_0+i)=H^{k-1}(l_1+H(i))=H^{k-2}(l_2+H^2(i))=\cdots = l_k+H^k(i)

が全ての 1\leq i \leq mに対して成り立つ。今、H^k(i) \in Dであるから、補題によってl_k+H^k(i)=l+H^k(i)はハッピー数であることが分かる。故に、全ての1\leq i \leq mに対してl_0+iもハッピー数となる。 Q.E.D.

最後に補題を示そう:

補題の証明. \displaystyle l:= \underbrace{99\cdots 9}_{233192}20958とする。u\in Dに対して

H(l+u)=233192\times 3^2+2^2+H(958+u)=18888556+H(958+u)

である。

18888556+H(959)=18888723\to 319\to 91\to 82\to 68\to 100\to 1

18888556+H(962)=18888677\to 391\to 91\to 82\to 68\to 100\to 1

18888556+H(974)=18888702\to 310\to 10\to 1

18888556+H(978)=18888750\to 331\to 19\to 82\to 68\to 100\to 1

18888556+H(995)=18888743\to 331\to 19\to 82\to 68\to 100\to 1

18888556+H(1000)=18888557\to 356\to 70\to 49\to 97\to 130\to 10\to 1

18888556+H(1016)=18888594\to 379\to 139\to 91\to 82\to 68\to 100\to 1

18888556+H(1047)=18888622\to 301\to 10\to 1

18888556+H(1103)=18888567\to 367\to 94\to 97\to 130\to 10\to 1

以上により、任意のu \in Dに対してl+uがハッピー数であることが示された。   Q.E.D.