local bigint = require "pluto:bigint"
local fmt = require "fmt"

local zero = bigint.new(0)
local one  = bigint.new(1)

-- Only valid for n > 0 && base >= 2.
local function mult(n, base)
    local m = one
    while m > zero and n > zero do
        local q, rem = n:div(base)
        m *= rem
        n = q
    end
    return m
end

-- Only valid for n >= 0 and base >= 2.
local function mult_digital_root(n, base)
    base = bigint.new(base)
    local m = n
    local mp = zero
    while m >= base do
        m = mult(m, base)
        mp += one
    end
    return {mp, tonumber(m:hex(), 16)}
end

local base = 10
local size = 5

local tests = {
    123321, 7739, 893, 899998,"18446743999999999999", 3778888999, "277777788888899"
}

local test_fmt = "%20s %3s %3s"
fmt.print(test_fmt, "Number", "MDR", "MP")
for tests as test do
    local n = bigint.new(test)
    local mpdr = mult_digital_root(n, base)
    fmt.print(test_fmt, n, mpdr[2], mpdr[1])
end
print()

local list = table.create(base)
for i = 1, base do list[i] = {} end
local cnt = size * base
local n = zero
while cnt > 0 do
    local mpdr = mult_digital_root(n, base)
    local mdr = mpdr[2]
    if #list[mdr + 1] < size then
        list[mdr + 1]:insert(n)
        cnt -= 1
    end
    n += one
end
fmt.print("%3s: %s", "MDR", "First")
local i = 0
for list as l do
    fmt.print("%3d: %,s", i, l)
    i += 1
end