インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

4937775:スミス数

4937775はSmith数(スミス数)です。Smith数とは何かをまず説明しましょう。

自然数mに対して、S(m)mの各桁の数の総和と定義します。例えば、

S(123456789) = 1+2+3+4+5+6+7+8+9 = 45

です。次に2以上の整数mm=p_1\cdots p_rと素因数分解で表します。ただし、今回はp_1, \dots, p_rの中には等しいものがあってもよいものとします。このとき、S_p(m)

S_p(m) := S(p_1)+\cdots +S(p_r)

により定義します。例えば、123456789 = 3\cdot 3\cdot 3607\cdot 3803なので、

S_p(123456789)=S(3)+S(3)+S(3607)+S(3803)=3+3+16+14=36

が成り立ちます。S(m)S_p(m)を比較することを考えてみましょう。上の例では

S_p(123456789) < S(123456789)

となっていることがわかります。Smith数は次のように定義されます。

定義 合成数mS_p(m)=S(m)を満たすとき、mSmith数という。

つまり、123456789はSmith数ではありません。定義でmが合成数となっているのは、素数は自明にS_p(m)=S(m)を満たしてしまうためです。それでは、タイトルの数である4937775がSmith数であることを確認しましょう。

S(4937775) = 4+9+3+7+7+7+5 = 42.

一方、{ 4937775 = 3\cdot 5\cdot 5\cdot 65837}なので、


\begin{equation}
\begin{split}
S_p(4937775) &= S(3)+S(5)+S(5)+S(65837)\\
&= 3+5+5+(6+5+8+3+7) = 42
\end{split}
\end{equation}

となって、S_p(4937775)=S(4937775)が成り立つことがわかります。すなわち、4937775はSmith数であることが確認できました。

Smith数はWilanskyによって、1982年に定義されました。名前の由来は彼の義理の兄弟であるSmithの電話番号が4937775であったことに基づいています(当時4937775が知られている最大のSmith数でした)。Smith数を小さい方からいくつか並べると次のようになります:

4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086, 1111, 1165, …

Wilanskyは「Smith数は無数にあるだろうか?」と問いましたが、これは1987年にMcDanielによって解決されました:

定理 (McDaniel) Smith数は無数に存在する。

以下、この定理の証明を彼の論文

W. McDaniel, "The existence of infinitely many k-Smith numbers", Fibonacci Quarterly 25(1):(1987), 76-80.

に基づいて紹介します。

証明は具体的なSmith数の作り方を提示することによって行います。その作り方を解説する前に、S_p(m)のある程度精密な上からの評価(McDanielの不等式)とS(m)に関する1つの補題が必要となります。

記号: d(m)mの桁数を表す。

定理 (McDanielの不等式) 整数mm=p_1\cdots p_rと素因数分解されているとする
(p_1, \ldots, p_rの中には等しいものがあってもよい)。このとき、
S_p(m)<9d(m)-0.54r
が成り立つ。

証明. 1\leq i \leq rに対して、 b_i:=d(p_i)-1とし、更に、b:=b_1+\cdots +b_rとする。p_iの全ての桁が9であることはあり得ないので(さもないとp_i9の倍数となってp_iが素数であることに反する)、S(p_i)\leq 9d(p_i)-1=9b_i+8が成り立つ。1\leq i \leq rに対してS(p_i)=9b_i+c_iによってc_i \in \mathbb{Z}_{\leq 8}を定義する。ここで、次のような分割を考える:

\{1, \ldots, r\}=I_1 \sqcup \cdots \sqcup I_8 \sqcup I_{<0},

 I_j := \{ i \mid 1\leq i \leq r, c_i=j\} (1\leq j \leq 8), I_{<0} := \{ i \mid 1\leq i \leq r, c_i <0 \}.

c_i=0にはなり得ないことに注意する(さもないと、再びp_i9の倍数となってp_iが素数であることに反する)。n_j := \#I_j (1\leq j \leq 8), n_0 := \#I_{<0}とすると、

\displaystyle S_p(m)=\sum_{i=1}^rS(p_i)=\sum_{i=1}^r(9b_i+c_i)=9b+\sum_{j=1}^8jn_j+\sum_{i \in I_{<0}}c_i

を得る。i \in I_{<0}に対してc_i\leq -1であるから、

\displaystyle
\begin{equation}
S_p(m) \leq 9b+\sum_{j=1}^8jn_j-n_0
\end{equation}
-(1)

となる。次に、各p_iを下から評価する。最悪の評価として、p_ib_i+1桁の数なのでp_i>10^{b_i}が成り立つ。i \in I_{<0}なるiについてはこの評価で我慢する。i \in I_j (1 \leq j \leq 8)かつp_i2, 3, 5, 7のいずれでもないならば、

\displaystyle p_i \geq (c_i+1)10^{b_i-1} \geq \left( c_i+\frac{9}{10}\right) 10^{b_i}

がより良い評価になっている(もしp_i<(c_i+1)10^{b_i}-1ならば S(p_i) < c_i+9b_iとなって矛盾する。二つ目の不等式でb_i\geq 1なる条件を用いている)。p_i=2, 3, 5, 7のときはb_i=0であるから、p_i = c_i10^{b_i}と思える。以上によって、次の評価を得る:

m = p_1\cdots p_r \geq 1.9^{n_1}\cdot 2^{n_2} \cdot 3^{n_3}\cdot 4.9^{n_4}\cdot 5^{n_5}\cdot 6.9^{n_6}\cdot 7^{n_7}\cdot 8.9^{n_9}\cdot 10^b.

m=a\cdot 10^{d(m)-1}1\leq a < 10を満たす有理数 aを用いて mを書き直し、\log_{10}を取ることによって、


\begin{equation}\begin{split}\log_{10}a+d(m)-1 \geq &\ n_1\log_{10}1.9+n_2\log_{10}2+n_3\log_{10}3+n_4\log_{10}4.9\\
&+n_5\log_{10}5+n_6\log_{10}6.9+n_7\log_{10}7+n_8\log_{10}8.9+b
\end{split}
\end{equation}

すなわち、

\begin{equation}\begin{split}9d(m) \geq &\ 9b+n_1(9\log_{10}1.9)+n_2(9\log_{10}2)+n_3(9\log_{10}3)+n_4(9\log_{10}4.9)\\
&+n_5(9\log_{10}5)+n_6(9\log_{10}6.9)+n_7(9\log_{10}7)+n_8(9\log_{10}8.9)\\
&+9(1-\log_{10}a)\end{split}\end{equation}

を得る。

\begin{align}&9\log_{10}(1.9)=2.50872409\cdots\\
&9\log_{10}2=2.709269961\cdots\\
&9\log_{10}3=4.294091292\cdots\\
&9\log_{10}(4.9)=6.21176472\cdots\\
&9\log_{10}5=6.290730039\cdots\\
&9\log_{10}(6.9)=7.549641817\cdots\\
&9\log_{10}7=7.60588236\cdots\\
&9\log_{10}(8.9)=8.54451006\cdots\end{align}

より、上記不等式のn_jの係数は1\leq j \leq 8なる全てのjに対してj+0.54より大きいことが確認できる。また、 1-\log_{10}a>0なので、

\displaystyle 9b+\sum_{j=1}^8n_j(j+0.54)<9d(m).

-n_0<-0.54n_0, n_0+n_1+\cdots +n_8=rに注意して、

\displaystyle 9b+\sum_{j=1}^8jn_j-n_0<9d(m)-0.54(n_0+n_1+\cdots +n_8)=9d(m)-0.54r

を得る。(1)と合わせることにより、所望の不等式が得られた。 Q.E.D.

補題 nを自然数とし、t10^n-1以下の自然数とする。このとき、
S(t(10^n-1))=S(10^n-1)=9n
が成り立つ。

証明. \displaystyle t=\sum_{i=0}^{k}a_{i}10^i (a_k \neq 0, 0\leq k < n)tを10進展開表示する。v:=\mathrm{ord}_{10}tとして、t=t^{\prime}\cdot 10^vとする。このとき、t^{\prime}の一の位は零ではなく、S(t(10^n-1))=S(t^{\prime}(10^n-1))である。よって、a_0\neq 0と仮定してよい。

\displaystyle \begin{equation}\begin{split} -\sum_{i=0}^ka_i10^i&=(10-a_0)+\sum_{i=1}^k(9-a_i)10^i-\left(10+9\sum_{i=1}^k10^i\right)\\ &=(10-a_0)+\sum_{i=1}^k(9-a_i)10^i-10^{k+1}.\end{split}\end{equation}

u:=n-k-1とする。このとき、

\displaystyle \begin{equation}\begin{split}-10^{k+1}+a_0\cdot 10^n &= \sum_{i=1}^u(-10^{k+i}+10^{k+i+1})-10^{k+u+1}+a_0\cdot 10^{k+u+1}\\ &=\sum_{i=1}^u9\cdot 10^{k+i}+(a_0-1)10^{n}.\end{split}\end{equation}

よって、

\displaystyle \begin{equation}\begin{split} t(10^n-1) = &\sum_{i=0}^ka_i\cdot 10^{n+i}-\sum_{i=0}^ka_i\cdot 10^i\\ = &\sum_{i=1}^ka_i\cdot 10^{n+i}+(a_0-1)10^{n}+\sum_{i=1}^u9\cdot 10^{k+i}+\sum_{i=1}^k(9-a_i)10^i\\&+(10-a_0)\end{split}\end{equation}

t(10^n-1)の10進展開表示が得られた。故に、

\displaystyle \begin{equation}\begin{split} S(t(10^n-1))&=\sum_{i=1}^ka_i+(a_0-1)+9u+\sum_{i=1}^k(9-a_i)+(10-a_0)\\ &=9u+9k+9=9n.\end{split}\end{equation}
Q.E.D.

以上で準備は整ったので、Smith数を構成するMcDanielのアルゴリズムを紹介しましょう。T:=\{2, 3, 4, 5, 8, 7, 15 \}とする。

McDaniel's algorithm for constructing Smith numbers

  1. 自然数nに対し、m=10^n-1とする。
  2. mを素因数分解する。
  3. S_p(m)を計算し、h:=9n-S_p(m)とする。
  4. x=h-7b \ (2\leq x \leq 8, b\geq 0)を満たす整数x, bを見つける。
  5. S_p(t)=xなるt \in Tをとる。
  6. \mathcal{M}(n) := tm\cdot 10^bとおく。

このとき、\mathcal{M}(n)はSmith数である。

上記アルゴリズムの正当性の証明. 手順1~手順3までは全く問題ない。3^2\mid mなので、n \geq 2ならばmは3つ以上の素因数をもつ。よって、McDanielの不等式より

S_p(m) \leq 9d(m)-0.54\times 3 \leq 9n-2

となって

h=9n-S_p(m) \geq 2

が成り立つ。この最後の不等式はn=1のときも成立している。今、

\{ S_p(t) \mid t \in T \} = \{2, 3, 4, 5, 6, 7, 8 \}

であり、これは\mathbb{Z}/7\mathbb{Z}の完全代表系をなす。以上により、手順4および手順5におけるx, b, tの存在が示された。後は、手順6の\mathcal{M}(n)がSmith数であることを示せば終わりである。n\geq 2ならばt\leq mであり、n=1の場合もt=3 < 10^1-1であるから、補題よりS(\mathcal{M}(n))=S(tm)=9nがわかる。一方、S_pの定義と構成から

S_p(\mathcal{M}(n))=S_p(t)+S_p(m)+S_p(10^b)=(h-7b)+(9n-h)+(2b+5b)=9n

と計算される。よって、S_p(\mathcal{M}(n))=S(\mathcal{M}(n))が示された。 Q.E.D.

さて、写像\mathcal{M}\colon \mathbb{N} \to \mathbb{N}は単射である(像の元に対して、まずbが復元され、その後n, tも復元される)。よって、特に\# \mathcal{M}(\mathbb{N}) = \inftyであり、Smith数は無数に存在することが示された。

最後にSmith数の例を作ってみよう。
integers.hatenablog.com
で紹介したレピュニット素数R_{19}を用いて\mathcal{M}(19)を計算する。

1.  m=10^{19}-1.
2. 素因数分解は 3^2\cdot R_{19}.
3. S_p(m)=3+3+19=25, h=9\times 19 -25=146.
4.  6=146-7\cdot 20, つまり、x=6, b=20.
5.  S_p(8)=6, つまり、t=8.
6. \mathcal{M}(19)=8m \cdot 10^{20} = 79999999999999999992\times 10^{20}.

\begin{align}S(79999999999999999992\times 10^{20})&=7+9\times 18 +2 = 171,\\
79999999999999999992\times 10^{20}&=2^{23}\cdot 3^2\cdot 5^{20}\cdot R_{19},\\
S_p(79999999999999999992\times 10^{20})&=46+6+100+19=171.\end{align}

こうして、我々はSmith氏の電話番号4937775よりはるかに大きいSmith数を手に入れることが出来た。