97 lines
2.5 KiB
Plaintext
97 lines
2.5 KiB
Plaintext
constant steps = 20,
|
|
primes = 20
|
|
|
|
sequence known_factors = {} -- nb: no specific order
|
|
|
|
function as_primes(integer n)
|
|
-- eg as_primes(55) -> {5,11} -> indexes to known_factors
|
|
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
|
|
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 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 step(sequence pgm, sequence n)
|
|
for pc=1 to length(pgm) do
|
|
sequence d = pgm[pc][2], res = n
|
|
bool ok = true
|
|
for f=1 to length(d) do
|
|
if d[f]!=0 then
|
|
if f>length(n) or d[f]>res[f] then
|
|
ok = false
|
|
exit
|
|
end if
|
|
res[f] -= d[f]
|
|
end if
|
|
end for
|
|
if ok then
|
|
n = pgm[pc][1]
|
|
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: %s\n",{steps,sprint(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: %s\n",{primes,sprint(res)})
|
|
printf(1,"%d iterations in %s\n",{iteration,elapsed(time()-t0)})
|