lucky.rkt

#|
Lucky numbers implementation.  See
- https://en.wikipedia.org/wiki/Lucky_number
- https://oeis.org/A000959

Heavily commented to help describe this to a Racket beginner. :)
|#
#lang racket

(define (lucky N)
  (let loop ([ls (range 1 (add1 N))]    ; Build the initial list of (0,N]
             [n 2])                     ; Start with 2
    (define first-kept #f)              ; Initialize this for use later.
    ;; Build the new list to replace ls.
    (define sieved
      (for/list ([m (in-list ls)]       ; Map over all the values in ls.
                 [pos (in-naturals 1)]  ; Get position, e.g. third elem -> 3
                 #:unless (zero? (modulo pos n))) ; Filter out nth elements
        ;; Save the first element that is greater than n.  This will be the
        ;; first element saved from the deletion.
        (when (and (not first-kept) (> m n))
          (set! first-kept m))
        m))
    (if first-kept
        ;; When an element was saved, there is more sieving to do.
        (loop sieved first-kept)
        ;; Otherwise work is complete.
        ls)))

(module+ test
  (require rackunit)
  (check-equal? (lucky 30)
                '(1 3 7 9 13 15 21 25))
  (check-equal? (lucky 100)
                '(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99)))