カプレカ数という概念があることを某チャットで知りました。
Wikipediaによると2種類の定義があるようですが、そのうち「数字の各桁をシャッフルしてできる数のうち、最大のものから最小のものを引き算して、元の数字と同じになるもの」という2つめの定義のほうをHaskellで実装して遊んでみました。
まず、「数字の各桁をシャッフルしてできる数のうち、最大のものから最小のものを引き算する」関数をさくっと書きます。
module Kaprekar where
import Data.List (permutations, unfoldr)
toDigits :: Int -> [Int]
toDigits n = unfoldr moddiv n
where
moddiv i =
if i == 0
then Nothing
else Just ((i `mod` 10), (i `div` 10))
toInt :: [Int] -> Int
toInt s = sum $ zipWith f s [0..]
where f x i = x * 10^i
arrange :: [Int] -> [Int]
arrange = (map toInt) . permutations
kaprekar :: Int -> Int
kaprekar = diffK . arrange . toDigits
where diffK xs = maximum xs - minimum xs
Wikipediaによると「6174」はカプレカ数らしいので、確かめてみます。
λ> kaprekar 6174
6174
確かに同じ数になっていますね。カプレカ数でない「6173」だと一致しません。
λ> kaprekar 6173
6264
（追記）
nobsun にもっとかっこいいのを教えてもらいました。
https://twitter.com/nobsun/status/1243939964137562113kaprekar :: Int -> Int kaprekar = (subtract . read <*> read . reverse) . sort . show
さらにWikipediaによると、どんな数もこの操作を繰り返すといつかはカプレカ数になるそうです。そこで、カプレカ数になるまでkaprekarを繰り返す関数kaprekaringを書いて確かめてみます。
kaprekaring :: Int -> [Int]
kaprekaring n = n : unfoldr isKaprekar n
where
isKaprekar i =
if kaprekar i == i
then Nothing
else Just (kaprekar i, kaprekar i)
やはりWikipediaに載っている例として、「2005」で試してみます。
λ> kaprekaring 2005
[2005,5175,5994,5355,1998,8082,8532,6174]
Wikipediaの例と同じ列が得られました。「2005」の場合は8回のkaprekarでカプレカ数に収束するようです。
こうなると、カプレカ数に収束する列がどれくらいまで長くなりうるのかが気になってきます。4桁のすべての数字についてカプレカ数に到達するまでの列をもとめて、その最大の長さを割り出してみます。
λ> fst $ maximum $ map ((\xs -> (length xs, xs)) . kaprekaring) [1000..9999]
8
ずいぶん拍子抜けする感じですが、4桁の数はどれも高々8回の繰り返しでカプレカ数に到達してしまうようですね。
ほんとかな。ちょっと不安なので、1回でカプレカ数になるもの（つまりカプレカ数そのもの）から、8回でカプレカ数になるものまで、それぞれどれくらいの個数があるのか見てみます。
λ> [length $ filter (\(x,_) -> x == i) $ map ((\xs -> (length xs, xs)) . kaprekaring) [1000..9999] | i <- [1..8]]
[1,365,587,2124,1124,1311,1508,1980]
4回でカプレカ数に収束するものが2124個でいちばん多いようです。先頭の1は4桁のカプレカ数の総数なので、すでに判明している「6174」だけという事実を表しています1。
各回の総数を合計すると4桁の数の総数になるので、たぶんあってそう。
λ> sum [1,365,587,2124,1124,1311,1508,1980]
9000
-
ちなみに、
kaprekar 1111の値は「0」で、0は自明なカプレカ数なので、ここでは「1111はカプレカ数0に収束」と考えることにします。つまり上記のリストでは2回のところに計上されています。 ↩