カプレカ数をPythonで求める｜20桁まで一気に計算

6174や495のような「カプレカ数」を、Pythonで求めてみました。

結論から言うと、1つずつ数字を調べる方法では、5分回しても6個目が出てきませんでした。ところが、数字の並べ方（組み合わせ）で調べる方法に変えると、20桁までのカプレカ数が約1分で全部求まりました。

要点

カプレカ数は、数字を並べ替えた「最大」から「最小」を引くと、元の数に戻る数です
1つずつ調べる方法では、6桁の631764までで止まってしまいました
数字の組み合わせだけを調べると、調べる数がぐっと減って一気に速くなります
20桁までに、カプレカ数は0を含めて66個ありました

カプレカ数とは

6174を例にします。

6174を、6、1、7、4のように1けたずつバラバラにします
それを、一番大きくなる順（7641）と、一番小さくなる順（1467）に並べ替えます
最大から最小を引きます。7641 − 1467 ＝ 6174

このように、最大 − 最小＝元の数 になる数がカプレカ数です。4桁では、6174のほかにはありません。考え方はとてもシンプルです。

なお、「カプレカ数」という名前は、2乗した数を2つに分けて足すと元に戻る数（45など）を指すこともあります。この記事のカプレカ数は、並べ替えて引く方のカプレカ数です。

1つずつ計算して調べてみる

1つずつ手で計算するのは面倒すぎるので、Pythonで書いてみました。学習の題材としても、いい課題になると思います。

import copy

num = 0
while num <= 99999999999999999999:  # 20桁まで求めてみる
    n = []
    for i in range(len(str(num))):
        n.append(str(num)[i])

    n.sort()              # 並べ替え（小さい順）
    s = copy.copy(n)
    n.sort(reverse=True)  # 並べ替え（大きい順）
    s = ''.join(s)        # リストの数字を1つの数字の列にする
    n = ''.join(n)
    kap = int(n) - int(s)  # 最大 − 最小

    if kap == num:        # カプレカ数か判断
        print(num)
    num += 1

結果：5分回しても6個目が出なかった

数秒で5個は出てきましたが、その後は時間がかかりすぎて、途中でやめました。5分回しても6個目が出てきません。20桁なんて夢でした。

この方法では、0から順番に、すべての数を1つずつ調べています。20桁までだと1垓（いちがい）回も計算することになるので、終わるはずがありませんでした。

速い方法：数字の組み合わせで調べる

よく考えると、「最大 − 最小」の答えは、使っている数字の組み合わせだけで決まります。たとえば6174も7641も1467も、使っている数字は同じ「1、4、6、7」なので、引き算の答えは全部同じ6174です。

そこで、数を1つずつ調べるのではなく、数字の組み合わせを1回ずつだけ調べる ことにしました。そして、引き算の答えが、同じ数字の組み合わせでできているかを確かめます。

from itertools import combinations_with_replacement
import time

start = time.time()
for keta in range(1, 21):  # 1桁から20桁まで
    for digits in combinations_with_replacement('0123456789', keta):
        small = ''.join(digits)  # 小さい順に並べた数
        big = small[::-1]        # 大きい順に並べた数
        kap = int(big) - int(small)
        # 答えが同じ数字の組み合わせで、同じ桁数ならカプレカ数
        if sorted(str(kap)) == list(digits) and len(str(kap)) == keta:
            print(kap)
print('かかった時間', round(time.time() - start, 1), '秒')

combinations_with_replacement は、同じ数字を何回使ってもいい組み合わせを作る関数です。20桁でも組み合わせは約1,000万通りなので、1垓回に比べるとほんのわずかです。

結果：20桁まで約1分で全部出た

このコードを動かすと、20桁までのカプレカ数が0を含めて66個出てきました。15桁までなら約5秒、20桁までで約53秒でした（時間はパソコンの性能で変わります）。

桁数	カプレカ数
1桁	0
3桁	495
4桁	6174
6桁	549945、631764
8桁	63317664、97508421
9桁	554999445、864197532
10桁	6333176664、9753086421、9975084201
11桁	86431976532
12桁	555499994445、633331766664、975330866421、997530864201、999750842001

13桁より大きいものも、20桁まで続けて出てきます。2、5、7桁には、カプレカ数はありませんでした。

1つずつ調べた方法で6個目が出なかったのは、7桁にカプレカ数がなく、次が8桁の63317664だったからです。1つずつの方法だと、6300万回以上計算しないとたどり着きません。

まとめ

カプレカ数は、数字を並べ替えた「最大 − 最小」が元の数に戻る数です
1つずつ調べる方法では、6桁の631764までしか出せませんでした
数字の組み合わせで調べると、20桁までの66個が約1分で求まりました
計算の回数を減らす工夫をすると、プログラムは何万倍も速くなります

専門家ではないので、誤りなどを見つけた方は教えていただけると助かります。

ほかにも、Pythonの練習問題としてFizzBuzz問題を書いた記事があります。

退屈なことはPythonにやらせよう第2版 ―ノンプログラマーにもできる自動化処理プログラミング