カプレカ数 (kaprekar number) はインドの数学者 D. R. Kaprekar 氏にちなんだ自然数のことで、参考 URL 『カプレカー数 - Wikipedia』によると、以下に示す二通りの定義があります。
今回は定義 2 のカプレカ数を取り上げます。ここでは、整数の桁を並べ替えて最大値と最小値の差を求める操作を「カプレカ操作」と呼ぶことにします。カプレカ操作とカプレカ数の簡単な例を示します。
123 => 321 - 123 = 198 198 => 981 - 189 = 792 792 => 972 - 279 = 693 693 => 963 - 369 = 594 594 => 954 - 459 = 495 495 => 954 - 459 = 495
このように、3 桁の整数にカプレカ操作を適用していくと、最後は 495 になります。495 はカプレカ操作を適用しても自身の値になるのでカプレカ数です。ちなみに、3 桁の整数の中でカプレカ数は 495 だけしかありません。
N 桁の整数は有限個しかなく、カプレカ操作を適用しても桁数は変化しません。したがって、カプレカ操作を繰り返し適用していくと、いつかは同じ整数が出現することになります。つまり、最後は循環ループになるのです。このループの周期が 1 なものをカプレカ数というわけです。
3 桁の整数にカプレカ操作を適用していくと、すべての数でカプレカ数 495 に到達します。桁数によっては、カプレカ数が存在しない場合もあるでしょう。その場合でも循環ループは存在すると思われます。今回は 2 - 8 桁のカブレラ数と循環ループを求めてみましょう。使用するプログラミング言語は Python3 (PyPy3) です。
それではプログラムを作りましょう。カプレカ数だけを求めるのであれば簡単です。最初に数値を桁に分解する関数 split_number() と、リストを数値に変換する関数 to_number() を作ります。
リスト : 数値の分解と合成
# 数値を桁に分解
def split_number(n, d):
xs = []
for _ in range(d):
xs.append(n % 10)
n //= 10
return xs
# リストを数値に変換
def to_number(xs):
n = 0
for x in xs:
n = n * 10 + x
return n
split_number() の引数 n が整数値、d が桁数を表します。桁の順番は逆になりますが、カプレカ操作を行うのに不都合はありません。to_number() の引数 xs は数字を格納したリストです。今回は for ループでプログラムしましたが、モジュール functools の関数 reduce() を使ってもかまいません。
簡単な実行例を示します。
>>>> split_number(12345, 5) [5, 4, 3, 2, 1] >>>> split_number(10000, 5) [0, 0, 0, 0, 1] >>>> split_number(1, 5) [1, 0, 0, 0, 0] >>>> to_number([1, 2, 3, 4, 5]) 12345 >>>> to_number([1, 0, 0, 0, 0]) 10000 >>>> to_number([0, 0, 0, 0, 1]) 1
次はカプレカ操作を行う関数 kaprekar_op() を作ります。
リスト : カプレカ操作
def kaprekar_op(n, d):
xs = split_number(n, d)
xs.sort()
x = to_number(xs)
xs.reverse()
y = to_number(xs)
return y - x, y, x
引数 n が整数値、d が桁数を表します。最初に、split_number() で数値を分解し、変数 xs にセットします。次に、xs を sort() で昇順にソートし、to_number() で数値に変換します。これが最小値 x になります。xs を reverse() で反転して数値に変換すると最大値 y を求めることができます。あとは、return で y - x, y, x を返します。
簡単な実行例を示します。
>>>> kaprekar_op(12345, 5) (41976, 54321, 12345) >>>> kaprekar_op(54321, 5) (41976, 54321, 12345) >>>> kaprekar_op(35142, 5) (41976, 54321, 12345) >>>> kaprekar_op(90000, 5) (89991, 90000, 9) >>>> kaprekar_op(900, 5) (89991, 90000, 9) >>>> kaprekar_op(9, 5) (89991, 90000, 9)
最後にカプレカ数を求めるプログラムを作ります。
リスト : カプレカ数
# d 桁のカプレカ数を求める
def kaprekar_d(d):
s = 10 ** (d - 1) - 1 + 9
e = 10 ** d
for n in range(s, e, 9):
a, b, c = kaprekar_op(n, d)
if n == a:
print(f'{a} = {b} - {c}')
def kaprekar_number(x):
for d in range(2, x + 1):
print(f'----- {d} -----')
kaprekar_d(d)
関数 kaprekar_d() の引数 d は求めるカプレカ数の桁数を表します。参考 URL 『カプレカー数 - Wikipedia』によると、『カプレカ数は 9 の倍数になる』とのことです。1 桁少ない整数の最大値は 10d-1 - 1 で、これは 9 の倍数 (9, 99, 999, ...) になるので、それに 9 を加えた値 s が始点になります。
あとは、range() で 9 を加算していき、整数 n にカプレカ操作 kaprekar_op() を適用します。n と a が等しい場合、見つけたカプレカ数を print() で出力します。関数 kaprekar_number() は 2 桁から x 桁までのカプレカ数を求めます。
それでは実行してみましょう。
>>>> s = time.time(); kaprekar_number(8); time.time() - s ----- 2 ----- ----- 3 ----- 495 = 954 - 459 ----- 4 ----- 6174 = 7641 - 1467 ----- 5 ----- ----- 6 ----- 549945 = 995544 - 445599 631764 = 766431 - 134667 ----- 7 ----- ----- 8 ----- 63317664 = 76664331 - 13346667 97508421 = 98754210 - 1245789 4.428447008132935 >>>> s = time.time(); kaprekar_number(9); time.time() - s ----- 2 ----- ・・・省略・・・ ----- 9 ----- 554999445 = 999555444 - 444555999 864197532 = 987654321 - 123456789 47.120784521102905 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
カプレカ数だけならば 9 桁でも PyPy3 で求めることができました。この結果は参考 URL 『カプレカー数 - Wikipedia』と一致します。カプレカ数の個数は思っていたよりもずっと少ないようです。
今度はカプレカ数だけではなく循環ループも求めてみましょう。プログラムは次のようになります。
リスト : 循環ループを求める
def kaprekar_l(n, d):
xs = [n]
while True:
a, _, _ = kaprekar_op(n, d)
if a in xs:
return xs[xs.index(a):]
xs.append(a)
n = a
def check_same_loop(ls, xss):
for xs in xss:
if ls[0] in xs: return True
return False
def kaprekar_ld(d):
s = 10 ** (d - 1)
e = 10 ** d
xss = []
for n in range(s, e):
ls = kaprekar_l(n, d)
if ls == [0] or check_same_loop(ls, xss): continue
xss.append(ls)
return xss
関数 kaprekar_l() は整数 n にカプレカ操作を繰り返し適用し、循環ループを検出します。変数 xs を [n] に初期化します。あとは n にカプレカ操作を適用し、その結果 a を xs に追加します。このとき、a が xs に含まれていれば、末尾の要素から xs.index(a) の位置にループすることがわかります。ループしている範囲を取り出して返します。
関数 kaprekar_ld() は d 桁の循環ループを探します。力任せに検索しているので、桁数が増えると時間がかかることに注意してください。見つけたループは変数 xss のリストに格納します。
まず、kaprekar_l() を呼び出して、整数 n が到達するループ ls を求めます。ls が [0] または xss にあるループと同じならば、continue で次の数値を調べます。そうでなければ、append() で ls を xss に追加します。関数 check_same_loop() は簡単です。ls の要素 (ls[0]) が xss のループ xs に含まれていれば同じループであることがわかります。
それでは実行してみましょう。
>>>> s = time.time(); print(kaprekar_ld(2)); time.time() - s [[9, 81, 63, 27, 45]] 0.0007729530334472656 >>>> s = time.time(); print(kaprekar_ld(3)); time.time() - s [[495]] 0.0022063255310058594 >>>> s = time.time(); print(kaprekar_ld(4)); time.time() - s [[6174]] 0.0223236083984375 >>>> s = time.time(); print(kaprekar_ld(5)); time.time() - s [[74943, 62964, 71973, 83952], [63954, 61974, 82962, 75933], [53955, 59994]] 0.23913860321044922 >>>> s = time.time(); print(kaprekar_ld(6)); time.time() - s [[851742, 750843, 840852, 860832, 862632, 642654, 420876], [631764], [549945]] 4.351001739501953 >>>> s = time.time(); print(kaprekar_ld(7)); time.time() - s [[8429652, 7619733, 8439552, 7509843, 9529641, 8719722, 8649432, 7519743]] 46.72070074081421 >>>> s = time.time(); print(kaprekar_ld(8)); time.time() - s [[86526432, 64308654, 83208762], [86308632, 86326632, 64326654, 43208766, 85317642, 75308643, 84308652], [97508421], [63317664]] 438.98128032684326
8 桁の循環ループを求めるのに 7 分以上かかりました。M.Hiroi の実行環境では、このあたりが限界なのかもしれません。今回の結果は参考 URL 『高次桁のカプレカ変換１ (PDF)』と一致しました。それにしても、カプレカ数だけではなく循環ループの個数も極めて少ないですね。この結果にはちょっと驚きました。
#
# kaprekar.py : カプレカ数
#
# Copyright (C) 2022 Makoto Hiroi
#
# 数値を桁に分解
def split_number(n, d):
xs = []
for _ in range(d):
xs.append(n % 10)
n //= 10
return xs
# リストを数値に変換
def to_number(xs):
n = 0
for x in xs:
n = n * 10 + x
return n
# カプレカ操作
def kaprekar_op(n, d):
xs = split_number(n, d)
xs.sort()
x = to_number(xs)
xs.reverse()
y = to_number(xs)
return y - x, y, x
# d 桁のカプレカ数を求める
def kaprekar_d(d):
s = 10 ** (d - 1) - 1 + 9
e = 10 ** d
for n in range(s, e, 9):
a, b, c = kaprekar_op(n, d)
if n == a:
print(f'{a} = {b} - {c}')
def kaprekar_number(x):
for d in range(2, x + 1):
print(f'----- {d} -----')
kaprekar_d(d)
# 循環ループを求める
def kaprekar_l(n, d):
xs = [n]
while True:
a, _, _ = kaprekar_op(n, d)
if a in xs:
return xs[xs.index(a):]
xs.append(a)
n = a
def check_same_loop(ls, xss):
for xs in xss:
if ls[0] in xs: return True
return False
def kaprekar_ld(d):
s = 10 ** (d - 1)
e = 10 ** d
xss = []
for n in range(s, e):
ls = kaprekar_l(n, d)
if ls == [0] or check_same_loop(ls, xss): continue
xss.append(ls)
return xss