Clever Geek Handbook

Find n-tuples of all integers below m whose sum is prime

I'm looking at Clojure in an action book and there is code similar to the one below for a function that returns all pairs of numbers below m whose sum is prime (let's say prime):

(defn pairs-for-primes [m]
  (let [z (range 0 m)]
    (for [a z b z :when (prime? (+ a b))]
      (list a b))))

How can I generalize this to return n-tuples of all numbers below m whose sum is prime?

(defn all-ntuples-below [n m]
...
+3


source to share


2 answers


for

can be used for a kind of "special case" Cartesian product, where you know the set in advance at compile time. Since you don't really know the sets you want to get, you have to use the real Cartesian product function. For example clojure.math.combinatorics you can write

(defn pairs-for-primes [m n]
  (let [z (range 0 m)
        tuples (apply cartesian-product (repeat n z))]
    (filter #(prime? (apply + %)) tuples)))


But maybe your question is about how to implement the Cartesian product? It's not that hard, although the version below is not very impressive:

(defn cartesian-product [sets]
  (cond (empty? sets) (list (list))
        (not (next sets)) (map list (first sets))
        :else (for [x (first sets)
                    tuple (cartesian-product (rest sets))]
                (cons x tuple))))
+2


source


You can use take

to do this (since it pairs-for-primes

returns a sequence take

, this will calculate the number of items needed)



(defn all-ntuples-below [n m]
  (take n (pairs-for-primes m)))
+1


source






More articles:


All Articles