null.clj

;; Greatest common divisor of two integer numbers.
;; Examples;
;;
;;     (gcd 18 24) ;; 6
(defn gcd
  ""
  [a b]
  (loop [a a
         b b
         ]
    (cond
      (= b 0) a
      (< a b) (recur b a)
      :else (recur b
             (mod a b)))))


;; All number between 0 and n that are relatively prime with n.
;; Examples:
;;
;;    (relative-primes-below-n 6)
(defn relative-primes-below-n
  [n]
  (filter #(= (gcd n %) 1) (range n)))

;; Euler's phi function.
;; Number of relative primes between 0 and n for n.
;; Examples:
;;    (euler-phi 1) ;; 1
;;    (euler-phi 3) ;; 2
;;    (euler-phi 4) ;; 2
;;    (euler-phi 5) ;; 4
(defn euler-phi
  [n]
  (count (relative-primes-below-n n)))


;; Are a and b relatively prime?
(defn relative-prime?
  [a b]
  (= (gcd a b) 1))

;; Are \\( x_1, x_2, \cdots\\) pairwise relatively prime?
(defn pairwise-relative-prime?
  [xs]
  (let [relative-prime-with-rest? (fn [n ys]
                                    (loop [[y & rest-ys] ys]
                                      (if (relative-prime? n y)
                                        (recur rest-ys)
                                        false)))]
    (loop [[x & rest-xs] xs]
      (cond
        (empty? rest-xs) true
        (relative-prime-with-rest? x rest-xs) (recur rest-xs)
        :else false))))

(pairwise-relative-prime? [2 3 9])