スミス数

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。

はじめに

前のエントリ「ヴァンパイア数」に続いて、名前がついている合成数について取り上げます。本稿では、素因数分解を使いますので、まずは素数列を求めるプログラムと素因数分解のプログラムを下記に掲載しておきましょう。

素数列 p と素因数分解 factors

p=2:3:5#p;n#x@(m:p:y)=[n|gcd m n<2]++(n+2)#last(x:[m*p:y|p^2-3<n])
factor n (x:xs) | n `mod` x == 0 = x | otherwise = factor n xs
factors n | n == 1 = [] | otherwise = q : factors (n `div` q) where q = factor n p

スミス数

次のような性質をもつ合成数をスミス数と呼びます。元祖数字遊びのような数です。

スミス数の定義

自然数$n$の各位の数字の和と、その数を素因数分解した数字の各位の和が等しい数

Wikipediaや他で紹介されている情報では $166$ が例示されていますが、ここでは $728$ を例にします。$728$ を素因数分解すると $728 = 2 \times 2 \times 2 \times 7 \times 13$ です。この素因数の各位の和は、$ 2 + 2 + 2 + 7 + ( 1 + 3 ) = 17$ です。一方で、もとの数の各位の和は、$ 7 + 2 + 8 = 17$ となり、等しくなります。このような数をスミス数と呼びます。

名前の由来（4937775）

Wikipediaによると、「スミス数」という名前は Albert Wilansky によって名付けられまたそうです。彼の義理の兄 Harold Smith の電話番号 $4937775$ がこの性質をもつことに由来します。（試してみると、$4937775=3 \times 5 \times 5 \times65837$ なので、もとの数の各位の和は $4+9+3+7+7+7+5=42$ に対して、素因数の各位の和は $3+5+5+(6+5+8+3+7)=42$ で等しい）

次に、スミス数を求めるために、スミス数を判定する関数isSmithを定義します。

スミス数の判定 isSmith

import Data.List (unfoldr)
import Data.Tuple (swap)
sumDigits = sum . (unfoldr r) where r x | x==0 = Nothing | otherwise = Just (swap (quotRem x 10))
isSmith n = fs /= [n] && sumDigits n == foldr ((+) . sumDigits) 0 fs where fs = factors n

これを用いて、さらに出力のためのchunk関数をつかって、2〜9999 まで調べてみると次のようになります。

ghci> chunk n xs | xs == [] = [] | otherwise = take n xs : chunk n (drop n xs)
ghci> mapM_ print $ chunk 20 $  filter isSmith [2..9999]
[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,1219,1255,1282,1284,1376,1449,1507,1581]
[1626,1633,1642,1678,1736,1755,1776,1795,1822,1842,1858,1872,1881,1894,1903,1908,1921,1935,1952,1962]
[1966,2038,2067,2079,2155,2173,2182,2218,2227,2265,2286,2326,2362,2366,2373,2409,2434,2461,2475,2484]
[2515,2556,2576,2578,2583,2605,2614,2679,2688,2722,2745,2751,2785,2839,2888,2902,2911,2934,2944,2958]
[2964,2965,2970,2974,3046,3091,3138,3168,3174,3226,3246,3258,3294,3345,3366,3390,3442,3505,3564,3595]
[3615,3622,3649,3663,3690,3694,3802,3852,3864,3865,3930,3946,3973,4054,4126,4162,4173,4185,4189,4191]
[4198,4209,4279,4306,4369,4414,4428,4464,4472,4557,4592,4594,4702,4743,4765,4788,4794,4832,4855,4880]
[4918,4954,4959,4960,4974,4981,5062,5071,5088,5098,5172,5242,5248,5253,5269,5298,5305,5386,5388,5397]
[5422,5458,5485,5526,5539,5602,5638,5642,5674,5772,5818,5854,5874,5915,5926,5935,5936,5946,5998,6036]
[6054,6084,6096,6115,6171,6178,6187,6188,6252,6259,6295,6315,6344,6385,6439,6457,6502,6531,6567,6583]
[6585,6603,6684,6693,6702,6718,6760,6816,6835,6855,6880,6934,6981,7026,7051,7062,7068,7078,7089,7119]
[7136,7186,7195,7227,7249,7287,7339,7402,7438,7447,7465,7503,7627,7674,7683,7695,7712,7726,7762,7764]
[7782,7784,7809,7824,7834,7915,7952,7978,8005,8014,8023,8073,8077,8095,8149,8154,8158,8185,8196,8253]
[8257,8277,8307,8347,8372,8412,8421,8466,8518,8545,8568,8628,8653,8680,8736,8754,8766,8790,8792,8851]
[8864,8874,8883,8901,8914,9015,9031,9036,9094,9166,9184,9193,9229,9274,9276,9285,9294,9296,9301,9330]
[9346,9355,9382,9386,9387,9396,9414,9427,9483,9522,9535,9571,9598,9633,9634,9639,9648,9657,9684,9708]
[9717,9735,9742,9760,9778,9840,9843,9849,9861,9880,9895,9924,9942,9968,9975,9985]

せきゅーんさんのブログにも幾つか特徴的な数について紹介があります。下記ブログで鑑賞してみてください。

おわりに

最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。

• macOS: Sonoma 14.5 (chip: Apple M1)
• GHCup: 0.1.30.0
• GHC: 9.6.4

ご一読いただきまして有り難うございます。
（●）（●） Happy Hacking!
/""　＿＿""＼