63 lines
1.5 KiB
Text
63 lines
1.5 KiB
Text
local int = require "int"
|
|
local fmt = require "fmt"
|
|
|
|
$define MAX_DIGITS = 15
|
|
|
|
local pps = {}
|
|
|
|
local function get_perfect_powers(max_exp)
|
|
local upper = 10 ^ max_exp
|
|
for i = 2.0, int.sqrt(upper) do
|
|
local p = i
|
|
while true do
|
|
p *= i
|
|
if p >= upper then break end
|
|
pps[p] = true
|
|
end
|
|
end
|
|
end
|
|
|
|
local function get_achilles(min_exp, max_exp)
|
|
local lower = 10 ^ min_exp
|
|
local upper = 10 ^ max_exp
|
|
local achilles = {} -- avoids duplicates
|
|
for b = 1.0, int.cbrt(upper) do
|
|
local b3 = b * b * b
|
|
for a = 1.0, int.sqrt(upper) do
|
|
local p = b3 * a * a
|
|
if p >= upper then break end
|
|
if p >= lower then
|
|
if !pps[p] then achilles[p] = true end
|
|
end
|
|
end
|
|
end
|
|
return achilles
|
|
end
|
|
|
|
get_perfect_powers(MAX_DIGITS)
|
|
local achilles_set = get_achilles(1, 5) -- enough for first 2 parts
|
|
local achilles = achilles_set:keys()
|
|
achilles:sort()
|
|
|
|
print("First 50 Achilles numbers:")
|
|
fmt.tprint("%4d", achilles:slice(1, 50), 10)
|
|
|
|
print("\nFirst 30 strong Achilles numbers:")
|
|
local strong_achilles = {}
|
|
local count = 0
|
|
local n = 1
|
|
while count < 30 do
|
|
local tot = int.totient(achilles[n])
|
|
if achilles_set[tot] then
|
|
strong_achilles:insert(achilles[n])
|
|
++count
|
|
end
|
|
++n
|
|
end
|
|
fmt.tprint("%5d", strong_achilles, 10)
|
|
|
|
print("\nNumber of Achilles numbers with:")
|
|
for d = 2, MAX_DIGITS do
|
|
local ac = get_achilles(d - 1, d):size()
|
|
fmt.print("%2d digits: %d", d, ac)
|
|
end
|