銀月の符号

Python 使い見習いの日記・雑記

スミス数（すみすすう）

Python 日記

すみすさんの すみす.jp ドメイン取得祝いに、スミス数ライブラリを Python で書いたよ。*1

Python 2.6.4 で作成、動作確認。

version 1.0.1 。 Python 2.5.4 でも動作をするように修正した。ただし Python 2.4.4 では動作しないことを確認。

version 1.0.2 。 Python 2.4.4 でも動作をするように修正した。

version 1.0.3 。 Python 2.5 以前で使用する自作 next 関数に多すぎる引数を与えるとエラーメッセージ生成時に TypeError を起こしていたので修正。テストの Python 2.5 以前用対策を修正。

version 1.1 。 各種イテレータが生成する値の初期値を指定できるようにした。 smith_numbers(1000) なら 1000 以上で最も小さいスミス数 1111 から出力する。 smith_numbers() ならいままでどおり最小スミス数 4 から出力する。

スミス数とは

スミス数とは 10 進数表記での数字の和 S(N) と素因子の数字の和 Sp(N) が等しい合成数 N のこと。

例えば 85 は S(85)=8+5=13 であり、 Sp(85)=Sp(5*17)=5+1+7=13 であるためスミス数。 86 は S(86)=8+6=14, Sp(86)=Sp(2*43)=2+4+3=9 なのでスミス数ではない。 7 は S(7)=Sp(7)=7 だけど素数であり、合成数ではないのでスミス数ではない。

>>> from smithnumber import is_smith_number
>>> is_smith_number(85)
True
>>> is_smith_number(86)
False
>>> is_smith_number(7)
False

100 未満のスミス数は 6 個ある。

>>> from itertools import takewhile
>>> from smithnumber import smith_numbers
>>> tuple(takewhile(lambda x: x < 100, smith_numbers()))
(4, 22, 27, 58, 85, 94)

スミス数は無限にある。 smith_numbers イテレータ使用の際には終了条件をつけるのをお忘れなく*2。

>>> from smithnumber import smith_numbers
>>> for i in smith_numbers(): # 正常終了せず
...   pass
...

スミス数のバリエーション

http://www.shyamsundergupta.com/smith.htm には、いろんなスミス数が紹介されている。 smithnumber.py にはこのサイトを参考にして作成した、これらのスミス数を順次生成するイテレータ(smith_numbers など)と、ある数がそうなのかどうか判定する関数(is_smith_number など)を詰め込んである。ものによってはなかなか返事が返ってこないものもあるので注意。

Smith Number ([http
//www.research.att.com/~njas/sequences/A006753:title=A006753]):スミス数 (2*2=4, 2*11=22, 3*3*3=27 など)
Smith Semiprime ([http
//www.research.att.com/~njas/sequences/A098837:title=A098837]):2つの素因数からなるスミス数 (2*2=4, 2*11=22, 2*29=58 など)
Palindromic Smith Number ([http
//www.research.att.com/~njas/sequences/A098834:title=A098834]):回文数でもあるスミス数 (121, 1111, 10201, 164461 など)
Reversible Smith Number ([http
//www.research.att.com/~njas/sequences/A104171:title=A104171]):反転させてもスミス数 (319, 913 など)
Fibonacci Smith Number
フィボナッチ数でもあるスミス数 (F31=1346269, F77, F231)
Abundant Smith Number ([http
//www.research.att.com/~njas/sequences/A098835:title=A098835]):過剰数でもあるスミス数 (378, 438, 576 など)
Deficient Smith Number ([http
//www.research.att.com/~njas/sequences/A098836:title=A098836]):不足数でもあるスミス数 (4, 22, 27 など)
Smith Square Number ([http
//www.research.att.com/~njas/sequences/A098839:title=A098839]):平方数でもあるスミス数 (4 など)
Smith Cubic Number ([http
//www.research.att.com/~njas/sequences/A098838:title=A098838]):立法数でもあるスミス数 (27 など)
Smith Trianglar Number ([http
//www.research.att.com/~njas/sequences/A098840:title=A098840]):三角数でもあるスミス数 (378 など)
Repdigit Smith Number ([http
//www.research.att.com/~njas/sequences/A104166:title=A104166]):すべての数字が等しいスミス数 (4, 22, 666, 1111, 6666666など)
k-Consecutive Smith Numbers
k 連続するスミス数の組。 k>=8 の存在は不明。
Smith Brothers ([http
//www.research.att.com/~njas/sequences/A050219:title=A050219]):2 連続スミス数 (728, 729 など)
Smith Triples ([http
//www.research.att.com/~njas/sequences/A105648:title=A105648]):3 連続スミス数 (73615, 73616, 73617 など)
Smith Quads ([http
//www.research.att.com/~njas/sequences/A104649:title=A104649]):4 連続スミス数 (4463535, 4463536, 4463537, 4463538 など)
Smith Quints ([http
//www.research.att.com/~njas/sequences/A105650:title=A105650]):5 連続スミス数 (15966114, 15966115, 15966116, 15966117, 15966118 など)
k-Smith Number
「数字合計のk倍」と「素因数の数字合計」が等しい数。 k=1 で通常のスミス数。
2-Smith Number([http
//www.research.att.com/~njas/sequences/A104390:title=A104390]):(32, 42, 60 など)
3-Smith Number([http
//www.research.att.com/~njas/sequences/A104391:title=A104391]):(402, 510, 700 など)
4-Smith Number([http
//www.research.att.com/~njas/sequences/A103125:title=A103125]):(2401, 5010, 7000 など)
5-Smith Number([http
//www.research.att.com/~njas/sequences/A103126:title=A103126]):(2030, 10203, 12110 など)
(k^-1)-Smith Number
「数字合計の1/k倍」と「素因数の数字合計」が等しい数。 k=1 で通常のスミス数。括弧部分は正しくは k の -1 乗。
(2^-1)-Smith Number([http
//www.research.att.com/~njas/sequences/A050224:title=A050224]):(88, 169, 286 など)
(3^-1)-Smith Number([http
//www.research.att.com/~njas/sequences/A050225:title=A050225]):(6969, 19998, 36399 など)
(4^-1)-Smith Number([http
//www.research.att.com/~njas/sequences/A103123:title=A103123]):(19899699, 36969999, 36999699 など)
(5^-1)-Smith Number([http
//www.research.att.com/~njas/sequences/A103124:title=A103124]):(399996663, 666609999, 669969663 など)

個人的には 2 連続するスミス数の組の名前、「Smith Brothers」の響きが好き。

*1:スミス数自体はなんの役に立つかはわからない（まて、役に立たないものをプレゼントするな）。 n 進数のスミス数を定義して、かつそれに面白い性質が見つかれば化けるのかもしれないけれどそんなことはなさそうだし。でもライブラリ作成過程で素因数分解の方法を学べたり、平方数、立方数、三角数、過剰数、不足数、回文数などの数、数列たちと出会えたのはよかった。あとオンライン整数列大辞典というサイトを知ったのも。

*2:itertools.repeat などのようにハードウェアが壊れるか電源供給が止まるかするまで動き続けるということはないはず。かなりの長時間動いた後、巨大な Python 長整数インスタンスが MemoryError を引き起こすことになると予想している。