PasteRack.org
Paste # 91167
2021-10-13 13:51:16

Fork as a new paste.

Paste viewed 544 times.


Embed:

lucky.rkt

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

=>