Twin Primes, Cousin Primes, Sexy Primes, and Prime Triplets

Description of the problems

Today, I am going to write about primes. Specifically, certain progression of primes. Let us fix our notation: I am going to use $p_n$ for the $n$-th prime number.

A pair of consecutive primes $(p_n,p_{n+1})$ are called

twin primes if $p_{n+1} - p_n = 2$,
cousin primes if $p_{n+1} - p_n = 4$,
sexy primes if $p_{n+1} - p_n = 6$.

Three consecutive primes $(p_n, p_{n+1}, p_{n+2})$ are called a triplet if $p_{n+2} - p_n = 6$.

Today, I am going to write a clojure program that will give us these prime pairs and triples for the first few prime numbers.

An implementation in clojure

I am going to implement a lazy sequence of prime numbers and then we are going to filter it. First, I am going to need a function that returns the smallest prime number that comes after a given number.

(defn next-prime [n]
  (if (= n 2) 
      3
      (let [m (+ n 2)
            t (-> n Math/sqrt int (+ 2))]
          (if (some #(zero? (mod m %)) (range 2 t))
              (next-prime m)
              m))))

#'prep/next-prime

Let us test:

(into [] (map next-prime [2 3 5 119]))

[3 5 7 127]

Next, the lazy sequence of primes

(def primes (lazy-seq (iterate next-prime 2)))

#'prep/primes

Let us test:

(into [] (take 20 primes))

[2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71]

Next, the main engine:

(defn find-primes [n window-size gap]
  (->> primes
       (take n)
       (partition window-size 1)
       (filter (fn [xs] (= gap (- (last xs) (first xs)))))))

#'prep/find-primes

The code takes a window size. This is because I am going to use the same function to filter pairs as well as triples. I am also giving the gap size since we are going to check several gap sizes.

Let us start with twin primes:

(into [] (find-primes 200 2 2))

[(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) (1019 1021) (1031 1033) (1049 1051) (1061 1063) (1091 1093) (1151 1153)]

Next, cousin primes

(into [] (find-primes 200 2 4))

[(7 11) (13 17) (19 23) (37 41) (43 47) (67 71) (79 83) (97 101) (103 107) (109 113) (127 131) (163 167) (193 197) (223 227) (229 233) (277 281) (307 311) (313 317) (349 353) (379 383) (397 401) (439 443) (457 461) (463 467) (487 491) (499 503) (613 617) (643 647) (673 677) (739 743) (757 761) (769 773) (823 827) (853 857) (859 863) (877 881) (883 887) (907 911) (937 941) (967 971) (1009 1013) (1087 1091) (1093 1097) (1213 1217)]

Then sexy primes

(into [] (find-primes 200 2 6))

[(23 29) (31 37) (47 53) (53 59) (61 67) (73 79) (83 89) (131 137) (151 157) (157 163) (167 173) (173 179) (233 239) (251 257) (257 263) (263 269) (271 277) (331 337) (353 359) (367 373) (373 379) (383 389) (433 439) (443 449) (503 509) (541 547) (557 563) (563 569) (571 577) (587 593) (593 599) (601 607) (607 613) (647 653) (653 659) (677 683) (727 733) (733 739) (751 757) (941 947) (947 953) (971 977) (977 983) (991 997) (1013 1019) (1033 1039) (1063 1069) (1097 1103) (1103 1109) (1117 1123) (1123 1129) (1181 1187) (1187 1193) (1217 1223)]

And finally triplets

(into [] (find-primes 200 3 6))

[(5 7 11) (7 11 13) (11 13 17) (13 17 19) (17 19 23) (37 41 43) (41 43 47) (67 71 73) (97 101 103) (101 103 107) (103 107 109) (107 109 113) (191 193 197) (193 197 199) (223 227 229) (227 229 233) (277 281 283) (307 311 313) (311 313 317) (347 349 353) (457 461 463) (461 463 467) (613 617 619) (641 643 647) (821 823 827) (823 827 829) (853 857 859) (857 859 863) (877 881 883) (881 883 887) (1087 1091 1093) (1091 1093 1097)]