re: Write a program or script to find Lucky Numbers VIEW POST

FULL DISCUSSION
 

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.

 

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)))))
code of conduct - report abuse