Sphenic numbers
editable example
Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.
ghul
use IO.Std.write_line
use Collections
use Ghul.Pipes
let search_limit = 1000000
smallest_prime_factors(limit: int) -> List[int] is
let factor = LIST()
(0..limit) |> each(_ => factor.add(0))
let prime mut = 2
while prime * prime < limit do
if factor[prime] == 0 then
let multiple mut = prime * prime
while multiple < limit do
if factor[multiple] == 0 then
factor[multiple] = prime
fi
multiple = multiple + prime
od
fi
prime = prime + 1
od
let n mut = 2
while n < limit do
if factor[n] == 0 then
factor[n] = n
fi
n = n + 1
od
return factor
si
is_sphenic(n: int, factor: List[int]) -> bool => (
let rest mut = n
let previous mut = 0
let total mut = 0
let distinct mut = 0
while rest > 1 do
let prime = factor[rest]
total = total + 1
if prime != previous then
distinct = distinct + 1
previous = prime
fi
rest = rest / prime
od
total == 3 /\ distinct == 3
)
prime_factors(n: int, factor: List[int]) -> List[string] => (
let rest mut = n
let factors = LIST[string]()
while rest > 1 do
let prime = factor[rest]
factors.add("{prime}")
rest = rest / prime
od
factors
)
let factor = smallest_prime_factors(search_limit)
let sphenics =
(2..search_limit)
|> filter(n => is_sphenic(n, factor))
|> collect_list()
let below_1000 = sphenics |> filter(n => n < 1000) |> join(", ")
write_line("sphenic numbers below 1000: {below_1000}")
let triplets = LIST()
let i mut = 0
while i + 2 < sphenics.count do
if sphenics[i + 1] == sphenics[i] + 1 /\
sphenics[i + 2] == sphenics[i] + 2
then
triplets.add(sphenics[i])
fi
i = i + 1
od
write_line("sphenic triplets below 10000:")
for first in triplets do
if first + 2 < 10000 then
write_line("({first}, {first + 1}, {first + 2})")
fi
od
write_line("sphenic numbers below {search_limit}: {sphenics.count}")
write_line("sphenic triplets below {search_limit}: {triplets.count}")
let sphenic_200000th = sphenics[200000 - 1]
write_line(
"the 200000th sphenic number is {sphenic_200000th} = {
prime_factors(sphenic_200000th, factor) |> join(" x ")
}"
)
let triplet_5000th = triplets[5000 - 1]
write_line(
"the 5000th sphenic triplet is "
"({triplet_5000th}, {triplet_5000th + 1}, {triplet_5000th + 2})")