461 PurelyFunctional.tv Newsletter

00 Primes in a number.md

Primes in a number

Another contrived math problem. This one I think is actually pretty hard. It's got detecting primes, string manipulation, and combinations.

Your task is to write a function that takes an integer and finds all primes that are substrings of the decimal digits of that integer.

Examples

(find-primes 2) ;=> [2]
(find-primes 22) ;=> [2 2]
(find-primes 717) ;=> [7 7 17 71]
(find-primes 1) ;=> []
(find-primes 44) ;=> []

Notes:

• Return the primes in ascending order.
• If a prime appears more than once, it should be in the returned sequence that many times.

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn prime? [n]
  (and (< 1 n) (not-any? #(zero? (rem n %)) (range 2 n))))

(defn subseqs [s]
  (let [ls (inc (count s))]
    (for [b (range ls) e (range (inc b) ls)] (subs s b e))))

(defn find-primes [n]
  (sort (filter prime? (map read-string (subseqs (str n))))))

(defn prime? [n]
  (if (even? n)
    (= n 2)
    (and (> n 1)
         (let [sqrt (Math/sqrt n)]
           (loop [candidate 3]
             (cond (> candidate sqrt) true
                   (zero? (rem n candidate)) false
                   :else (recur (inc (inc candidate)))))))))


(defn find-primes [n]
  (let [digs (into () (comp (take-while pos?) (map #(rem % 10))) (iterate #(quot % 10) n))
        parts (reduce (fn [ps w] (into ps (partition w 1 digs)))
                      []
                      (range 1 (inc (count digs))))
        cands (map #(reduce (fn [r i] (+ (* 10 r) i)) 0 %) parts)]
    (sort (filter prime? cands))))

Transducer version. Use prime? from above.

(defn find-primes [n]
  (let [digs (into () (comp (take-while pos?) (map #(rem % 10))) (iterate #(quot % 10) n))]
    (transduce (comp (mapcat #(partition % 1 digs))
                     (map #(reduce (fn [r i] (+ (* 10 r) i)) 0 %))
                     (filter prime?))
               (completing conj! (comp sort persistent!))
               (transient [])
               (range 1 (inc (count digs))))))

Inspired by the other solutions, I see that parsing the substrings is faster than doing the math on partitions. Again, using prime? from my first example, here is my fastest solution.

(defn find-primes [n]
  (let [s (str n)
        c (inc (count s))]
    (->> (for [b (range c)
               e (range (inc b) c)]
           (Long/parseLong (subs s b e)))
         (filter prime?)
         sort)))

I just want to show that for have something more to offer.

(defn prime? [num]
  (and
    (not= 1 num)
    (every?
      (fn [each-num]
        (not= 0 (mod num each-num)))
      (range 2 (Math/ceil (Math/sqrt num))))))

(defn find-primes [num]
  (let [num-str (str num)]
    (sort (for [start (range (count num-str))
                end (range (inc start)
                           (inc (count num-str)))
                :let [maybe-p (Integer/parseInt (subs num-str start end))]
                :when (prime? maybe-p)]
            maybe-p))))

Sorry for the long-winded solution - will study the very concise and elegant examples above.
In trying for a speedup I used a sieve upfront, windowing for combining digits, and a sorted-in-place vector.

;; Utilities: a sorted-vector implementation
(defn insert-idx 
"Finds the insertion point for x in a sorted vector according to binary pred" 
  [xs x pred]
  (let [cmptor (comparator pred)]
    (loop [lo 0 hi (dec (count xs))]
      (if (> lo hi)
        lo 
        (let [mid (bit-shift-right (+ lo hi) 1)
              midv (nth xs mid)
              cmp (cmptor midv x)]
          (cond 
            (< cmp 0)
            (recur (inc mid) hi)
            (> cmp 0)
            (recur lo (dec mid))
            :else
            mid))))))

(defn sorted-conj 
  "xs is a sorted vector. Yields a new vector with remaining args conj'ed in the proper 
  location in increasing order."
  ([xs y & ys]
   (->> ys (cons y)
        (reduce (fn [sorted y]
                  (let [insert-loc (insert-idx sorted y <)]
                    (-> sorted (subvec 0 insert-loc)
                        (into [y])
                        (into (subvec sorted insert-loc (count sorted))))))
                xs))))

;; Translation b/w number and digits
(defn n->digs [n]
  (loop [n n acc ()]
    (let [[q r] [(quot n 10) (rem n 10)]]
      (if (zero? n)
        acc
        (recur (quot n 10) (conj acc r))))))

(defn digs->n [digs]
  (->> 1 
       (iterate (fn [pow] 
                  (* pow 10))) 
       (map #(* % %2) (reverse digs))
       (apply +)))

;; Primality detection
(defn sieve
  "Yields a map of integers upto and including n, of whether
  the key is a prime (value is :prime), or some product [mult base]
  where base is a prime."
 [n]
  (loop [sieve (sorted-map) x 2]
    (cond 
      (< n x)
      sieve
      (contains? sieve x)
      (recur sieve (inc x))
      :else
      (-> (into sieve (for [i (range 1 n)
                            :let [ix (* i x)]
                            :while (<= ix n)]
                        [ix [i x]]))
          (update x #(when-not (get % x) :prime))
          (recur (inc x))))))

(defn primes [sieve]
  (->> sieve 
       (keep (fn [[k v]] 
                 (when (= :prime v) 
                   k)))))

;; Combining digits
(defn windows 
  "Constructs a lazy seq of all contiguous subsequences of xs."
  [xs]
  (->> xs (iterate rest)
       (sequence (comp (take-while seq)
                       (mapcat #(reductions conj [] %))
                       (map seq)
                       (filter identity)))
       (cons ())
       lazy-seq))

(defn find-primes [n]
  (let [prime? (-> n sieve primes set) 
        digs (n->digs n)]
    (->> digs windows rest
         (reduce (fn [acc win]
                   (let [kand (digs->n win)]
                     (if (prime? kand)
                       (sorted-conj acc kand)
                       acc)))
                 []))))

(find-primes 2) ;=> [2]
(find-primes 22) ;=> [2 2]
(find-primes 717) ;=> [7 7 17 71]
(find-primes 1) ;=> []
(find-primes 44) ;=> []