Posts Tagged ‘chain’

Programming Praxis – Two Kaprekar Exercises

March 22, 2011

In today’s Programming Praxis exercise,our goal is to determine the longest possible Kaprekar chain and the Kaprekar numbers below 1000. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.List.Key as K
import Text.Printf

The Kaprekar chain algorithm is fairly simple. We use printf for easy padding of the number.

chain :: Int -> [Int]
chain 0 = []
chain 6174 = [6174]
chain n = n : chain (read (reverse p) - read p) where
    p = sort $ printf "%04d" n

Determining whether a number is a Kaprekar number is made easier by realizing that the whole ‘take the first n-1 or n and the last n digits’ bit can be replaced with the divMod function.

isKaprekar :: Integral a => a -> Bool
isKaprekar n = n == uncurry (+) (divMod (n^2) $ 10 ^ length (show n))

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ chain 2011 == [2011, 1998, 8082, 8532, 6174]
          print . K.maximum length $ map chain [0..9999]
          print $ filter isKaprekar [1..999] ==
                  [1, 9, 45, 55, 99, 297, 703, 999]

The chain shown is just one of 2184 possible chains of length 8. The first chain of length 8 starts with 14.