Monday 20 July 2015

Prime?

Today I found something called Wolstenholme’s theorem, which says: 
For a prime p > 3, the numerator of H(p-1) is divisible by p^2,
where H(n) =  1/1 + 1/2 + ... 1/n

Here's a function (in Clojure) to test whether a number is a prime based on the above:

(defn harmonic [n]
  (apply + (for [i (range 1 (inc n))] 
             (/ 1 i))))

(defn possibly-prime? [n]
  (if (< n 4)
    (or (= n 2) (= n 3))
    (-> n dec harmonic numerator (mod (* n n)) zero?)))

PS: Thank you Colin Wright for the corrections.

No comments:

Post a Comment