Lucky Numbers

March 18, 2014

We calculated Josephus numbers in a previous exercise. In today’s exercise, we study Lucky Numbers, which are those positive integers that survive the Sieve of Josephus. It works like this:

Start with the numbers 1 through n, where n is the desired limit of the sieve; we’ll illustrate with n = 20: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20. At the first step, remove every second number from the sieve, starting from the 0’th: this leaves 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. At the second step, the second number in the list is 3, so remove every third number from the sieve, starting from the 0’th: this leaves 1, 3, 7, 9, 13, 15, 19. At the third step, the third number in the list is 7, so remove every seventh number from the sieve, starting from the 0’th: this leaves 1, 3, 7, 9, 13, 15. And so on. The lucky numbers are listed at A000959: 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, …. Lucky numbers share many properties with prime numbers, including the same asymptotic behavior as the primes: any given number n is lucky with probability 1 / loge n, the same as any given number n is prime with probability 1 / loge n.

Your task is to write a program that lists the lucky numbers less than n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 )

Facebook photo

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

Cancel

Connecting to %s

%d bloggers like this: