デュードニー数：512 - tsujimotterのノートブック

今日はこんな問題を考えてみましょう：

問題（ルートの展開）

ある3乗数を考えます。その数の各桁の数を足し算したら、もとの数の3乗根に一致しました。
もとの数は何でしょうか？

一例として、 $512$ を考えましょう。 $512 = 8^3$ なので、これは3乗数です。

$512$ の各桁を足し算すると

$5 + 1 + 2 = 8$

となり、 $512$ の3乗根である $8$ に一致しました。

というわけで、 $8$ はこの問題の答えの一つです。

$1$ もこの問題の答えの一つです。 $1 = 1^3$ なので、これは3乗数ですが、その各桁を足し算すると、もちろん $1$ に一致します。

さて、ほかにも例はあるでしょうか？

（自分で考えたい人は、ぜひどうぞ。答えは記事の後半で紹介します。）

今回紹介したいのは、デュードニー数です。

デュードニー数とは、3乗数であって（10進法の）各桁の和を3乗すると元に戻るという性質持った数のことです。

上で紹介した $1$ や $512$ はもちろんデュードニー数ですね。

ちなみに、この記事は5/12に公開していますが、日付の数を並べた512はデュードニー数というわけですね。

なお、デュードニー数の名前ですが、ヘンリー・デュードニーというイギリスの有名なパズル作家に由来しています。デュードニーが、冒頭のような問題を書籍「536 Puzzles & Curious Problems」の「120. Root Extraction」という項目で紹介したのがきっかけで、この数が世に広まりました。

デュードニーはこんな感じのおじさんです

元の問題文は、以下のURLから見ることができます：
536 puzzles & curious problems : Dudeney, Henry Ernest, 1857-1930 : Free Download, Borrow, and Streaming : Internet Archive

デュードニーといえば、有名なもので言うと「正三角形を4つに分割して正方形に戻す（以下の図参照）」という裁ち合わせパズルを発見したことでも知られていますね。

デュードニー数は既に多くの人に調べられていて、たとえばオンライン整数列大辞典（OEIS）でも次のような数列のリストがあります：
oeis.org

一般化b進デュードニー数と前回の記事の関係

上の話は、 $3$ 乗数を考えて、その10進法での各桁を足していましたが、ここを $k$ 乗数と $b$ 進法に一般化することもできます。

一般化 $b$ 進デュードニー数とは、 $k$ 乗数であって（ $b$ 進法の）各桁の和を $k$ 乗すると元に戻るという性質持った数のことです。

数式で書くと、 $k$ 乗数 $n = m^k$ が $b$ 進法で $n = (a_{d-1} a_{d-2} \cdots a_0)_{b}$ で表せるとします。このとき、各桁の総和が

$a_{d-1} + a_{d-2} + \cdots + a_0 = m$

と表せるとき、 $n$ を一般化 $b$ 進デュードニー数といいます。
（このとき、得られた $m$ を $k$ 乗すると $n$ に一致するので、元の文章と同じことを言っていますね。）

ちなみに、 $n$ の $b$ 進法での各桁の総和を

$s_b(n) := a_{d-1} + a_{d-2} + \cdots + a_0$

で定義すると、デュードニー数の条件は

$\sqrt[k]{n} = s_b(n)$

で簡潔に表せます。

たとえば、簡単な例でいうと、 $81 = 9^2$ が $k = 2$ における一般化10進デュードニー数です。

実際、 $81$ の各桁の総和をとると

$8 + 1 = 9$

となり、 $9$ に一致しますね。

ところでここまでの話を聞いて、前回の「平方根計算の裏技（？）」の記事との関連性に気づいた方もいるかもしれません。

tsujimotter.hatenablog.com

以下のように整理してみましょう。

一般化10進デュードニー数：
$k$ 乗数 $n = m^k$ について、 $n$ の（10進法での）各桁の総和が $m$ に一致する

平方根計算の裏技（？）で考えていたもの：
$k$ 乗数 $n = m^k$ について、 $n$ の（10進法での）各桁の総和が $m + k$ に一致する

比較すると、最後が $m$ そのものに一致するか、 $m + k$ に一致するかの違いで、ほとんど同じですね。

つまり、前回考えていたのは「一般化10進デュードニー数」の問題の亜種だったというわけです。

前回の問題は一見テキトーに思いついた一問題という感じでしたが、デュードニー数といういかにも由緒正しそうな（？）問題の亜種だったというのは、面白いことですね。

一般化デュードニー数の有限性

前回と同じ形の問題となっているので、ほとんど同じように定式化することができます。

$k$ 乗数 $n = m^k$ が $b$ 進法で $d$ 桁の数であり $n = (a_{d-1} a_{d-2} \cdots a_0)_{b}$ で表せるとします。すると、総和記号を用いて

$\displaystyle \sum_{i=0}^{d-1} a_i b^i = m^k \;\;\;\;\;\;\;\;\;\;\;\; (1)$

と表せます。

一般化デュードニー数のもう一つの条件「各桁の総和が $m$ に一致する」より

$\displaystyle \sum_{i=0}^{d-1} a_i = m \;\;\;\;\;\;\;\;\;\;\;\; (2)$

となります。

したがって、連立方程式

$\begin{cases} \displaystyle \sum_{i=0}^{d-1} a_i b^i = m^k \;\;\;\;\;\;\;\;\;\;\;\; (1) \\ \displaystyle \sum_{i=0}^{d-1} a_i = m \;\;\;\;\;\;\;\;\;\;\;\; (2) \end{cases}$

を満たす $n = m^k$ がデュードニー数となります。

ここで、前回の議論を思い出すと、不等式の議論を行うことで $b, k$ を固定したときのデュードニー数が有限個であることが示せます。

実際、式 $(1)$ と、最上位の桁が $1$ 以上であることから、

$\displaystyle m^k = \sum_{i=0}^{d-1} a_i b^i \geq b^{d-1}$

が成り立ちます。

また、式 $(2)$ と、各桁が $a_i \leq b - 1$ であることから

$\displaystyle m = \sum_{i=0}^{d-1} a_i \leq \sum_{i=0}^{d-1} (b - 1) = (b - 1)d$

が成り立ちます。

したがって、2つの不等式を合わせて

$\displaystyle b^{d-1} \leq m^k \leq (b-1)d \;\;\;\;\;\;\;\; (3)$

が言えます。

ここで、仮に

$\displaystyle b^{d-1} > (b-1)d \;\;\;\;\;\;\;\; (4)$

が成り立ってしまうと、不等式 $(3)$ を満たす $m^k$ は存在しないことになってしまいます。

しかしながら、不等式 $(4)$ の左辺は $d$ についての指数関数であり、右辺は一次関数であることから、いつかは指数関数が追い抜きます。すなわち、固定した $b$ に対して十分大きな $d$ は式 $(4)$ を常に満たします。

したがって、デュードニー数の条件を満たす $d$ は有限の範囲に収まることが示されました。よって、固定した $b, k$ に対して、デュードニー数は有限個であることがわかりました。

一般化10進デュードニー数のリスト

以上を踏まえて、一般化デュードニー数を計算してみたいと思います。

$b = 10$ として、 $k$ を $2$ から $10$ の範囲で固定して、それぞれのデュードニー数の全リストを求めました。

不等式 $(3)$ のおかげで、本当に全列挙できてしまうのが面白いですね。

k = 2 の場合：

　 $\begin{align*} 1 = 1^{2}, \;\; 81 = 9^{2} \end{align*}$

$k = 2$ の場合、 $1$ と $81$ だけが解となります。

k = 3 の場合（デュードニー数）：

　 $\begin{align*} 1 = 1^{3}, \;\; 512 = 8^{3}, \;\; 4913 = 17^{3}, \;\; 5832 = 18^{3}, \;\; 17576 = 26^{3}, \;\; 19683 = 27^{3} \\ \end{align*}$

$k = 3$ のときは、以上6つがすべての解となります。

実際

$4 + 9 + 1 + 3 = 17$
$5 + 8 + 3 + 2 = 18$
$1 + 7 + 5 + 7 + 6 = 26$
$1 + 9 + 6 + 8 + 3 = 27$

が成り立つことを確認しましょう。

これにより、元々のデュードニーの問題の答えがすべて列挙できたことになりますね。

k = 4 の場合：

　 $\begin{align*} &1 = 1^{4}, \\ &2401 = 7^{4}, \\ &234256 = 22^{4}, \\ &390625 = 25^{4}, \\ &614656 = 28^{4}, \\ &1679616 = 36^{4}, \\ \end{align*}$

k = 5 の場合：

　 $\begin{align*} &1 = 1^{5}, \\ &17210368 = 28^{5}, \\ &52521875 = 35^{5}, \\ &60466176 = 36^{5}, \\ &205962976 = 46^{5}, \\ \end{align*}$

k = 6 の場合：

　 $\begin{align*} &1 = 1^{6}, \\ &34012224 = 18^{6}, \\ &8303765625 = 45^{6}, \\ &24794911296 = 54^{6}, \\ &68719476736 = 64^{6}, \\ \end{align*}$

k = 7 の場合：

　 $\begin{align*} &1 = 1^{7}, \\ &612220032 = 18^{7}, \\ &10460353203 = 27^{7}, \\ &27512614111 = 31^{7}, \\ &52523350144 = 34^{7}, \\ &271818611107 = 43^{7}, \\ &1174711139837 = 53^{7}, \\ &2207984167552 = 58^{7}, \\ &6722988818432 = 68^{7}, \\ \end{align*}$

k = 8 の場合：

　 $\begin{align*} &1 = 1^{8}, \\ &20047612231936 = 46^{8}, \\ &72301961339136 = 54^{8}, \\ &248155780267521 = 63^{8}, \\ \end{align*}$

k = 9 の場合：

　 $\begin{align*} &1 = 1^{9}, \\ &3904305912313344 = 54^{9}, \\ &45848500718449031 = 71^{9}, \\ &150094635296999121 = 81^{9}, \\ \end{align*}$

k = 10 の場合：

　 $\begin{align*} &1 = 1^{10}, \\ &13744803133596058624 = 82^{10}, \\ &19687440434072265625 = 85^{10}, \\ &53861511409489970176 = 94^{10}, \\ &73742412689492826049 = 97^{10}, \\ &179084769654285362176 = 106^{10}, \\ &480682838924478847449 = 117^{10}, \\ \end{align*}$

合同式を用いた分析（自由研究）

以上は計算機を用いた結果ですが、前回のときと同じように、合同式を用いて理論的に攻めることはできないでしょうか。

ちょっと自由研究的に考えてみたいと思います。

$b = 10$ として、一般化10進デュードニー数の条件をまとめると、次の連立方程式となります：

$\begin{cases} \displaystyle \sum_{i=0}^{d-1} a_i 10^i = m^k \;\;\;\;\;\;\;\;\;\;\;\; (1') \\ \displaystyle \sum_{i=0}^{d-1} a_i = m \;\;\;\;\;\;\;\;\;\;\;\; (2') \end{cases}$