#!/usr/bin/ruby

#
## http://rosettacode.org/wiki/Kaprekar_numbers
#

var kap = Hash()
var nt = frequire('ntheory')

for n in (1..15) {
    var np = (10**n - 1)
    nt.fordivisors({ |d|
        var dp = np//d
        if (gcd(d, dp) == 1) {
            kap{ dp == 1 ? d : d*invmod(d, dp) } := 0 ++
        }
    }, np)
}

var nums = kap.keys.map{ Num(_) }.sort

for n in (6 .. 14) {
    var np = (10**n - 1)
    printf("Kaprekar numbers <= 10^%2d:  %5d\n", n, nums.count_by { _ <= np })
}
