Sz\303\241m\303\255t\303\263g\303\251pes sz\303\241melm\303\251letJ\303\241rai AntalEzek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak1. A pr\303\255mek eloszl\303\241sa, szit\303\241l\303\241srestart; with(numtheory);1.1. A pr\303\255msz\303\241mt\303\251tel.[i$i=1..20]; evalf(map(i->log[2](mersenne([i])+1),%));primeprod:=proc(n) local p,i;
p:=1;
for i from 2 to n do if isprime(i) then p:=p*i fi od;
p,log[2.](p);
end;primeprod(16);primeprod(32);primeprod(64);primeprod(128);primeprod(256);primeprod(512);primeprod(1024);primeprod(2048);pd16:=1/ln(2.)/16; # approximate density of primes <=16 bitp16:=2.^16/ln(2.)/16; # approximate number of primes <=16 bitpd32:=1/ln(2.)/32; # approximate density of primes <=32 bitp32:=2.^32/ln(2.)/32; # approximate number of primes <=32 bitpd35:=1/ln(2.)/35; # approximate density of primes <=35 bitp35:=2.^35/ln(2.)/35; # approximate number of primes <=35 bitpd40:=1/ln(2.)/40; # approximate density of primes <=40 bitp40:=2.^40/ln(2.)/40; # approximate number of primes <=40 bitpd50:=1/ln(2.)/50; # approximate density of primes <=50 bitp50:=2.^50/ln(2.)/50; # approximate number of primes <=50 bitpd64:=1/ln(2.)/64; # approximate density of primes <=64 bitp64:=2.^64/ln(2.)/64; # approximate number of primes <=64 bit1.2. K\303\251rd\303\251s: zeta gy\303\266kei.1.3. K\303\251rd\303\251s: \317\200(x).1.4. Ikerpr\303\255mek.1.5. K\303\251rd\303\251s: \317\200_2(x)1.6. K\303\251rd\303\251s: az ikerpr\303\255mek reciprokainak \303\266sszege.1.7. Sejt\303\251s.#
# This procedure approximate Cs calculating the product
# for primes below x.
#
Cs:=proc(s::posint,x::posint) local P,p;
P:=1.; p:=nextprime(s);
while p<x do P:=P*(1-s/p)/(1-1/p)^s; p:=nextprime(p) od;
P end;Cs(2,10); Cs(2,100); Cs(2,1000); Cs(2,10000); Cs(2,100000);
Cs2:=Cs(2,1000000);Cs(3,10); Cs(3,100); Cs(3,1000); Cs(3,10000); Cs(3,100000);
Cs3:=Cs(3,1000000);Cs(4,10); Cs(4,100); Cs(4,1000); Cs(4,10000); Cs(4,100000);
Cs4:=Cs(4,1000000);Cs(5,10); Cs(5,100); Cs(5,1000); Cs(5,10000); Cs(5,100000);
Cs5:=Cs(5,1000000);Cs(6,10); Cs(6,100); Cs(6,1000); Cs(6,10000); Cs(6,100000);
Cs6:=Cs(6,1000000);Cs(7,10); Cs(7,100); Cs(7,1000); Cs(7,10000); Cs(7,100000);
Cs7:=Cs(7,1000000);Cs(8,10); Cs(8,100); Cs(8,1000); Cs(8,10000); Cs(8,100000);
Cs8:=Cs(8,1000000);evalf(9*exp(-2*gamma)*Cs(3,10));
evalf(9*exp(-2*gamma)*Cs(3,100));
evalf(9*exp(-2*gamma)*Cs(3,1000));
evalf(9*exp(-2*gamma)*Cs(3,10000));
evalf(9*exp(-2*gamma)*Cs(3,100000));
evalf(9*exp(-2*gamma)*Cs(3,1000000));1.8. P\303\251lda.# Twin prime, oldf1:=h->(3.+30*h)*2.^38880.-1;
f2:=f1+2; f2(1);
g:=h->1/ln(f1(h))/ln(f2(h));H:=2.^27; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2:=C2*(1-1/3)^2/(1-2/3)*(1-1/5)^2/(1-2/5)/(1-1/2)^2/(1-1/3)^2/(1-1/5)^2;%%*20*Cs2;f1:=h->(5775.+30030*h)*2.^171960.-1;
f2:=f1+2; f2(1);
g:=h->1/ln(f1(h))/ln(f2(h));H:=2.^35; H/6*(g(0)+4*g(H/2)+g(H));C2*(1-1/3)^2/(1-2/3)*(1-1/5)^2/(1-2/5)*(1-1/7)^2/(1-2/7)*(1-1/11)^2/(1-2/11)*(1-1/13)^2/(1-2/13);Cf1f2:=%/(1-1/2)^2/(1-1/3)^2/(1-1/5)^2/(1-1/7)^2/(1-1/11)^2/(1-1/13)^2;%*%%%; subs(C2=Cs2,%);# Cunningham chain I, length 3f1:=h->(3.+78*h)*2.^(273*128)-1;
f2:=2*f1+1; f3:=2*f2+1; f3(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h));H:=2.^40; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3:=C3/(1-1/2)^3/(1-1/3)^3*(1-1/13)^3/(1-3/13);%*%%; subs(C3=Cs3,%); HCCI3:=H/%;# Cunningham chain I, length 4f1:=h->(375.+390*h)*2.^(77*128)-1;
f2:=2*f1+1; f3:=2*f2+1; f4:=2*f3+1; f4(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h));H:=2.^47; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4:=C4*(1-1/2)/(1-1/2)^4*(1-2/3)/(1-1/3)^4*(1-3/7)/(1-4/7)*(1-1/5)^4/(1-4/5)*(1-1/13)^4/(1-4/13);%*%%; subs(C4=Cs4,%); HCCI4:=H/%;# Cunningham chain I, length 5f1:=h->(255.+390*h)*2.^(32*128)-1;
f2:=2*f1+1; f3:=2*f2+1; f4:=2*f3+1; f5:=2*f4+1; f5(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h))/ln(f5(h));H:=2.^54; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4f5:=C5*(1-1/2)/(1-1/2)^5*(1-2/3)/(1-1/3)^5*(1-4/5)/(1-1/5)^5*(1-2/7)/(1-4/7)*(1-1/13)^5/(1-5/13)*(1-7/17)/(1-5/17);%*%%; subs(C5=Cs5,%); HCCI5:=H/%;# Cunningham chain I, length 6f1:=h->(375.+390*h)*2.^(29*64)-1;
f2:=2*f1+1; f3:=2*f2+1; f4:=2*f3+1; f5:=2*f4+1; f6:=2*f4+1; f6(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h))/ln(f5(h))/ln(f6(h));H:=2.^60; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4f5f6:=C6*(1-1/2)/(1-1/2)^6*(1-2/3)/(1-1/3)^6*(1-4/5)/(1-1/5)^6*(1-1/7)/(1-4/7)*(1-1/13)^6/(1-6/13)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);%*%%; subs(C6=Cs6,%); HCCI6:=H/%;# Cunningham chain I, length 6f1:=h->(375.+2*3*5*7*11*13*17*19*23*29*31*37*41*47*53*59*61*67*h)*2.^(29*64)-1;
f2:=2*f1+1; f3:=2*f2+1; f4:=2*f3+1; f5:=2*f4+1; f6:=2*f4+1; f6(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h))/ln(f5(h))/ln(f6(h));H:=2.^60; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4f5f6:=C6*(1-1/2)/(1-1/2)^6*(1-2/3)/(1-1/3)^6*(1-4/5)/(1-1/5)^6*(1-1/7)/(1-4/7)*(1-1/13)^6/(1-6/13)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);%*%%; subs(C6=Cs6,%); HCCI61:=H/%;# Cunnigham chain II, length 2 + twinprimef1:=h->(5775.+30030*h)*2.^(1983*128)-1;
f2:=f1+2; f3:=2*f2-1; f3(1);
g:=h->1/ln(f1(h))/ln(f3(h));H:=2.^35; H/6*(g(0)+4*g(H/2)+g(H));C2*(1-1/3)^2/(1-2/3)*(1-1/5)^2/(1-2/5)*(1-1/7)^2/(1-2/7)*(1-1/11)^2/(1-2/11)*(1-1/13)^2/(1-2/13);Cf1f3:=%/(1-1/2)^2/(1-1/3)^2/(1-1/5)^2/(1-1/7)^2/(1-1/11)^2/(1-1/13)^2;%*%%%; subs(C2=Cs2,%);# Cunningham chain II, length 3f1:=h->(3.+6*h)*2.^(247*128)+1;
f2:=2*f1-1; f3:=2*f2-1; f3(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h));H:=2.^43; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3:=C3*(1-1/2)/(1-1/2)^3*(1-2/3)/(1-1/3)^3;%*%%; subs(C3=Cs3,%); HCCII3:=H/%;# Cunningham chain II, length 4f1:=h->(15.+30*h)*2.^(61*128)+1;
f2:=2*f1-1; f3:=2*f2-1; f4:=2*f3-1; f4(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h));H:=2.^49; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4:=C4*(1-1/2)/(1-1/2)^4*(1-2/3)/(1-1/3)^4*(1-4/5)/(1-1/5)^4*(1-3/7)/(1-4/7);%*%%; subs(C4=Cs4,%); HCCII4:=H/%;# Cunningham chain II, length 5f1:=h->(15.+30*h)*2.^(30*128)+1;
f2:=2*f1-1; f3:=2*f2-1; f4:=2*f3-1; f5:=2*f4-1; f5(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h))/ln(f5(h));H:=2.^54; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4f5:=C5*(1-1/2)/(1-1/2)^5*(1-2/3)/(1-1/3)^5*(1-4/5)/(1-1/5)^5*(1-2/7)/(1-4/7);%*%%; subs(C5=Cs5,%); HCCII5:=H/%;# Cunningham chain II, length 6f1:=h->(15.+30*h)*2.^(29*64)+1;
f2:=2*f1-1; f3:=2*f2-1; f4:=2*f3-1; f5:=2*f4-1; f6:=2*f4-1; f6(1);
g:=h->1/ln(f1(h))/ln(f2(h))/ln(f3(h))/ln(f4(h))/ln(f5(h))/ln(f6(h));H:=2.^58; H/6*(g(0)+4*g(H/2)+g(H));Cf1f2f3f4f5f6:=C6*(1-1/2)/(1-1/2)^6*(1-2/3)/(1-1/3)^6*(1-4/5)/(1-1/5)^6*(1-1/7)/(1-4/7)*(1-5/31)/(1-6/31);%*%%; subs(C6=Cs6,%); HCCII6:=H/%;1.9. K\303\251rd\303\251s.1.10. Eratoszten\303\251sz szit\303\241ja.sieve:=proc(N::posint) local n,B,i,j;
n:=floor((N-1)/2);
B:=Array(0..n-1);
for j from 0 to n-1 do B[j]:=1 od;
j:=0;
while j<n do
while B[j]=0 do j:=j+1 od;
i:=2*j^2+6*j+3;
if i>=n then break fi;
while i<n do B[i]:=0; i:=i+2*j+3 od;
j:=j+1;
od; B; end;debug(sieve); sieve(21);undebug(sieve); sieve(10000);#
# This is a simple pretest for a number
# using gcd. If there is a true divisor
# below 1000 then the result is false else true.
#
pre:=proc(n::integer) local p;
p:=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
if n < 2 then false
elif has(p,n) then true
elif igcd(2305567963945518424753102147331756070,n) <> 1 then false
elif n < 10201 then true
elif igcd(\
84969694892334181105323399091873499659260625866489327366115454263422038932\
70769390909069477309509137509786917118668028861499333825097682386722983737\
96296306675767413112673657893644078815718696989373063311306647862044862494\
92573240226273954373636390387526081667586612559568346306972204475122988482\
22228550062683786342519960225996301315945644470064720696621750477244528915\
927867113,n) <> 1 then
false
else
true
fi end;#
# This simple routine do the the simple pretest for n+id, 0<=i<N.
# The result is the list of i's not find to be composite.
#
preseq:=proc(n,d,N) local i,L;
L:=[];
for i from 0 to N-1 do
if pre(n+i*d) then L:=[op(L),i]; fi;
od; L; end;Digits:=10000; n:=ceil(Pi*10^4999): L:=preseq(n,2,30000):1.11. Feladat.1.12. Modul\303\241ris inverz euklid\303\251szi algoritmussal.#
# Calculation of the greatest common
# divisor by the Euclidean algorithm.
#
eucgcd:=proc(x::integer,y::integer) local u,v,r;
u:=abs(x); v:=abs(y);
while v<>0 do r:=irem(u,v); u:=v; v:=r od;
u end;#
# Calculation of the modular inverse by the Euclidean
# algorithm using division.
#
modinvdiv:=proc(a::integer,m::integer) local x1,x2,x3,d1,d2,d3,q,p;
x1:=1; d1:=a; x2:=0; d2:=m; p:=0;
do
if d2=0 then
if p=0 then return [x1,d1]
elif x1=0 then return [x1,d1]
else return [m-x1,d1]
fi;
fi;
q:=iquo(d1,d2); d3:=d1-q*d2; x3:=x1+q*x2; p:=1-p;
x1:=x2; x2:=x3; d1:=d2; d2:=d3;
od; end;modinvdiv(13874,15543);1.13. Feladat.1.14. Modul\303\241ris inverz bin\303\241ris lnko algoritmussal.#
# Calculation of the greatest common
# divisor by the binary algorithm.
#
bingcd:=proc(x::integer,y::integer) local u,v,k,t;
u:=abs(x); v:=abs(y);
if u=0 then RETURN(v) fi;
if v=0 then RETURN(u) fi;
k:=0;
while type(u,even) and type(v,even) do k:=k+1; u:=u/2; v:=v/2 od;
if type(u,odd) then t:=-v else t:=u fi;
while t<>0 do
while type(t,even) do t:=t/2 od;
if t>0 then u:=t else v:=-t fi;
t:=u-v;
od; u*2^k end;1.15. Feladat.#
# Calculation of the modular inverse with respect to an
# odd modulus by the binary gcd algorithm.
#
oddmodinvbin:=proc(a::nonnegint,m::posint)
local x1,x2,x3,d1,d2,d3,p;
if not type(m,odd) then error "second argument have to be odd",m fi;
if m=1 then return [0,1] fi;
x1:=1; d1:=a mod m; x2:=m; d2:=m;
if type(d1,even) then x3:=0; d3:=m; p:=1 else x3:=1; d3:=d1; p:=0 fi;
while d3<>0 do
while type(d3,even) do d3:=d3/2;
if type(x3,even) then x3:=x3/2 else x3:=(x3+m)/2 fi;
od;
if p=0 then x1:=x3; d1:=d3 else x2:=m-x3; d2:=d3 fi;
if x1>=x2 then x3:=x1-x2 else x3:=m+x1-x2 fi;
if d1>=d2 then d3:=d1-d2; p:=0 else d3:=d2-d1; p:=1 fi;
od; [x1,d1] end;oddmodinvbin(13874,15543);trymodinvs:=proc(n) local i,a,m,b,d;
for i to n do a:=rand(); m:=rand();
if type(m,even) then m:=m+1; fi;
a:=a mod m;
d:=modinvdiv(a,m); b:=oddmodinvbin(a,m);
if d[1]*a-d[2]mod m<>0 or b[1]*a-b[2] mod m<>0 then print(a,m,d,b) fi;
od; end;trymodinvs(10);1.16. \303\201ltal\303\241nos szita.Digits:=10;1.17. Programoz\303\241si probl\303\251m\303\241k.#
# This procedure calculate the sum of the reciprocal
# of primes up to x and compare with ln(ln(x)).
#
sumprimerec:=proc(x) local s,p,i;
s:=0.; p:=2;
while p<x do
s:=evalf(s+1/p); p:=nextprime(p)
od; [s,evalf(s-ln(ln(x)))] end;sumprimerec(10); sumprimerec(100); sumprimerec(1000); sumprimerec(10000); sumprimerec(100000); sumprimerec(1000000);1.18. A szit\303\241l\303\241s d\303\272s\303\255t\303\263 hat\303\241sa.#
# This procedure calculate the factor qsAB.
#
qsAB:=proc(s::posint,A::posint,B::posint) local P,p;
P:=1.; p:=nextprime(A-1);
while p<B do P:=P*(1-s/p); p:=nextprime(p) od;
P end;
qsAB(1,1,100);B:=10: [qsAB(1,1,B),evalf(qsAB(1,1,B)-exp(-gamma)/ln(B))];
B:=100: [qsAB(1,1,B),evalf(qsAB(1,1,B)-exp(-gamma)/ln(B))];
B:=1000: [qsAB(1,1,B),evalf(qsAB(1,1,B)-exp(-gamma)/ln(B))];
B:=10000: [qsAB(1,1,B),evalf(qsAB(1,1,B)-exp(-gamma)/ln(B))];
B:=100000: [qsAB(1,1,B),evalf(qsAB(1,1,B)-exp(-gamma)/ln(B))];
B:=1000000: [qsAB(1,1,B),evalf(qsAB(1,1,B)-exp(-gamma)/ln(B))];1.19. P\303\251lda.qsAB(2,7,1000000);%*(ln(1000000.)/ln(44000.*2^25))^2;# Cunningham chain I, length 3f:=qsAB(3,16,64);f:=f*(1-3/5)*(1-3/7)*(1-3/11);H:=HCCI3; H/8; H*f; 2*%;P:=20; f0:=qsAB(3,16,P); f0:=f0*(1-3/5)*(1-3/7)*(1-3/11);
HCCI30:=H*f0; %/8; 2*%%;
log[2.](H*f0); primeprod(P); op(2,[%])+%%;P:=72; f1:=qsAB(3,16,P); f1:=f1*(1-3/5)*(1-3/7)*(1-3/11);
HCCI31:=H*f1; %/8; 2*%%;
log[2.](H*f1); primeprod(P); op(2,[%])+%%;P:=125; f:=qsAB(3,16,P); f:=f*(1-3/5)*(1-3/7)*(1-3/11); H*f; %/8; 2*%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=165; f2:=qsAB(3,16,P); f2:=f2*(1-3/5)*(1-3/7)*(1-3/11);
HCCI32:=H*f2; %/8; 2*%;
log[2.](H*f2); primeprod(P); op(2,[%])+%%;f10:=qsAB(3,16,2^16); f10:=f10*(1-3/5)*(1-3/7)*(1-3/11); H*f10; 2*%;f13:=f10*(16/19)^3; H*f13; 2*%;f15:=f13*(19/21)^3; H*f15; 2*%;f18:=f15*(21/24)^3; H*f18; 2*%;f26:=f18*(24/32)^3; H*f26; 2*%;f29:=f26*(32/35)^3; H*f26; 2*%;f34:=f29*(35/40)^3; H*f34; 2*%;f44:=f34*(40/50)^3; H*f44; 2*%;#64 bit multiplier
H:=HCCI30; %/8; 2*%%; P:=20.;150*p50/3.2/10^9; # 64 bit reciprocal modulo primes <= 50 bit, sec# density and number after sieve with <=16 bit primes
f10/f0; %*H;
# sieve events for <=16 bit primes
3*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f0; %*H;# sieve events for <=32 bit primes
3*H*ln(32./ln(P));# sieve events for <=50 bit primes
3*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#128 bit multiplier
H:=HCCI31; %/8; 2*%%; P:=72.;200*p50/3.2/10^9; # 128 bit reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f1; %*H;
# sieve events for <=16 bit primes
3*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f1; %*H;# sieve events for <=32 bit primes
3*H*ln(32./ln(P));# sieve events for <=50 bit primes
3*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#256 bit multiplier
H:=HCCI32; %/8; 2*%%; P:=165.;300*p50/3.2/10^9; # 256 bit reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f2; %*H;
# sieve events for <=16 bit primes
3*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f2; %*H;# sieve events for <=32 bit primes
3*H*ln(32./ln(P));# sieve events for <=50 bit primes
3*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in secH*f44/f2*300/8^2/1.352243653; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain I, length 4f:=qsAB(4,16,64);f:=f*(1-3/7)*(1-4/11);H:=HCCI4; H/8; H*f; 2*%;P:=16; f0:=qsAB(4,16,P); f0:=f0*(1-3/7)*(1-4/11);
HCCI40:=H*f0; %/8; 2*%%;
log[2.](H*f0); primeprod(P); op(2,[%])+%%;P:=65; f1:=qsAB(4,16,P); f1:=f1*(1-3/7)*(1-4/11);
HCCI41:=H*f1; %/8; 2*%%;
log[2.](H*f1); primeprod(P); op(2,[%])+%%;P:=112; f:=qsAB(4,16,P); f:=f*(1-3/7)*(1-4/11); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=162; f2:=qsAB(4,16,P); f2:=f2*(1-3/7)*(1-4/11);
HCCI42:=H*f2; %/8; 2*%%;
log[2.](H*f2); primeprod(P); op(2,[%])+%%;P:=352; f3:=qsAB(4,16,P); f3:=f3*(1-3/7)*(1-4/11);
HCCI43:=H*f3; %/8; 2*%%;
log[2.](H*f3); primeprod(P); op(2,[%])+%%;f10:=qsAB(4,16,2^16);f10:=f10*(1-3/7)*(1-4/11); H*f10; 2*%;f13:=f10*(16/19)^4; H*f13; 2*%;f15:=f13*(19/21)^4; H*f15; 2*%;f18:=f18*(21/24)^4; H*f18; 2*%;f26:=f18*(24/32)^4; H*f26; 2*%;f29:=f26*(24/35)^4; H*f29; 2*%;f34:=f29*(35/40)^4; H*f34; 2*%;f44:=f34*(40/50)^4; H*f44; 2*%;#64 bit multiplier
H:=HCCI40; %/8; 2*%%; P:=16.;150*p50/3.2/10^9; # 64 bit reciprocal modulo primes <= 50 bit, sec# density and number after sieve with <=16 bit primes
f10/f0; %*H;
# sieve events for <=16 bit primes
4*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f0; %*H;# sieve events for <=32 bit primes
4*H*ln(32./ln(P));# sieve events for <=50 bit primes
4*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#128 bit multiplier
H:=HCCI41; %/8; 2*%%; P:=65.;200*p50/3.2/10^9; # 128 bit reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f1; %*H;
# sieve events for <=16 bit primes
4*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f1; %*H;# sieve events for <=32 bit primes
4*H*ln(32./ln(P));# sieve events for <=50 bit primes
4*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#256 bit multiplier
H:=HCCI42; %/8; 2*%%; P:=162.;300*p50/3.2/10^9; # 256 bit reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f2; %*H;
# sieve events for <=16 bit primes
4*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f2; %*H;# sieve events for <=32 bit primes
4*H*ln(32./ln(P));# sieve events for <=50 bit primes
4*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#512 bit multiplier
H:=HCCI43; %/8; 2*%%; P:=352.;500*p50/3.2/10^9; # 512 bit reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f3; %*H;
# sieve events for <=16 bit primes
4*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f3; %*H;# sieve events for <=32 bit primes
4*H*ln(32./ln(P));# sieve events for <=50 bit primes
4*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in secH*f44/f3*300/32^2/1.902321417; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain I, length 5f:=qsAB(5,18,64);f:=f*(1-3/7)*(1-5/11)*(1-11/17);H:=HCCI5; H/8; H*f; 2*%;P:=60; f1:=qsAB(5,18,P); f1:=f1*(1-3/7)*(1-5/11)*(1-11/17);
HCCI51:=H*f1; %/8; 2*%%;
log[2.](H*f1); primeprod(P); op(2,[%])+%%;P:=155; f2:=qsAB(5,18,P); f2:=f2*(1-3/7)*(1-5/11)*(1-11/17);
HCCI52:=H*f2; %/8; 2*%%;
log[2.](H*f2); primeprod(P); op(2,[%])+%%;P:=348; f3:=qsAB(5,18,P); f3:=f3*(1-3/7)*(1-5/11)*(1-11/17);
HCCI53:=H*f3; %/8; 2*%%;
log[2.](H*f3); primeprod(P); op(2,[%])+%%;P:=708; f4:=qsAB(5,18,P); f4:=f4*(1-3/7)*(1-5/11)*(1-11/17);
HCCI54:=H*f4; %/8; 2*%%;
log[2.](H*f4); primeprod(P); op(2,[%])+%%;P:=1445; f5:=qsAB(5,18,P); f5:=f5*(1-3/7)*(1-5/11)*(1-11/17);
HCCI55:=H*f5; %/8; 2*%%;
log[2.](H*f5); primeprod(P); op(2,[%])+%%;P:=2855; f6:=qsAB(5,18,P); f6:=f6*(1-3/7)*(1-5/11)*(1-11/17);
HCCI56:=H*f6; %/8; 2*%%;
log[2.](H*f6); primeprod(P); op(2,[%])+%%;f10:=qsAB(5,18,2^16);f10:=f10*(1-3/7)*(1-5/11)*(1-11/17); H*f10; 2*%;f13:=f10*(16/19)^5; H*f13; 2*%;f15:=f13*(19/21)^5; H*f15; 2*%;f18:=f15*(21/24)^5; H*f18; 2*%;f26:=f18*(24/32)^5; H*f26; 2*%;f29:=f26*(32/35)^5; H*f29; 2*%;f34:=f29*(35/40)^5; H*f34; 2*%;f44:=f34*(40/50)^5; H*f44; 2*%;#128 bit multiplier
H:=HCCI51; %/8; 2*%%; P:=60.;200*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f1; %*H;
# sieve events for <=16 bit primes
5*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f1; %*H;# sieve events for <=32 bit primes
5*H*ln(32./ln(P));# sieve events for <=50 bit primes
5*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#256 bit multiplier
H:=HCCI52; %/8; 2*%%; P:=155.;300*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f2; %*H;
# sieve events for <=16 bit primes
5*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f2; %*H;# sieve events for <=32 bit primes
5*H*ln(32./ln(P));# sieve events for <=50 bit primes
5*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#512 bit multiplier
H:=HCCI53; %/8; 2*%%; P:=348.;500*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f3; %*H;
# sieve events for <=16 bit primes
5*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f3; %*H;# sieve events for <=32 bit primes
5*H*ln(32./ln(P));# sieve events for <=50 bit primes
5*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#1024 bit multiplier
H:=HCCI54; %/8; 2*%%; P:=708.;900*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f4; %*H;
# sieve events for <=16 bit primes
5*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f4; %*H;# sieve events for <=32 bit primes
5*H*ln(32./ln(P));# sieve events for <=50 bit primes
5*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#2048 bit multiplier
H:=HCCI55; %/8; 2*%%; P:=1445.;1700*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f5; %*H;
# sieve events for <=16 bit primes
5*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f5; %*H;# sieve events for <=32 bit primes
5*H*ln(32./ln(P));# sieve events for <=50 bit primes
5*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#4096 bit multiplier
H:=HCCI56; %/8; 2*%%; P:=2855.;3300*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f6; %*H;
# sieve events for <=16 bit primes
5*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f6; %*H;# sieve events for <=32 bit primes
5*H*ln(32./ln(P));# sieve events for <=50 bit primes
5*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in secH*f44/f6*300/64^2/1.925834177; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain I, length 6f:=qsAB(6,18,64);f:=f*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
H:=HCCI6; H/8; H*f; 2*%;P:=18; f:=qsAB(6,18,P);
f:=f*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=58; f1:=qsAB(6,18,P);
f1:=f1*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI61:=H*f1; %/8; 2*%%;
log[2.](H*f1); primeprod(P); op(2,[%])+%%;P:=155; f2:=qsAB(6,18,P);
f2:=f2*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI62:=H*f2; %/8; 2*%%;
log[2.](H*f2); primeprod(P); op(2,[%])+%%;P:=345; f3:=qsAB(6,18,P);
f3:=f3*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI63:=H*f3; %/8; 2*%%;
log[2.](H*f3); primeprod(P); op(2,[%])+%%;P:=700; f4:=qsAB(6,18,P);
f4:=f4*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI64:=H*f4; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=1445; f5:=qsAB(6,18,P);
f5:=f5*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI65:=H*f5; %/8; 2*%%;
log[2.](H*f5); primeprod(P); op(2,[%])+%%;P:=2850; f6:=qsAB(6,18,P);
f6:=f6*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI66:=H*f6; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=5735; f7:=qsAB(6,18,P);
f7:=f7*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
HCCI67:=H*f7; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;f10:=qsAB(6,18,2^16);f10:=f10*(1-3/7)*(1-6/11)*(1-14/17)/(1-6/17)*(1-5/31)/(1-6/31);
H*f10; 2*%;f13:=f10*(16/19)^6; H*f13; 2*%;f15:=f13*(19/21)^6; H*f15; 2*%;f18:=f15*(21/24)^6; H*f18; 2*%;f26:=f18*(24/32)^6; H*f26; 2*%;f29:=f26*(32/35)^6; H*f29; 2*%;f34:=f29*(35/40)^6; H*f34; 2*%;f44:=f34*(40/50)^6; H*f44; 2*%;#128 bit multiplier
H:=HCCI61; %/8; 2*%%; P:=58.;200*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f1; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f1; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#256 bit multiplier
H:=HCCI62; %/8; 2*%%; P:=155.;300*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f2; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f2; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#512 bit multiplier
H:=HCCI63; %/8; 2*%%; P:=345.;500*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f3; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f3; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#1024 bit multiplier
H:=HCCI64; %/8; 2*%%; P:=700.;900*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f4; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f4; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#2048 bit multiplier
H:=HCCI65; %/8; 2*%%; P:=1445.;1700*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f5; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f5; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#4096 bit multiplier
H:=HCCI66; %/8; 2*%%; P:=2850.;3300*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f6; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f6; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in sec#8192 bit multiplier
H:=HCCI67; %/8; 2*%%; P:=5735.;6500*p50/3.2/10^9; # reciprocal modulo primes <=50 bit, sec# density and number after sieve with <=16 bit primes
f10/f7; %*H;
# sieve events for <=16 bit primes
6*H*ln(16./ln(P));# density and number after sieve with <=32 bit primes
f26/f7; %*H;# sieve events for <=32 bit primes
6*H*ln(32./ln(P));# sieve events for <=50 bit primes
6*H*ln(50./ln(P));%/0.8/10^9; # total sieve time in secH*f44/f7*300/128^2/2.373951103; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain II, length 2 + twinprimeqsAB(2,16,1000000);q2:=%*(ln(1000000.)/(50*ln(2.)))^2;qsAB(3,16,1000000);q3:=%*(ln(1000000.)/(50*ln(2.)))^3;expval:=29.62739122*q3/q2; # Expected number of twins/CullensH:=2.^35; q3*H*260/expval; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain II, length 3f:=qsAB(3,4,64); H:=2.^43; H/8; H*f; 2*%;P:=20; f:=qsAB(3,4,P); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=72; f:=qsAB(3,4,P); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=165; f:=qsAB(3,4,P); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=358; f:=qsAB(3,4,P); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;f:=qsAB(3,4,2^19); H*f; 2*%;f:=f*(19/21)^3; H*f; 2*%;f:=f*(21/24)^3; H*f; 2*%;f:=f*(24/35)^3; H*f; 2*%;f:=f*(35/40)^3; H*f; 2*%;f:=f*(40/50)^3; H*f; 2*%;H*f*300/16^2/2.380149958; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain II, length 4f:=qsAB(4,6,64); f:=f*(1-3/7)/(1-4/7); H:=2.^49; H/8; H*f; 2*%;P:=16; f:=qsAB(4,6,P); f:=f*(1-3/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=70; f:=qsAB(4,6,P); f:=f*(1-3/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=165; f:=qsAB(4,6,P); f:=f*(1-3/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=352; f:=qsAB(4,6,P); f:=f*(1-3/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=718; f:=qsAB(4,6,P); f:=f*(1-3/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;f:=qsAB(4,6,2^19); f:=f*(1-3/7)/(1-4/7); H*f; 2*%;f:=f*(19/21)^4; H*f; 2*%;f:=f*(21/24)^4; H*f; 2*%;f:=f*(24/35)^4; H*f; 2*%;f:=f*(35/40)^4; H*f; 2*%;f:=f*(40/50)^4; H*f; 2*%;H*f*300/64^2/1.731884327; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain II, length 5f:=qsAB(5,6,64); f:=f*(1-2/7)/(1-4/7); H:=2.^54; H/8; H*f; 2*%;P:=12; f:=qsAB(5,6,P); f:=f*(1-2/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=65; f:=qsAB(5,6,P); f:=f*(1-2/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=162; f:=qsAB(5,6,P); f:=f*(1-2/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=348; f:=qsAB(5,6,P); f:=f*(1-2/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=708; f:=qsAB(5,6,P); f:=f*(1-2/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;P:=1445; f:=qsAB(5,6,P); f:=f*(1-2/7)/(1-4/7); H*f; %/8; 2*%%;
log[2.](H*f); primeprod(P); op(2,[%])+%%;f:=qsAB(5,6,2^19); f:=f*(1-2/7)/(1-4/7); H*f; 2*%;f:=f*(19/21)^5; H*f; 2*%;f:=f*(21/24)^5; H*f; 2*%;f:=f*(24/35)^5; H*f; 2*%;f:=f*(35/40)^5; H*f; 2*%;f:=f*(40/50)^5; H*f; 2*%;H*f*300/128^2/2.132358865; # SPU time in sec%/24/3600/420; # time for all SPU in days# Cunningham chain II, length 6f:=qsAB(6,6,64); f:=f*(1-1/7)/(1-4/7)*(1-25/31)/(1-26/31);
H:=2.^58; H/8; H*f; 2*%;f:=qsAB(6,6,68); f:=f*(1-1/7)/(1-4/7)*(1-25/31)/(1-26/31); H*f; 2*%;f:=qsAB(6,6,2^19); f:=f*(1-1/7)/(1-4/7)*(1-25/31)/(1-26/31); H*f; 2*%;f:=f*(19/21)^6; H*f; 2*%;f:=f*(21/24)^6; H*f; 2*%;f:=f*(24/35)^6; H*f; 2*%;f:=f*(35/40)^6; H*f; 2*%;f:=f*(40/50)^6; H*f; 2*%;H*f*300/256^2/1.927056039; # SPU time in sec%/24/3600/420; # time for all SPU in days1.20. K\303\251rd\303\251s.#
# This triviality makes a list of the differences
# between odd primes up to a given limit. The
# half of the differences is stored. The first
# item is 1=(5-3)/2.
#
primes:=proc(N) local p,pp,L;
L:=[]; pp:=3;
for p from 5 while p<=N by 2 do
if isprime(p) then L:=[op(L),(p-pp)/2]; pp:=p; fi;
od; L end;L:=primes(1000);1.21. K\303\251rd\303\251s.save(L,"primediffs"); read("primediffs");1.22. K\303\251rd\303\251s.1.23. K\303\251rd\303\251s.1.24. K\303\251rd\303\251s.1.25. K\303\251rd\303\251s.2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263dszerek3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\263dszerekLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn4. Lucas-sorozatok5. Alkalmaz\303\241sok 6. Sz\303\241mok \303\251s polinomok7. Gyors Fourier-transzform\303\241ci\303\2638. Elliptikus f\303\274ggv\303\251nyek9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251ken10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251kkel11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel12. Polinomfaktoriz\303\241l\303\241s13. Az AKS-teszt14. A szita m\303\263dszerek alapjai15. Sz\303\241mtest szita16. Vegyes probl\303\251m\303\241kLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn