From oleg-at-okmij.org Mon Feb 12 17:37:46 2007
To: haskell-cafe@haskell.org
Subject: Even better Eratosthenes sieve and lucky numbers
From: oleg-at-pobox.com
Message-ID: <20070213023746.11694AB40@Adric.metnet.fnmoc.navy.mil>
Date: Mon, 12 Feb 2007 18:37:46 -0800 (PST)
Status: OR
We further simplify the previously posted genuine sieve algorithm and
generalize it to the finding of lucky numbers.
We observe that we only need to store marks _signifying_ the integers,
but never the integers themselves. Thus we arrive at the algorithm
that is distinguished from all previously posted by:
(i) doing no operations on composite numbers
(ii) using neither multiplication nor division nor the
remainder operation
(iii) using neither general addition nor the comparison.
The algorithm only relies on the successor, predecessor and zero
comparison. The predecessor can be easily eliminated. Thus the
algorithm can be used with Church and Peano numerals, or members of
Elliptic rings, where zero comparison and successor take constant
time but other arithmetic operations are more involved.
> -- repl_every_n n l replaces every (n+1)-th element in a list (_:l)
> -- with False
> repl_every_n :: Int -> [Bool] -> [Bool]
> repl_every_n n l = repl_every_n' n l
> where repl_every_n' 0 (_:t) = False: repl_every_n n t
> repl_every_n' i (h:t) = h: repl_every_n' (pred i) t
>
> primes = 2:(loop 3 (repeat True))
> where loop n (False:t) = loop (succ (succ n)) t
> loop n (_:t) = n:(loop (succ (succ n)) (repl_every_n (pred n) t))
>
> main = putStrLn $ "Last 10 primes less than 10000: " ++
> show (take 10 $ reverse $ takeWhile (< 10000) primes)
Last 10 primes less than 10000:
[9973,9967,9949,9941,9931,9929,9923,9907,9901,9887]
The algorithm easily generalizes to lucky numbers
http://mathworld.wolfram.com/LuckyNumber.html
http://www.research.att.com/~njas/sequences/A000959
> -- Consider the series of odd numbers starting with k=1; the k-th number
> -- is 2k-1.
> -- If we start the elimination from the very beginning of the series (k=1),
> -- we start with the phase (2k-2) and eliminate with the step 2k-2.
> -- If we start at the number k+1, the phase becomes (2k-2-k) = (k-2).
> -- Thus the starting phase gets incremented by 1 as we move up the series.
> -- However, already eliminated numbers don't count, so as we skip
> -- over eliminated numbers, we increment the phase by 2
> lucky = 1:(loop 3 0 (repeat True))
> where loop n i (False:t) = loop (succ (succ n)) (succ (succ i)) t
> loop n i (_:t) = n:(loop (succ (succ n)) (succ i)
> (repl_every_np i (pred n) t))
>
> -- repl_every_np i n eliminates (marks as False) every (n+1)-th number
> -- starting with the phase i.
> -- Already eliminated numbers don't count.
> repl_every_np :: Int -> Int -> [Bool] -> [Bool]
> repl_every_np i n (False:t) = False: repl_every_np i n t
> repl_every_np 0 n (_:t) = False: repl_every_np n n t
> repl_every_np i n (_:t) = True: repl_every_np (pred i) n t
*Main> take 10 lucky
[1,3,7,9,13,15,21,25,31,33]
*Main> takeWhile (<100) lucky
[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87,93,99]