Proth Primes And Sierpinski Numbers

April 6, 2018

We begin with a function proth? that is #t if any of 3, 5, 7 or 17 identifies a prime, and #f otherwise:

(define (proth? n)
  (let loop ((a '(3 5 7 17)))
    (if (null? a) #f
      (if (not (= (jacobi (car a) n) -1)) (loop (cdr a))
        (if (= (expm (car a) (/ (- n 1) 2) n) (- n 1)) #t
          (loop (cdr a)))))))
(define (proth k)
  (do ((k2n (* k 2) (* k2n 2)) (n 1 (+ n 1))) (#f)
    (when (proth? (+ k2n 1)) (display n) (newline))))

And here’s the beginning of the output for k = 12909:

> (proth 12909)
1
2
5
7
11
14
17
18
22
30
39
58
62
77
85
91
99
109
125
131
149
171
185
215
223
253
267
285
287
299
310
337
347
391
639
641
685
767
771
781
887
CTRL-C

Here we see a Sierpinski number:

> (proth 78557)
... wait forever ...

You can run the program at https://ideone.com/e6FnQS.

Advertisements

Pages: 1 2

One Response to “Proth Primes And Sierpinski Numbers”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: