DEV Community

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

Collapse
 
joshavg profile image
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.

Collapse
 
joshavg profile image
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)))))