require "table2"

local function ends_with_89(n)
    local digit = 0
    local sum = 0
    while true do
        while n > 0 do
            digit = n % 10
            sum += digit * digit
            n //= 10
        end
        if sum == 89 then return true end
        if sum == 1 then return false end
        n = sum
        sum = 0
    end
end

local sums = table.rep(8 * 81, 0)
sums[0] = 1
local s = 0
for n = 1, 8 do
    for i = n * 81, 1, -1 do
        for j = 1, 9 do
            s = j * j
            if s > i then break end
            sums[i] += sums[i - s]
        end
    end
    if n == 8 then
        local count89 = 0
        for i = 1, n * 81 do
            if ends_with_89(i) then count89 += sums[i] end
        end
        print($"There are {string.formatint(count89)} numbers from 1 to 100 million ending with 89.")
    end
end