Prime Factorization With core.logic

It’s time for my first code kata, and on Colin’s suggestion, I’m starting with a classic: prime factorization. The problem description is simple: write a function that takes an integer n and returns a list of its prime factors in ascending order. That leaves lots of room for creativity, and in my few months at 8th Light, I’ve seen several interesting solutions, including Objective-C and Erlang. I’ve been meaning to learn Clojure’s core.logic library for a while, so I decided to come up with a logic programming solution.

If you haven’t yet checked out core.logic, there are a growing number of resources on the web. To get up to speed, I worked through David Nolen’s logic tutorial, the Magical Island of Kanren, the core.logic Primer, and a few chapters of The Reasoned Schemer. Hopefully, following along with my test cases will explain the subset of logic functions in my solution.

I’ll start with a basic speclj test setup:

core_spec.clj 
1
2
3

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

For the production code, I’ll start with core.logic and three functions from the finite domain namespace.

core.clj 
1
2
3

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

On to the tests! The declarative aspect of logic programming feels well-suited to a mathy problem like this. Instead of describing how to factorize, I’ll write a few definitions and let the logic engine handle the rest. The strategy I have in mind is the same simple one I learned in 8th grade algebra: start with a composite integer, and decompose it into a factor tree whose leaves are prime factors.

To start, I’ll define “factor pairs”: a vector of two integers that multiply to another. So, [2 3] is a factor pair of 6, [1 23] a factor pair of 23. Here’s the most general test I came up with:

core_spec.clj 
1
2
3
4
5
6
7
8
9

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should= '([_0 _1]) (factor-pairs 81))))

There’s a lot of syntax right off the bat, but this test isn’t as confusing as it might look. So far, I’ve found it easiest to understand logic programming as describing a set of constraints on a solution. This test describes the first constraint: factor pairs are vectors of two elements.

Here, _0 and _1 represent reified, unbound logic variables: symbolic representations of logic variables that can take on any value. (The numbers at the end indicate that they’re two different variables: _0 and _1 can take on different values). So this test simply describes the most general constraint: the factor-pairs function should take something as an argument and return a list of vectors of two things–any two things!.

Here’s a function that does just that:

core.clj 
1
2
3
4
5
6
7
8

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (== pair [factor1 factor2]))))

The run* function is the, uh, core of core.logic, used to set up problems for the logic engine to solve. It returns a list of all the solutions that match the constraints defined inside. The fresh form inside of run* is analogous to let: a way to declare local logic variables. The first two lines say “Find all the solutions where pair, factor1, and factor2 meet these constraints,” and the third describes the only constraint: “A pair is a vector of two elements, factor1 and factor2”.

Note that I’m ignoring the number argument! At this point (factor-pairs 81), (factor-pairs 72), and (factor-pairs 23) all return the same result. For now, calling this function factor-pairs is a little misleading, since it returns the equivalent of all possible pairs of two things. But now that the tests pass, we can add another constraint:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81))))

Here, I’ll describe the next constraint: factor pairs should only be defined between 2 and n. (Yes, a pair like [1 23] is technically a pair of factors, but it’s not very useful for my prime factorization purposes).

I may be open to a little TDD legal trouble with this test update, but I’ve added a couple helper functions to keep the tests as declarative as possible. Should-all asserts that a predicate matches for every element in a collection. In-interval? tests whether a pair is in the range low to high, inclusive. Hopefully, Two-elements? explains itself. Since factor-pairs will now return a list with many elements, I’ve generalized the original test.

It only takes one line to add the extra constraint:

core.clj 
1
2
3
4
5
6
7
8
9

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (== pair [factor1 factor2]))))

The new line declares that factor1 and factor2 must both be in the finite interval 2-number. Factor-pairs is still something of a misnomer: it now returns the Cartesian product of all numbers 2-number. But it’s a step closer. I’ll add one more constraint:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (fn [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

Factor pairs contain two elements between 2 and n that equal n when multiplied. That’s a complete definition of a factor pair, and adding the third constraint completes the function:

core.clj 
1
2
3
4
5
6
7
8
9
10

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (eq (= number (* factor1 factor2)))
               (== pair [factor1 factor2]))))

Here, eq converts an arithmetic expression into a constraint, as long as the logic variables are defined over a finite domain. So the final constraint simply says number must equal factor1 times factor2. If you’re not convinced by the tests, try it in a REPL:

1
2
3
4
5
6
7
8

user=> (factor-pairs 81)
([3 27] [9 9] [27 3])

user=> (factor-pairs 148)
([2 74] [4 37] [37 4] [74 2])

user=> (factor-pairs 23)
()

There are some properties here that I’ll use to my advantage. First, by default, factor pairs are ordered by the first factor, ascending. Second, I’ve already created an implicit definition of primes: numbers that return an empty list of factor pairs. I’ll add it as a test for clarity:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (fn [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

(describe "Prime numbers"
          (they "have no factor pairs"
                (should= '() (factor-pairs 23))))

Now I’ll move on to decomposition. If you’ve watched a prime factors kata before, you’ve probably seen a few standard tests: start by testing 1, then 2, then 3, and then composites. Here’s where something similar comes in:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (fn [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

(describe "Prime numbers"
          (they "have no factor pairs"
                (should= '() (factor-pairs 23))))

(describe "Decomposition"
          (it "decomposes 1 into itself"
              (should= '(1) (decompose 1))))

Of course, it’s easy to pass this one:

core.clj 
1
2
3
4
5
6
7
8
9
10
11
12

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (eq (= number (* factor1 factor2)))
               (== pair [factor1 factor2]))))

(defn decompose [number] '(1))

I’ll make it a little harder with the next bit of the definition. Primes should decompose into themselves:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (fn [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

(describe "Prime numbers"
          (they "have no factor pairs"
                (should= '() (factor-pairs 23))))

(describe "Decomposition"
          (it "decomposes 1 into itself"
              (should= '(1) (decompose 1)))
          (it "decomposes primes into themselves"
              (should= '(2) (decompose 2))
              (should= '(3) (decompose 3))
              (should= '(17) (decompose 17))
              (should= '(23) (decompose 23)))

I’ll get back to passing with a small tweak. Instead of returning '(1), decompose should check if a number has any factor pairs. If not, return the number.

core.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (eq (= number (* factor1 factor2)))
               (== pair [factor1 factor2]))))

(defn decompose [number]
  (let [factorpair (first (factor-pairs number))]
    (if (empty? factorpair) (list number))))

That’s the easy part, but what about composites? Well, two times a prime should certainly decompose to 2 and the prime:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (fn [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

(describe "Prime numbers"
          (they "have no factor pairs"
                (should= '() (factor-pairs 23))))

(describe "Decomposition"
          (it "decomposes 1 into itself"
              (should= '(1) (decompose 1)))
          (it "decomposes primes into themselves"
              (should= '(2) (decompose 2))
              (should= '(3) (decompose 3))
              (should= '(17) (decompose 17))
              (should= '(23) (decompose 23)))
          (it "decomposes 2 * a prime into 2 and itself"
              (should= '(2 2) (decompose 4))))

Decompose already includes the base case at the bottom of of the prime factor tree. If I feed it a number that’s not prime, it should decompose its factors until it runs into a prime. Concatenating the results should return a nice list of prime factors:

core.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(ns prime-factors.core
  (:require [clojure.core.logic :refer :all])
  (:require [clojure.core.logic.fd :refer [in interval eq]]))

(defn factor-pairs [number]
  (run* [pair]
        (fresh [factor1 factor2]
               (in factor1 factor2 (interval 2 number))
               (eq (= number (* factor1 factor2)))
               (== pair [factor1 factor2]))))

(defn decompose [number]
  (let [factorpair (first (factor-pairs number))]
    (if (empty? factorpair) (list number)
        (concat (decompose (first factorpair))
                (decompose (second factorpair))))))

And that’s it! Here’s a last set of test cases to confirm that it works:

core_spec.clj 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

(ns prime-factors.core-spec
  (:require [speclj.core :refer :all]
            [prime-factors.core :refer :all]))

(defmacro they [& args] `(it ~@args))

(defn should-all [predicate collection]
  (should (every? predicate collection)))

(defn in-interval? [low high]
  (fn [pair] (every? #(and (>= % low) (<= % high)) pair)))

(defn two-elements? [pair]
  (= 2 (count pair)))

(defn multiply-to? [n]
  (fn [[factor1 factor2]] (= n (* factor1 factor2))))

(describe "Factor pairs of n"
          (they "contain two elements"
                (should-all two-elements? (factor-pairs 81)))
          (they "are defined between 2 and n"
                (should-all (in-interval? 2 81) (factor-pairs 81)))
          (they "equal n when multiplied"
                (should-all (multiply-to? 81) (factor-pairs 81))))

(describe "Prime numbers"
          (they "have no factor pairs"
                (should= '() (factor-pairs 23))))

(describe "Decomposition"
          (it "decomposes 1 into itself"
              (should= '(1) (decompose 1)))
          (it "decomposes primes into themselves"
              (should= '(2) (decompose 2))
              (should= '(3) (decompose 3))
              (should= '(17) (decompose 17))
              (should= '(23) (decompose 23)))
          (it "decomposes 2 * a prime into 2 and itself"
              (should= '(2 2) (decompose 4)))
          (it "decomposes a composite into its prime factorization"
              (should= '(2 2 2) (decompose 8))
              (should= '(2 3 5) (decompose 30))
              (should= '(2 11 11) (decompose 242))
              (should= '(2 5 11 23) (decompose (* 23 5 2 11)))))

This isn’t the fastest way to find prime factors, but it’s no worse than the typical trial division solution to the prime factors kata. Using core.logic to declare definitions and constraints on the solution feels uniquely concise, expressive, and clear, and the exercise helped me get a more concrete handle on logic programming. You can find the code from this post (and a few earlier iterations) as a Gist here.

Comments