What year comes next in the following sequence?
1973 1979 1987 1993 1997 1999
(In reply to
Any Easier way ? by Syzygy)
UBASIC has a nxtprm function to find the next prime after a given number, and it's used in:
10 n=1972
20 for i = 1 to 8
30 n=nxtprm(n)
40 ? n
50 next
which finds
run
1973
1979
1987
1993
1997
1999
2003
2011
OK
The nxtprm function in UBASIC doesn't work beyond 2^32=4,294,967,296. A probabilistic primality test, derived from Donald Knuth's The Art of Computer Programming, is incorporated in this following program which finds the next prime after one googol:
10 point 80
20 x=10^100
30 y=fnNxprime(x)
40 print y
80 end
90 '
10000 fnOddfact(N)
10010 local K=0,P
10030 while N@2=0
10040 N=N\2
10050 K=K+1
10060 wend
10070 P=pack(N,K)
10080 return(P)
10090 '
10100 fnPrime(N)
10110 local I,X,J,Y,Q,K,T,Ans
10120 if N@2=0 then Ans=0:goto *EndPrime
10125 O=fnOddfact(N-1)
10130 Q=member(O,1)
10140 K=member(O,2)
10150 I=0
10160 repeat
10170 repeat
10180 X=fnLrand(N)
10190 until X>1
10200 J=0
10210 Y=modpow(X,Q,N)
10220 loop
10230 if or{and{J=0,Y=1},Y=N-1} then goto *ProbPrime
10240 if and{J>0,Y=1} then goto *NotPrime
10250 J=J+1
10260 if J=K then goto *NotPrime
10270 Y=(Y*Y)@N
10280 endloop
10290 *ProbPrime
10300 I=I+1
10310 until I>50
10320 Ans=1
10330 goto *EndPrime
10340 *NotPrime
10350 Ans=0
10360 *EndPrime
10370 return(Ans)
10380 '
10400 fnLrand(N)
10410 local R
10415 N=int(N)
10420 R=(int(rnd*10^(alen(N)+2)))@N
10430 return(R)
10440 '
10500 fnNxprime(X)
10510 if X@2=0 then X=X+1
10520 while fnPrime(X)=0
10530 X=X+2
10540 wend
10550 return(X)
10560 '
BTW it finds 10^100+267.
|
Posted by Charlie
on 2004-10-04 11:33:50 |