- Hi All,

1) I know this is a moving target, but as people continue to

calculate pi (3.14...) to ever increasing number of decimal places

surely someone out there must be enumerating the function pi (The

number of primes less than n)

So my first question is

What is the largest number n such that pi(n) is known?

I don't mind that the answer will have changed by the time I read the

reply

If no one is willing to be specific an order of magnitude will do

(e.g 10^16)

2) The prime community concentrates on finding larger and larger

primes. I have a question dealing with smallest.

What is the smallest prp?

(By which I mean number known to be prp but beyond our current

skills/effort to prove prime (or composite)).

For Jon Perry's benefit (if practical) we could treat this as a game.

Someone supply a prp (whose primality is non-trivial to determine

(say a week of pII cpu time)) to which someone can answer with either

a smaller example or with proof of the numbers

primeness/compositeness thus eliminating it from contention.

Cheers

Ken - --- In primenumbers@yahoogroups.com, "Phil" <philiplouisbewig@...> wrote:
>

Well, its certainly a lot more calculation than simply recording

> I discussed the Baillie-Wagstaff primality checker at my blog

> <http://programmingpraxis.com/2010/01/26/primality-checking-revisited/>

> . Here's the latest version of source code, in Scheme, which differs

> slightly from the original entry; it's more than "a few lines" of code,

> but not too long:

> (define (prime? n) (letrec ( (expm (lambda (b e m) (let ((times

> (lambda (x y) (modulo (* x y) m)))) (cond ((zero? e) 1) ((even?

> e) (expm (times b b) (/ e 2) m)) (else (times b (expm (times b b)

> (/ (- e 1) 2) m))))))) (digits (lambda (n) (let loop ((n n) (ds

> '())) (if (zero? n) ds (loop (quotient n 2) (cons (modulo n 2)

> ds)))))) (isqrt (lambda (n) (let loop ((x n) (y (quotient (+ n

> 1) 2))) (if (<= 0 (- y x) 1) x (loop y (quotient (+ y (quotient n

> y)) 2)))))) (square? (lambda (n) (let ((n2 (isqrt n))) (= n (* n2

> n2))))) (jacobi (lambda (a n) (let loop ((a a) (n n))

> (cond ((= a 0) 0) ((= a 1) 1) ((= a 2) (case (modulo n 8)

> ((1 7) 1) ((3 5) -1))) ((even? a) (* (loop 2 n) (loop (/ a

> 2) n))) ((< n a) (loop (modulo a n) n)) ((and

> (= (modulo a 4) 3) (= (modulo n 4) 3)) (- (loop n a)))

> (else (loop n a)))))) (inverse (lambda (x m) (let loop ((a 1) (b

> 0) (g x) (u 0) (v 1) (w m)) (if (zero? w) (modulo a m)

> (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q

> v)) (- g (* q w)))))))) (strong-pseudo-prime? (lambda (n a) (let

> loop ((r 0) (s (- n 1))) (if (even? s) (loop (+ r 1) (/ s 2))

> (if (= (expm a s n) 1) #t (let loop ((r r) (s s))

> (cond ((zero? r) #f) ((= (expm a s n) (- n 1)) #t) (else

> (loop (- r 1) (* s 2)))))))))) (chain (lambda (m f g u v) (let

> loop ((ms (digits m)) (u u) (v v)) (cond ((null? ms) (values u

> v)) ((zero? (car ms)) (loop (cdr ms) (f u) (g u v)))

> (else (loop (cdr ms) (g u v) (f v))))))) (lucas-pseudo-prime? (lambda

> (n) (let loop ((a 11) (b 7)) (let ((d (- (* a a) (* 4 b))))

> (cond ((square? d) (loop (+ a 2) (+ b 1))) ((not (= (gcd

> n (* 2 a b d)) 1)) (loop (+ a 2) (+ b 2))) (else (let*

> ((x1 (modulo (- (* a a (inverse b n)) 2) n))

> (m (quotient (- n (jacobi d n)) 2)) (f

> (lambda (u) (modulo (- (* u u) 2) n))) (g

> (lambda (u v) (modulo (- (* u v) x1) n))))

> (let-values (((xm xm1) (chain m f g 2 x1)))

> (zero? (modulo (- (* x1 xm) (* 2 xm1)) n))))))))))) (if (not

> (integer? n)) (error 'prime? "must be integer") (if (< n 2) #f (if

> (even? n) (= n 2) (if (zero? (modulo n 3)) (= n 3) (and

> (strong-pseudo-prime? n 2) (strong-pseudo-prime? n 3)

> (lucas-pseudo-prime? n))))))))

>

>

a '1' or '2' as each prime candidate in a long chain appears.

PARI can check primality of 19-20 digit integers at a rate of

about 8000/sec, according to Maximillian, so I would expect

Praxis to be a bit slower. My primitive pm2 hit 11500/sec when

I put it into a Lazarus FreePascal compiler on a Pentium4, so I

feel it has potential. I would have to seriously upgrade my

programming skills to see how far the idea can really go

however. Somebody please shoot it down - my brain hurts!

Its pretty easy to check out even if Pascal is not your bag.

Just download Lazarus and put the program from my Primemine2

posting in the source editor starting at the line 'type ='.

Piece of cake.

Aldrich