PasteRack.org
Paste # 58289
2021-10-13 13:52:44

Forked from paste # 91167.

Fork as a new paste.

Paste viewed 692 times.


Embed:

lucky.rkt

  1. #lang racket
  2.  
  3. #|
  4. Lucky numbers implementation.  See
  5. - https://en.wikipedia.org/wiki/Lucky_number
  6. - https://oeis.org/A000959
  7.  
  8. Heavily commented to help describe this to a Racket beginner. :)
  9. |#
  10.  
  11. (define (lucky N)
  12.   (let loop ([ls (range 1 (add1 N))]    ; Build the initial list of (0,N]
  13.              [n 2])                     ; Start with 2
  14.     (define first-kept #f)              ; Initialize this for use later.
  15.     ;; Build the new list to replace ls.
  16.     (define sieved
  17.       (for/list ([m (in-list ls)]       ; Map over all the values in ls.
  18.                  [pos (in-naturals 1)]  ; Get position, e.g. third elem -> 3
  19.                  #:unless (zero? (modulo pos n))) ; Filter out nth elements
  20.         ;; Save the first element that is greater than n.  This will be the
  21.         ;; first element saved from the deletion.
  22.         (when (and (not first-kept) (> m n))
  23.           (set! first-kept m))
  24.         m))
  25.     (if first-kept
  26.         ;; When an element was saved, there is more sieving to do.
  27.         (loop sieved first-kept)
  28.         ;; Otherwise work is complete.
  29.         ls)))
  30.  
  31. (module+ test
  32.   (require rackunit)
  33.   (check-equal? (lucky 30)
  34.                 '(1 3 7 9 13 15 21 25))
  35.   (check-equal? (lucky 100)
  36.                 '(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99)))
  37.  
  38. (lucky 100)

=>