ナルシシスト数

図：ナルシシスト数のイメージ（ChatGPTによる）

ナルシシスト数とは，各桁を「桁数乗」した和が元の数に一致する数のことである。たとえば 3 桁の 153 は，1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153 なので，これに該当する。10 進数では全部で 88 個のナルシシスト数しか存在せず（1桁の1〜9は自明），最大は39桁の 115132219018763992565095597973971522401 であることがわかっている。

これを求めるJuliaプログラムをChatGPTにつくってもらう。しらみつぶしでは，10^39個のチェックが必要なので宇宙的時間がかかる。もとのChatGPTのコードでは，MacBook Air M1（16GB）で30桁までを2時間以内で計算できたが，35桁まではメモリがあふれて無理だった。そこで，Claudeにコードの見直しを頼んだところ，劇的にメモリと実行時間が改善されて，最大39桁まで求めることができるようになった。

koshi@mba2020 % julia -t auto nar.jl 5

threads = 4,  maxdigits = 5

  0.015720 seconds (42.52 k allocations: 2.053 MiB, 390.47% compilation time)

# 0.238553 seconds (819.56 k allocations: 36.810 MiB, 99.02% compilation time)

count = 10 (19)

koshi@mba2020 % julia -t auto nar.jl 10

threads = 4,  maxdigits = 10

  0.022560 seconds (43.89 k allocations: 2.125 MiB, 274.50% compilation time)

# 0.727917 seconds (11.10 M allocations: 265.898 MiB, 30.57% compilation time)

count = 23 (32)

koshi@mba2020 % julia -t auto nar.jl 15

threads = 4,  maxdigits = 15

  0.166714 seconds (46.73 k allocations: 2.264 MiB, 38.92% compilation time)

# 9.047403 seconds (236.09 M allocations: 5.176 GiB, 2.37% compilation time)

count = 32 (41)

koshi@mba2020 % julia -t auto nar.jl 20

threads = 4,  maxdigits = 20

   1.793978 seconds (51.71 k allocations: 2.525 MiB, 3.45% compilation time)

# 95.901206 seconds (2.74 G allocations: 60.317 GiB, 0.24% compilation time)

count = 42 (51)

koshi@mba2020 % julia -t auto nar.jl 25

threads = 4,  maxdigits = 25

   12.477025 seconds (59.49 k allocations: 2.894 MiB, 0.50% compilation time)

# 857.291978 seconds (18.41 G allocations: 413.536 GiB, 0.03% compilation time)

count = 57 (66)

koshi@mba2020 % julia -t auto nar.jl 30

threads = 4,  maxdigits = 30

    59.770551 seconds (70.61 k allocations: 3.388 MiB, 0.11% compilation time)

# 6715.091422 seconds (88.46 G allocations: 1.925 TiB, 0.00% compilation time)

count = 66 (75)

koshi@mba2020 % julia -t auto nar.jl 35

threads = 4,  maxdigits = 35

216.267226 seconds (85.74 k allocations: 4.133 MiB, 0.04% compilation time)

# unmeasureable

count = 75 (84)

koshi@mba2020 % julia -t auto nar.jl 39                     

threads = 4,  maxdigits = 39

2690.310601 seconds (143.28 k allocations: 6.921 MiB, 0.00% compilation time)

# unmeasureable

BigInt[153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914, 28116440335967, 4338281769391370, 4338281769391371, 21897142587612075, 35641594208964132, 35875699062250035, 1517841543307505039, 3289582984443187032, 4498128791164624869, 4929273885928088826, 63105425988599693916, 128468643043731391252, 449177399146038697307, 21887696841122916288858, 27879694893054074471405, 27907865009977052567814, 28361281321319229463398, 35452590104031691935943, 174088005938065293023722, 188451485447897896036875, 239313664430041569350093, 1550475334214501539088894, 1553242162893771850669378, 3706907995955475988644380, 3706907995955475988644381, 4422095118095899619457938, 121204998563613372405438066, 121270696006801314328439376, 128851796696487777842012787, 174650464499531377631639254, 177265453171792792366489765, 14607640612971980372614873089, 19008174136254279995012734740, 19008174136254279995012734741, 23866716435523975980390369295, 1145037275765491025924292050346, 1927890457142960697580636236639, 2309092682616190307509695338915, 17333509997782249308725103962772, 186709961001538790100634132976990, 186709961001538790100634132976991, 1122763285329372541592822900204593, 12639369517103790328947807201478392, 12679937780272278566303885594196922, 1219167219625434121569735803609966019, 12815792078366059955099770545296129367, 115132219018763992565095597973971522400, 115132219018763992565095597973971522401]

count = 79 (88)

#はoriginalのChatGPTのコードでの実行時間とメモリ，countの()は自明の1-9を加えたもの。

Ａ（Claude）：

（以下は，Claudeに元のコードのキモを解説させた結果の要約）

キモ①：数を総当たりしない発想の転換

$n$桁の数の各桁の数字の$n$乗の和 $s$ は，$s = \sum_{d=0}^9$ （数字 $d$ の個数）× d^n

である。これは，どの数字が何個あるかだけに依存してその並び順には依存しない。組み合わせの数は，Binomial[n+9,9]であり（$n$=39で1.7*10^9），$10^n$ にくらべて圧倒的に小さい。この振り分け個数ベクトル(10次元) を再帰的に全列挙する。ベクトルの成分の和が$n$になる。

キモ②：正しさを保証する「自己一致チェック」

振り分け個数ベクトルから得られる和$s$がナルシシスト数であるには，「$s$がちょうど$n$桁で，かつ$s$を実際に分解した数字の個数が，最初に仮定したベクトルと一致する」必要がある。

キモ③：分枝限定法（枝刈り）

narcissistic(n ごとにループ)

   └ search_n_threaded(T, n)

        ├ pows = T[T(d)^n for d in 0:9]   ← ここで n を使って累乗を1回だけ計算

        └ search_counts!(…, pows, …)       ← 出来た pows を渡す

              └ search_counts!(…, pows, …) ← 再帰。pows[d] を引くだけ(n は不要)

このpowsを使って，serach_counts! の冒頭で以下のように不要な計算を省いている。

if s + rem * pows[d] > hi   # 残り rem 桁を「全部いまの最小の数字」にしても hi超え

    return                   # → これ以上どう積んでも超えるので即打ち切り

end

if s + rem * pows[10] < lo  # 残りを「全部 9」にしても lo に届かない

    return                   # → 逆にどう積んでも足りないので打ち切り

end

キモ④：並列化の切り口

（回答略）

要するに全体の構造は、「個数ベクトルの全列挙（枝刈り付き）」→「和 s を構成」→「s の実際の桁構成が仮定と一致するか検証」 という三段で、最初の「数そのものではなく個数の分配を回す」発想がこのコードの心臓部である。