TITLE: Implementing Flavius Josephus's Sieve
AUTHOR: Eugene Wallingford
DATE: February 23, 2023 10:40 AM
DESC:
-----
BODY:
The other night, I wanted to have some fun, so I implemented a few
Racket functions to implement
Flavius Josephus's sieve.
Think the sieve of Eratosthenes, but with each pass applied to the
numbers left after the previous pass:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
1 3 5 7 9 11 13 15 ... - after pass 1 (remove every 2nd)
1 3 7 9 13 15 ... - after pass 2 (remove every 3rd)
1 3 7 13 15 ... - after pass 3 (remove every 4th)
...
My code isn't true to the mathematical ideal, because it doesn't
process the unbounded sequence of natural numbers. (Haskell, with
lazy evaluation, might be a better choice for that!) Instead, it
works on a range [1..n] for a given n.
That's plenty good enough for me to see how the sequence evolves.
I ended up using a mix of higher-order functions and recursive
functions. When it comes to time to filter out every kth
item in the previous sequence, I generate a list of booleans with
false in every kth position and true elsewhere. For example,
'(#t #t #f #t #t #f ...) is the mask for the pass that
filters out every third item. Then, this function:
(define filter-with-mask
(lambda (lon mask)
(map car
(filter (lambda (p) (cdr p))
(map cons lon mask)))))
applies a mask to a list of numbers lon and produces an
updated list of numbers. The rest of the code is a recursive
function that, on each pass, applies the next mask in sequence to
the list remaining after the previous pass.
I won't be surprised if my mathematician friends, or readers who
are better Racket programmers, can suggest a more elegant way to
"strain" a list, but, hey, I'm a programmer. This is a simple
enough approach that does the job. The code is reasonably fast
and flexible.
In any case, it was a nice way to spend an hour after a long day
on campus. My wife just smiled when I told what I was going to
do to relax that evening. She knows me well.
-----