Lucky Numbers

March 18, 2014

We store the sieve in a list, initialized with only the odd positive integers to save the first step in the iteration:

(define (lucky n)
  (let loop ((i 1) (sieve (range 1 n 2)))
    (let ((p (list-ref sieve i)))
      (if (< (length sieve) p) sieve
        (loop (+ i 1) (del sieve p))))))

The del function removes every k‘th item from a list:

(define (del xs k)
  (let loop ((i 1) (xs xs) (zs (list)))
    (if (null? xs) (reverse zs)
      (if (zero? (modulo i k))
          (loop (+ i 1) (cdr xs) zs)
          (loop (+ i 1) (cdr xs) (cons (car xs) zs))))))

Here’s the list from oeis.org:

> (lucky 304)
(1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87
 93 99 105 111 115 127 129 133 135 141 151 159 163 169 171
 189 193 195 201 205 211 219 223 231 235 237 241 259 261 267
 273 283 285 289 297 303)

We used range from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/Dtz9yq59.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
6 Comments »

6 Responses to “Lucky Numbers”

  1. Tejas said
    March 18, 2014 at 11:18 AM

    Can anybody give me link for the proof for probability that a given number ‘n’ is prime is (1 / loge n)?

  2. Mike said
    March 18, 2014 at 11:08 PM 
    from itertools import count

def lucky(n):
	ns = list(range(1, n, 2))
	for i in count(1):
		if ns[i] >= len(ns):
			return ns
		del ns[ns[i]-1::ns[i]]
  3. programmingpraxis said
    March 18, 2014 at 11:13 PM

    @Tejas: That’s the Prime Number Theorem, first conjectured by Gauss when he was fourteen years old and proved later. Wikipedia and MathWorld are good places to start your study.

  4. Tejas said
    March 19, 2014 at 3:51 AM

    Thanks a lot..

  5. Josef Svenningsson said
    March 19, 2014 at 2:55 PM

    I’m almost ashamed at showing my convoluted Haskell versions but here is one anyway (it computes all lucky numbers):

    lucky = 1 : unfoldr remNth [2..]
    remNth (a:as) = let bs@(b:_) = removeNth a as in Just (b,bs)
    removeNth n [] = []
removeNth n ls = init ++ removeNth n rest
  where (init,_:rest) = splitAt (n-1) ls
  6. matthew said
    April 5, 2014 at 5:01 PM

    Are you sure that Haskell version is right? This is my one:

    dropn n 1 (a:s) = dropn n n s
dropn n m (a:s) = a : dropn n (m-1) s
lucky = 1:(aux 2 [3,5..])
  where aux k (n:s) = n:aux (k+1) (dropn n (n-k) s)

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: