Recamán Sequence (A005132)

Question

I'm going to screw around with visualizing Recamán's Sequence, but want to have a good sequence generator to generate the sequence before I start. I want to use a lazy generator for my actual application, but decided to make a strict version first since it will likely be simpler.

This is what I ended up with. It works (verified against the OEIS), but is quite verbose. I don't technically require seen, but doing constant linear searching over acc would likely be unacceptable. I'm just looking for broad suggestions on how this can be improved, because while it's fairly fast (it can find the first million numbers in ~2 seconds on my potato), it's rather ugly.

I know though that I can make use of transients here, but they're easy enough to add afterwards that that's not a big deal.

Any suggestions would be appreciated, because I feel like I'm missing something obvious.

(defn strict-recamans-sequence [max-n]
 (let [c-last #(get % (dec (count %)))]
 (loop [n 1
 seen #{}
 acc [0]]
 (if (> n max-n)
 acc
 (let [prev (c-last acc)
 back (- prev n)
 new-n (if (and (pos? back) (not (seen back)))
 back
 (+ prev n))]
 (recur (inc n) (conj seen new-n) (conj acc new-n)))))))

Answer 1

• I like the implementation of c-last as it produces an O(1) runtime with vectors (instead using the last function with O(n) runtime)
• However, you do not need c-last as you could also keep track of the last value in the loop bindings.
• If you do not need to eagerly compute the numbers in a vector, you can also use lazy sequences. It is not too difficult to write something in a lazy manner if you can already write it recursively.
• When replacing a loop with a recursive function call you can pass the loop's bindings as function parameters.

The result would look something like this.

(defn recaman []
 (letfn [(tail [previous n seen]
 (let [nx (if (and (> previous n) (not (seen (- previous n))))
 (- previous n)
 (+ previous n))]
 (cons nx (lazy-seq (tail nx (inc n) (conj seen nx))))))]
 (tail 0 0 #{})))

Calling (receman) will produce an infinite lazy sequence.

(take 100 (recaman))

• Carcigenicate: Thanks. I'm not great at writing lazy functions, so this is a big help.

Answer 2

If you want a lazy sequence, this may be a good example of using Python-style generator functions. An example:

(defn concat-gen ; concat a list of collections
 [& collections]
 (lazy-gen
 (doseq [curr-coll collections]
 (doseq [item curr-coll]
 (yield item)))))
(defn concat-gen-pair
 [& collections]
 (lazy-gen
 (doseq [curr-coll collections]
 (doseq [item curr-coll]
 (yield-all [item item])))))
(def c1 [1 2 3])
(def c2 [4 5 6])
(def c3 [7 8 9])
(is= [1 2 3 4 5 6 7 8 9] (concat-gen c1 c2 c3))
(is= [1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9] (concat-gen-pair c1 c2 c3))