インテジャーズ

INTEGERS

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

連続ハーシャッド数

この記事では

定理 21個連続してハーシャッド数が現れることはない。

のCooperとKennedyによる証明を解説します。Cooperと言えば先日の最大素数の発見の代表研究者です。
integers.hatenablog.com

定義 自然数nの各桁の総和がnを割り切るとき、nのことをハーシャッド数という*1

例えば2016の各桁の和は9であり、2016=9\times 224なので2016はハーシャッド数であることが分かります。ハーシャッド数はインドの数学者Kaprekarによって定義され、サンスクリット語のharṣa(喜び)と da(与える)が語源だそうです。また、Niven数とも広くよばれています。Nivenは円周率の無理性証明で有名なあのNivenです。
integers.hatenablog.com

各桁の数の平方和を扱うハッピー数の場合はいくらでも長い連続ハッピー数の存在を証明することができました:
integers.hatenablog.com

それとは対照的に、ハーシャッド数の場合は21個以上連続することは決してないということが証明できるのです。

各桁の総和S(n)

自然数の各桁の総和をSmith数のときと同じくS(n)で表すことにします。
integers.hatenablog.com
このとき、次が成り立ちます:

補題1 \displaystyle S(n) = n - 9\sum_{j=1}^{\infty} \left[ \frac{n}{10^j} \right]

証明する代わりに三桁の自然数のときにこの公式が何を言っているかを見てみましょう:

a+b+c = 100a+10b+c - 9((10a+b)+a)

補題2 自然数m, nに対し、\displaystyle c(m+n)m+nの筆算において桁の繰り上がる回数とする。このとき、S(m+n)=S(m)+S(n)-9c(m+n)が成り立つ。

証明. 補題1より

\begin{equation}\begin{split}S(m)+S(n) &= m+n-9\sum_{j=1}^{\infty}\left( \left[ \frac{m}{10^j}\right] +\left[ \frac{n}{10^j}\right] \right) \\ &=S(m+n)+9\sum_{j=1}^{\infty}\left( \left[ \frac{m+n}{10^j}\right] - \left[ \frac{m}{10^j}\right] - \left[ \frac{n}{10^j}\right]\right)\end{split}\end{equation}

が成り立つ。括弧の中身は01しか取り得ないが、m+nの筆算において、nmj桁目までを足してj+1桁目の繰り上がりが起きるときに

\displaystyle \left[ \frac{m+n}{10^j}\right]- \left[ \frac{m}{10^j}\right] - \left[ \frac{n}{10^j}\right] = 1

をとる。 Q.E.D.

デケイドと世紀

nを非負整数とする。\{10n, 10n+1, \dots, 10n+9\}なる形の集合のことをデケイドといい、\{100n, 100n+1, \dots, 100n+99\}の形をした集合のことを世紀という。デケイドが与えられたとき、そのデケイドの元であってパリティが等しいものは、各桁の数の総和を取ったものもパリティが等しいことに注意する。そこで、便宜的に、所属する奇数の各桁の数の総和が偶数になるようなデケイドをEで、奇数になるようなデケイドをOで表すことにする。このとき、定義からEに属する奇数はハーシャッド数にはなり得ない(偶数が奇数を割り切ることはない)。また、世紀は小さい順に数を並べると

O, E, O, E, O, E, O, E, O, E

または

E, O, E, O, E, O, E, O, E, O

のようになっているため、12個以上連続したハーシャッド数は世紀をまたぐ必要がある。

f:id:integers:20160129145647p:plain

図のように世紀をまたいただとしても、すぐにEが邪魔をすることがわかる。というわけで、22個以上連続するハーシャッド数が存在しないことは既にわかった。また、次の命題も証明できたことになる:

命題 21個連続するハーシャッド数が存在すれば、その中で一番小さい数は十進表記で ****999\cdots 90 という形をしている。

証明

21個連続するハーシャッド数が存在したと仮定して矛盾を導く。すなわち、a, a+1, \dots, a+20が全てハーシャッド数であったとする。
このとき、命題によってt\geq 2が存在して、a\equiv \underbrace{9\cdots 9}_{t-1}0 \pmod{10^t}が成り立つ。また、a(t+1)桁目の数は9ではないと仮定してよい。ハーシャッド数であるという定義および補題2によって次の合同式が成立する:

\begin{align}x &\equiv 0 \pmod{S(a)} \ \text{-①} \\
x &\equiv -1 \pmod{S(a)+1} \ \text{-②} \\ 
x &\equiv -2 \pmod{S(a)+2} \ \text{-③} \\
x &\equiv -3 \pmod{S(a)+3} \ \text{-④} \\
x &\equiv -4 \pmod{S(a)+4} \ \text{-⑤} \\
x &\equiv -5 \pmod{S(a)+5} \ \text{-⑥} \\
x &\equiv -6 \pmod{S(a)+6} \ \text{-⑦} \\
x &\equiv -7 \pmod{S(a)+7} \ \text{-⑧} \\
x &\equiv -8 \pmod{S(a)+8} \ \text{-⑨} \\
x &\equiv -9 \pmod{S(a)+9} \ \text{-⑩} \\
x &\equiv -10 \pmod{S(a)+10-9t} \ \text{-⑪} \\
x &\equiv -11 \pmod{S(a)+11-9t} \ \text{-⑫} \\
x &\equiv -12 \pmod{S(a)+12-9t} \ \text{-⑬} \\
x &\equiv -13 \pmod{S(a)+13-9t} \ \text{-⑭} \\
x &\equiv -14 \pmod{S(a)+14-9t} \ \text{-⑮} \\
x &\equiv -15 \pmod{S(a)+15-9t} \ \text{-⑯} \\
x &\equiv -16 \pmod{S(a)+16-9t} \ \text{-⑰} \\
x &\equiv -17 \pmod{S(a)+17-9t} \ \text{-⑱} \\
x &\equiv -18 \pmod{S(a)+18-9t} \ \text{-⑲} \\
x &\equiv -19 \pmod{S(a)+19-9t} \ \text{-⑳} \\
x &\equiv -20 \pmod{S(a)+11-9t} \ \text{-㉑} \end{align}

kが二桁の数の場合は補題2によって

S(a+k)=S(a)+S(k)-c(a+k)=S(a)+S(k)-9(t-1)

が成り立つので、例えば

S(a+19)=S(a)+10-9(t-1)=S(x)+19-9t

となる。⑫と㉑によって、-11\equiv -20 \pmod{S(a)+11-9t}が成り立つ。これはS(a)+11-9t9を割り切ること、すなわち、

S(a)+11-9t=1, 3 \ \text{or} \ 9

を意味する。しかしながら、a\equiv \underbrace{9\cdots 9}_{t-1}0 \pmod{10^t}からS(z) \geq 9t-9なので、9t-S(a) = 2 \ \text{or} \ 8であることがわかる。

9t-S(x)=8のとき: ⑪、⑫、⑭、⑯、⑳より、

\begin{align}a &\equiv 0 \pmod{2} \\
a &\equiv 1 \pmod{3} \\
a &\equiv 2 \pmod{5} \\
a &\equiv 6 \pmod{7} \\
a &\equiv 3 \pmod{11} \end{align}

が成り立つ。よって、中国剰余定理により

x \equiv 2302 \pmod{2310}

を得る。しかし、aは仮定より5の倍数なので、この合同式は成り立ちえない。


9t-S(x)=2のとき:

\begin{align}x &\equiv 0 \pmod{9t-2} \ \text{-①} \\
x &\equiv -1 \pmod{9t-1}\text{-②} \\
x &\equiv -2 \pmod{9t} \ \text{-③} \\
x &\equiv -3 \pmod{9t+1} \ \text{-④} \\
x &\equiv -4 \pmod{9t+2} \ \text{-⑤} \\
x &\equiv -5 \pmod{9t+3} \ \text{-⑥} \\
x &\equiv -6 \pmod{9t+4} \ \text{-⑦} \\
x &\equiv -7 \pmod{9t+5} \ \text{-⑧} \\
x &\equiv -8 \pmod{9t+6} \ \text{-⑨} \\
x &\equiv -9 \pmod{9t+7} \ \text{-⑩} \\
x &\equiv 6 \pmod{8} \ \text{-⑪} \\
x &\equiv 7 \pmod{9} \ \text{-⑫} \\
x &\equiv 8 \pmod{10} \ \text{-⑬} \\
x &\equiv 9 \pmod{11} \ \text{-⑭} \\
x &\equiv 10 \pmod{12} \ \text{-⑮} \\
x &\equiv 11 \pmod{13} \ \text{-⑯} \\
x &\equiv 12 \pmod{14} \ \text{-⑰} \\
x &\equiv 13 \pmod{15} \ \text{-⑱} \\
x &\equiv 14 \pmod{16} \ \text{-⑲} \\
x &\equiv 15 \pmod{17} \ \text{-⑳} \\
x &\equiv 7 \pmod{9} \ \text{-㉑} \end{align}

を得る。ここで、

x\equiv r\pmod{m}, x\equiv s\pmod{n} \Longrightarrow \mathrm{gcd}(m, n) \mid r-s

を用いることにより、

④と⑬より\mathrm{gcd}(10, 9t+1)=1
⑥と⑬より\mathrm{gcd}(10, 9t+3)=1
⑦と⑬より\mathrm{gcd}(10, 9t+4)=1
⑩と⑬より\mathrm{gcd}(10, 9t+7)=1

が得られる。aは偶数なので、②よりtは偶数である。しかし、

t \equiv 2 \pmod{10} \Longrightarrow \mathrm{gcd}(10, 9t+7) \neq 1
t \equiv 4 \pmod{10} \Longrightarrow \mathrm{gcd}(10, 9t+4) \neq 1
t \equiv 6 \pmod{10} \Longrightarrow \mathrm{gcd}(10, 9t+1) \neq 1
t \equiv 8 \pmod{10} \Longrightarrow \mathrm{gcd}(10, 9t+3) \neq 1

となるので、残る可能性はt \equiv 0 \pmod{10}のみである。

a\equiv \underbrace{9\cdots 9}_{t-1}0 \pmod{10^t}(仮定)
a \equiv -7 \pmod{9t+5}(⑧より)

によって、\mathrm{gcd}(10^t, 9t+5)\underbrace{9\cdots 9}_{t-1}7の約数である。これは\mathrm{gcd}(10^t, 9t+5)5では割り切れないことを導く。つまり、t \equiv 0 \pmod{10}もあり得ない。全ての可能性が消去されたので、背理法により証明が完了する。 Q.E.D.

連続する20個のハーシャッド数

ちなみにCooperとKennedyは20個連続するようなハーシャッド数の組は無数に存在することを次のように構成的に証明しています:

\begin{equation}\begin{split}a=&4090669070187777592348077471447408839621564801\\
&2007115516094806249015486761744582584646124234\\
&1540855543641742325745294115007591954820126570\\
&08707100552326606429204305490237043943\underbrace{0\cdots 0}_{1120}\end{split}\end{equation}

\begin{equation}\begin{split}b=&2846362190166818294716429619770154544233311863\\
&4187301827478422658543387589306681088151446703\\
&2759507916140833155837906335537198825206802774\\
&8430283149755020972927459559360592362156\underbrace{9\cdots 9}_{1119}0\end{split}\end{equation}

c=2464645030, d=2464634960

とする。このとき、

c \mid a
c+1 \mid a
\dots
c+9 \mid a
d \mid a
d+1 \mid a
\dots
d+9 \mid a

c \mid b
c+1 \mid b+1
\dots
c+9 \mid b+9
d \mid b+10
d+1 \mid b+11
\dots
d+9 \mid b+19

d=c+1-9\times 1119

S(a)=720, S(b)=10870

が確認できる。任意の非負整数mに対して、

x := \underbrace{a \cdots a}_{3423103}\underbrace{0 \cdots 0}_{m}b

とおけば(ただし、abは掛けるのではなくconcatenateしている)、S(x)=cであり、構成からx, x+1, \dots, x+19は全てハーシャッド数であることがわかる。

*1:何進法でも考えられますが、この記事では十進法に限定します。