Project Euler #49: Find 12-digit number concatenating a three terms sequence

First of all, project Euler has been a great help for me to learn Clojure. I tried for months trying to get web projects going but ended up frustrated with and struggling with tooling and libraries more than anything else. The code below gives the solution to Problem 49 in Project Euler:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

;; gen-primes Taken from https://stackoverflow.com/a/7625207/466694
(defn gen-primes "Generates an infinite, lazy sequence of prime numbers"
[]
(let [reinsert (fn [table x prime]
(update-in table [(+ prime x)] conj prime))]
(defn primes-step [table d]
(if-let [factors (get table d)]
(recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
(inc d))
(lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
(inc d))))))
(primes-step {} 2)))

(defn get-digits [num]
(->> [num []]
(iterate (fn [[num digits]]
(when (> num 0)
[(quot num 10) (conj digits (rem num 10))])))
(take-while some?)
(last)
(second)))

(defn are-permutations-of-each-other? [num1 num2]
(= (sort (get-digits num1)) (sort (get-digits num2))))

(let [four-digit-primes (->> (gen-primes)
(drop-while #(< % 1000))
(take-while #(< % 10000))
(apply sorted-set))]
(->> (for [i four-digit-primes
j four-digit-primes]
[i j])
(remove #(apply = %))
(filter #(apply are-permutations-of-each-other? %))
(filter (fn [[n1 n2]]
(let [mx (max n1 n2)
mn (min n1 n2)
diff (- mx mn)
next (+ mx diff)]
(and (< next 10000)
(four-digit-primes next)
(are-permutations-of-each-other? n1 next)))))
(map sort)
(distinct)
(map #(cons (+ (second %) (- (second %) (first %))) %))
(map sort)
(map #(map str %))
(map (partial apply str))
(second)))

For example, the last let expression is the result of tinkering for half an hour or so until I get the information I want out of it. Two questions:

1. I've found threading macros (especially ->>) a pure joy to work with. But, is there such a thing as a threading expression that is too long?
2. I know that this is throw-away coding, but what things can I do to improve this code to fit best practices? Are there things I'm doing wrong?

There's a few things that can be improved here:

First, I'm not sure if you neglected it here or if you actually aren't using it, but every file should start with a call to ns. This sets the namespace that the code following it will be in so other files can require it properly. If the code resides in src/my_thing/my_file, you would have

(ns my-thing.my-file)

At the top.

Second, unfortunately, that gen-primes function that you took from SO isn't a good example a proper practice. Unless you have an extraordinarily good reason, don't use def (and by extension, defn) to create a locally bound symbol. def creates globals that exist even once the function has returned:

(take 0 (gen-primes)) ; Run the function just so the inner defn happens
=> ()

(type primes-step)
=> irrelevant.cr2_original$gen_primes$primes_step__4224

Note how using using primes-step doesn't lead to an error. It's in scope!

To fix this, you could either just use let and define the function like was done with reinsert:

(defn gen-primes []
(let [reinsert (fn [table x prime]
(update-in table [(+ prime x)] conj prime))

primes-step (fn primes-step [table d]
(if-let [factors (get table d)]
(recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
(inc d))
(lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
(inc d))))))]

(primes-step {} 2)))

or, since you're only defining local functions, this is a good use-case for letfn:

(defn gen-primes []
(letfn [(reinsert [table x prime]
(update-in table [(+ prime x)] conj prime))

(primes-step [table d]
(if-let [factors (get table d)]
(recur (reduce #(reinsert %1 d %2) (dissoc table d) factors)
(inc d))
(lazy-seq (cons d (primes-step (assoc table (* d d) (list d))
(inc d))))))]

(primes-step {} 2)))

The latter doesn't have as much indentation, which is always nice.

This can be greatly simplified though if you're willing to sacrifice some performance for readability. Here's a version I threw together:

(defn gen-primes []
; Quick helper predicate
; A number is prime if there is not some number which is a factor of the number
(letfn [(prime? [n]
(not (some #(zero? (rem n %))
(range 2 (int (inc (Math/sqrt n)))))))]

; Drop the first two numbers from the range (because we don't care about 0 and 1
; Then filter all the primes
(filter prime? (drop 2 (range)))))

Rarely do you ever actually need to use lazy-seq explicitly. lazy-seq is the fundamental, low level building block for creating lazy sequences. Fortunately, many functions like filter already return a lazy sequence. In my function above, I'm just lazily filtering out all the non-primes from an infinite range of numbers, without ever explicitly using lazy-seq.

I realized after I posted this that this is actually a bit of an "apples and oranges" comparison. My version is a naïve brute-force approach which, while terse, is inefficient. Looking at the original code again, I'm assuming it's some kind of sieve that likely performs much better than my version.

get-digits can be greatly simplified as well if you just abuse strings here:

(defn my-get-digits [num]
(->> num
(str) ; Have str do most of the heavy lifting
(map str) ; Then turn each character back into a string so they can be parsed
(map #(Long/parseLong %))
(into '())))

They even perform identically. I was expecting mine to be slower, but it ended up being 0.1 µs faster:

(cc/quick-bench
(get-digits 192837465))
Evaluation count : 93972 in 6 samples of 15662 calls.
Execution time mean : 5.665620 µs
Execution time std-deviation : 872.894028 ns
Execution time lower quantile : 4.709602 µs ( 2.5%)
Execution time upper quantile : 6.504343 µs (97.5%)
=> nil

(cc/quick-bench
(my-get-digits 192837465))
Evaluation count : 130404 in 6 samples of 21734 calls.
Execution time mean : 5.508682 µs
Execution time std-deviation : 485.864725 ns
Execution time lower quantile : 4.669716 µs ( 2.5%)
Execution time upper quantile : 5.944096 µs (97.5%)

Where cc is an alias for the Criterium core module; a great benchmarking library.

Again, try to reuse existing constructs unless you have a good reason to get your hands dirty, or you really want the practice (although practicing reusing existing constructs is important as well).

are-permutations-of-each-other? has a little duplication, but is simple enough that that's not a big deal. If you wanted, you could use map to reduce some of the duplication. I made a var-arg function so it can accept any number of numbers to check. It's highly unnecessary, but doing so works well with use of map anyways, and doesn't change its usage. There's two nearly identical versions to choose from, depending on whether or not you want to use functions composition via comp, or just lazily map twice:

(defn are-permutations-of-each-other? [& nums]
(->> nums
(map (comp sort get-digits))
(apply =)))

(defn are-permutations-of-each-other? [& nums]
(->> nums
(map get-digits)
(map sort)
(apply =)))

This isn't a big deal, but in your main threading call that ties everything together, you have

(->> (for [i four-digit-primes
j four-digit-primes]
[i j])

(remove #(apply = %))
...)

There's certainly nothing wrong with this. I'll just point out that an alternative is just to apply filter directly in the for:

(->> (for [i four-digit-primes
j four-digit-primes
:when (not= i j)] ; Here
[i j])
...)

for can accept three kinds of keywords like that in its binding list. :when only adds to the list if the condition is true. It's like Python's if inside of list comprehensions.

Again in the main thread, you have:

(filter (fn [[n1 n2]]
(let [mx (max n1 n2)
mn (min n1 n2)
diff (- mx mn)
next (+ mx diff)]
(and (< next 10000)
(four-digit-primes next)
(are-permutations-of-each-other? n1 next)))))

At some point, you need to look at your anonymous function and break it off into it's own function. Not only does that neaten up the threading calls, it names the function so it's clearer what the code is actually doing.

A little down, you have

(map #(map str %))
(map (partial apply str))

Now, it doesn't matter which you choose, but consistency is nice. In the first line, you're using #(), and in the second, you're using partial; even though both can be done using either. I prefer #() unless I'm already inside a function macro since I find partial adds a lot of noise. Which you use doesn't matter though; just try to apply the same idea everywhere and be consistent in your style.

Finally, I stuck the whole main thread call into a -main function. Having code executing on the top level like that sucks if you're developing using a REPL. Every time I tried to load the function into the REPL to reflect a change I had made, the whole thing would run, which forced me to wait a couple seconds extra. In most cases, I prefer to stick everything inside functions so stuff only runs when I want it to.

Taking all that into consideration, here's what I ended up with:

(ns irrelevant.cr2-fixed)

(defn- gen-primes []
(let [prime? (fn [n] (not (some #(zero? (rem n %))
(range 2 (int (inc (Math/sqrt n)))))))]

; Drop the first two numbers from the range (because we don't care about 0 and 1
; Then filter all the primes
(filter prime? (drop 2 (range)))))

(defn- get-digits [num]
(->> num
(str) ; Have str do most of the heavy lifting
(map str) ; Then turn each character back into a string so they can be parsed
(map #(Long/parseLong %))
(into '())))

(defn- are-permutations-of-each-other? [& nums]
(->> nums
(map get-digits)
(map sort)
(apply =)))

(defn -main []
(let [four-digit-primes (->> (gen-primes)
(drop-while #(< % 1000))
(take-while #(< % 10000))
(apply sorted-set))

; Give this a better name. I have no idea what you'd want to call it.
filter-helper (fn [[n1 n2]]
(let [mx (max n1 n2)
mn (min n1 n2)
diff (- mx mn)
next (+ mx diff)]
(and (< next 10000)
(four-digit-primes next)
(are-permutations-of-each-other? n1 next))))]

(->> (for [i four-digit-primes
j four-digit-primes
:when (not= i j)]
[i j])
(filter #(apply are-permutations-of-each-other? %))
(filter filter-helper)
(map sort)
(distinct)
(map #(cons (+ (second %) (- (second %) (first %))) %))
(map sort)
(map #(map str %))
(map #(apply str %))
(second)
(println))))

(-main)
296962999629
=> nil

Hopefully that helps you out. Your code is actually quite good for someone learning the language. Keep it up!

• Thanks for all the advice. gen-primes is ugly yes, but I found that it performs well (Doesn't matter for this problem though). I will refactor it to use local fns as you suggested. I will start using Criterium, I'm currently simply using time. On a side note, this isn't the only time I ended up with a 10-12 line threading expression. Is this normal? For me, this follows naturally from immediate feedback. But, am I supposed to refactor the threading expression later somehow? Again, thanks for taking the time to write up a long and helpful answer. Nov 8 '18 at 15:58
• @nakiya Long threading macro calls aren't necessarily bad. I'd look at it like I would any other code: if the code is getting long in one function, that function is likely trying to do to much and should be broken up, or have some of its parts moved to a new function. When you break a long function up into smaller functions, you'll have smaller, more easily tested pieces to deal with which is always a win. I can't say I ever get ->> calls that end up being as long as you have here for the above reason. Once it's 5-6 lines long, I decide to break things up. Nov 8 '18 at 16:02

Three suggestions.

Carciginate repaired the syntax of your gen-primes algorithm. It can, though, be significantly simplified:

(defn gen-primes []
(letfn [(primes-step [table d]
(letfn [(reinsert [table prime]
(update table (+ prime d) conj prime))]
(if-let [factors (get table d)]
(recur (reduce reinsert (dissoc table d) factors)
(inc d))
(lazy-seq (cons d (primes-step
(assoc table (* d d) [d])
(inc d)))))))]
(primes-step {} 2)))

What are the changes?

• Make the reinsert function local to the primes-step function. This simplifies the reduce considerably.
• Replace the oversized update-in with the well-fitting update.
• Use vectors instead of a lists as values in the table. Small vectors are fast.

Clojure currently handles lexical closures badly, so though the first change makes the program clearer, it probably slows it down a bit too.

(defn get-digits [n]
(->> n
(iterate #(quot % 10))
(take-while pos?)
(map #(mod % 10))))

... which is simpler than yours or Carciginate's.

Down the line, you can probably speed this up using transducers:

(defn get-digits [n]
(sequence
(comp
(take-while pos?)
(map #(mod % 10)))
(iterate #(quot % 10) n)))
• Both take-while and map, given a single function argument, produce transducers.
• These are identical in form to those applied to a sequence by the ->> (thread last) macro, which has an implicit argument.
• The transducers combine by functional composition - comp.
• We use sequence to thus transform the initial sequence generated by iterate.

(defn are-permutations-of-each-other? [num1 num2]
(= (frequencies (get-digits num1)) (frequencies (get-digits num2))))

or

(defn are-permutations-of-each-other? [& nums]
(->> nums
(map (comp frequencies get-digits))
(apply =)))

... which might be respectively faster than yours and Cartiginate's. I haven't tested this.

• Thanks for the answer. If it's not too much trouble, can you give me a simple example of how to use transducers here? Apr 8 '19 at 2:29
• @nakiya Transducer example added. I got it wrong. Transducers do no good to the last example, but may speed up the first. Apr 9 '19 at 17:49