37 lines
849 B
Text
37 lines
849 B
Text
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
|