Discussion on: Write a program or script to find Lucky Numbers

[Josha von Gizycki]

As always: happy to provide a Clojure solution:

(defn luckies [n]
  (loop [working-set (range 1 (inc n))
         ln 2
         step 1]
    (if (< ln (count working-set))
      (let [new-ws (keep-indexed
                    (fn [ix item]
                      (when (not= 0 (mod (inc ix) ln)) item))
                    working-set)]
        (recur new-ws (nth new-ws step) (inc step)))
      (println (count working-set)))))

This is just a first draft, happy to have the running code in about half an hour. I bet there's a lot of room for improvements, it calculates the first million numbers in 147 seconds.

[Josha von Gizycki]

Got it down to still very slow 100 seconds by using the vec function on the sieved result to make it a vector instead of a linked list. This way the nth call inside the recur statement is way faster.

(defn luckies [n]
  (loop [working-set (range 1 (inc n))
         ln 2
         step 1]
    (if (< ln (count working-set))
      (let [new-ws (vec
                    (keep-indexed
                     (fn [ix item]
                       (when (not= 0 (mod (inc ix) ln)) item))
                     working-set))]
        (recur new-ws (nth new-ws step) (inc step)))
      (println (count working-set)))))