## Twin primes

Q&A's, tips, howto's
cameyo
Posts: 102
Joined: Sun Mar 27, 2011 3:07 pm

### Twin primes

Two functions to calculate twin primes (pairs and pairs-i).

Code: Select all

``````(define (prime? n)
(if (even? n) nil
(= 1 (length (factor n)))))

(define (twin? n)
(if (and (prime? n) (prime? (+ n 2)))
(list n (+ n 2))
nil))

(twin? 9)
;-> nil
(twin? 881)
;-> (881 883)

(define (pairs a b)
(filter true? (map twin? (sequence a b))))

(pairs 3 1000)
;-> ((3 5) (5 7) (11 13) (17 19) (29 31) (41 43) (59 61) (71 73) (101 103) (107 109)
;->  (137 139) (149 151) (179 181) (191 193) (197 199) (227 229) (239 241) (269 271)
;->  (281 283) (311 313) (347 349) (419 421) (431 433) (461 463) (521 523) (569 571)
;->  (599 601) (617 619) (641 643) (659 661) (809 811) (821 823) (827 829) (857 859)
;->  (881 883))
(length (pairs 3 1000))
;-> 35
(time (pairs 3 2e7))
;-> 47479.457

==================================================

(define (pairs-i a b)
(local (idx found out)
(setq found nil)
(setq idx a)
; only the number 5 belongs to two pairs of twin prime numbers
(setq out '((3 5) (5 7)))
(while (< idx b)
(if (and (prime? idx) (prime? (+ idx 2)))
(begin
(push (list idx (+ idx 2)) out -1)
(setq found true))
)
(if found (++ idx 4) (++ idx 2))
(setq found nil)
)
out
)
)

(pairs-i 7 1000)
;-> ((3 5) (5 7) (11 13) (17 19) (29 31) (41 43) (59 61) (71 73) (101 103) (107 109)
;->  (137 139) (149 151) (179 181) (191 193) (197 199) (227 229) (239 241) (269 271)
;->  (281 283) (311 313) (347 349) (419 421) (431 433) (461 463) (521 523) (569 571)
;->  (599 601) (617 619) (641 643) (659 661) (809 811) (821 823) (827 829) (857 859)
;->  (881 883))
(length (pairs-i 7 1000))
;-> 35
(time (pairs-i 7 2e7))
;-> 43177.908``````
Post yours :-)

ralph.ronnquist
Posts: 216
Joined: Mon Jun 02, 2014 1:40 am
Location: Melbourne, Australia

### Re: Twin primes

Something like this, perhaps:

Code: Select all

``````(define (pairs-i a b)
(let ((out (list)) (x nil))
(for (y (if (odd? a) a (inc a)) b 2)
(if (1 (factor y)) (setf y nil) x (push (list x y) out -1))
(setf x y))
out))``````

cameyo
Posts: 102
Joined: Sun Mar 27, 2011 3:07 pm

### Re: Twin primes

Thanks ralph.ronnquist. This is faster than mine :-)
Have a nice day.

ralph.ronnquist
Posts: 216
Joined: Mon Jun 02, 2014 1:40 am
Location: Melbourne, Australia

### Re: Twin primes

You will gain a bit in speed for handling larger numbers by checking if the modulus of a prime product include any of the product primes. The code could be something like the following:

Code: Select all

``````(define (pairs-i1 a b)
(let ((out (list)) (x nil) (FX (* 2 3 5 7 11 13)) (M 0))
(for (y (if (odd? a) a (inc a)) b 2)
(if (if (< y FX) (1 (factor y))
(or (= (setf M (% y FX))) (if (factor M) (<= (\$it 0) 13)) (1 (factor y))))
(setf y nil)
x (push (list x y) out -1))
(setf x y))
out))``````
That example uses the prime product (* 2 3 5 7 11 13). For numbers greater than that, it checks if the modulus is a product of any of those primes, in which case the number as whole is divisible by that prime (and therefore not a prime itself). Notably, the factorization of the modulus is typically faster, and the end result is a faster filtering out of these. The speed up for handling large numbers is significant (~30%).