(phixonline)-->
without js -- 8s
--with javascript_semantics -- 52s!! (see note)
constant steps = 20,
primes = 45
sequence known_factors = {} -- nb: no specific order
function combine_factors(sequence n)
-- (inverse of as_primes)
atom res = 1
for i=1 to length(n) do
if n[i]!=0 then
res *= power(known_factors[i],n[i])
end if
end for
return res
end function
function as_primes(integer n)
-- eg as_primes(55) -> {5,11} -> indexes to known_factors
if n=1 then return {} end if
sequence pf = prime_factors(n,duplicates:=true)
sequence res = repeat(0,length(known_factors))
for i=1 to length(pf) do
integer k = find(pf[i],known_factors)
if k=0 then
known_factors = append(known_factors,pf[i])
res = append(res,1)
else
res[k] += 1
end if
end for
-- atom chk = combine_factors(res)
-- if chk!=n then ?9/0 end if
return res
end function
function parse(string s)
sequence res = split(s)
for i=1 to length(res) do
sequence sri = scanf(res[i],"%d/%d")
if length(sri)!=1 then ?9/0 end if -- oops!
integer {{n,d}} = sri
res[i] = {as_primes(n),as_primes(d)}
end for
return res
end function
function step(sequence pgm, sequence n)
for pc=1 to length(pgm) do
sequence d = pgm[pc][2], res = n
-- sequence d = pgm[pc][2], res = deep_copy(n) -- (see timing note)
bool ok = true
for f=1 to length(d) do
integer df = d[f]
if df!=0 then
if f>length(n) or df>n[f] then
ok = false
exit
end if
res[f] -= df
end if
end for
if ok then
n = pgm[pc][1]
integer zf = length(n)-length(res)
if zf>0 then res &= repeat(0,zf) end if
for i=1 to length(n) do
res[i] += n[i]
end for
return res
end if
end for
return 0
end function
constant src = "17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1"
sequence pgm = parse(src)
object n = as_primes(2)
sequence res = {}
for i=1 to steps do
n = step(pgm,n)
if n=0 then exit end if
res = append(res,combine_factors(n))
end for
printf(1,"first %d results: %v\n",{steps,res})
n = as_primes(2)
integer k2 = find(2,known_factors)
sequence n0 = repeat(0,length(known_factors))
res = {}
integer iteration = 1
atom t0 = time()
while length(res)<primes do
n = step(pgm,n)
if n=0 then exit end if
n0[k2] = n[k2]
if n=n0 then -- (ie all non-2 are 0)
-- and the prime itself is ready and waiting...
res = append(res,n[k2])
end if
iteration += 1
end while
printf(1,"first %d primes: %v\n",{primes,res})
printf(1,"%,d iterations in %s\n",{iteration,elapsed(time()-t0)})