Lucky number

Last updated

In number theory, a lucky number is a natural number in a set which is generated by a certain "sieve". This sieve is similar to the Sieve of Eratosthenes that generates the primes, but it eliminates numbers based on their position in the remaining set, instead of their value (or position in the initial set of natural numbers). [1]

Contents

The term was introduced in 1956 in a paper by Gardiner, Lazarus, Metropolis and Ulam. In the same work they also suggested calling another sieve, "the sieve of Josephus Flavius" [2] because of its similarity with the counting-out game in the Josephus problem.

Lucky numbers share some properties with primes, such as asymptotic behaviour according to the prime number theorem; also, a version of Goldbach's conjecture has been extended to them. There are infinitely many lucky numbers. Twin lucky numbers and twin primes also appear to occur with similar frequency. However, if Ln denotes the n-th lucky number, and pn the n-th prime, then Ln > pn for all sufficiently large n. [3]

Because of their apparent similarities with the prime numbers, some mathematicians have suggested that some of their common properties may also be found in other sets of numbers generated by sieves of a certain unknown form, but there is little theoretical basis for this conjecture.

The sieving process

An animation demonstrating the lucky number sieve. The numbers on a reddish orange background are lucky numbers. When a number is eliminated its background changes from grey to purple. Chart goes to 120. LuckySieve.gif
An animation demonstrating the lucky number sieve. The numbers on a reddish orange background are lucky numbers. When a number is eliminated its background changes from grey to purple. Chart goes to 120.
Begin with a list of integers starting with 1:
12345678910111213141516171819202122232425
Every second number (all even numbers) in the list is eliminated, leaving only the odd integers:
135791113151719212325
The first number remaining in the list after 1 is 3, so every third number (beginning at 1) which remains in the list (not every multiple of 3) is eliminated. The first of these is 5:
13791315192125
The next surviving number is now 7, so every seventh remaining number is eliminated. The first of these is 19:
137913152125

Continue removing the nth remaining numbers, where n is the next number in the list after the last surviving number. Next in this example is 9.

One way that the application of the procedure differs from that of the Sieve of Eratosthenes is that for n being the number being multiplied on a specific pass, the first number eliminated on the pass is the n-th remaining number that has not yet been eliminated, as opposed to the number 2n. That is to say, the list of numbers this sieve counts through is different on each pass (for example 1, 3, 7, 9, 13, 15, 19... on the third pass), whereas in the Sieve of Eratosthenes, the sieve always counts through the entire original list (1, 2, 3...).

When this procedure has been carried out completely, the remaining integers are the lucky numbers (those that happen to be prime are in bold):

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, 307 , 319, 321, 327, 331 , 339, ... (sequence A000959 in the OEIS ).

The lucky number which removes n from the list of lucky numbers is: (0 if n is a lucky number)

0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 7, 2, 0, 2, 3, 2, 0, 2, 9, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 7, 2, 3, 2, 0, 2, 13, 2, 3, 2, 0, 2, 0, 2, 3, 2, 15, 2, 9, 2, 3, 2, 7, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 7, 2, 3, 2, 21, 2, ... (sequence A264940 in the OEIS )

Lucky primes

A "lucky prime" is a lucky number that is prime. They are:

3, 7, 13, 31, 37, 43, 67, 73, 79, 127, 151, 163, 193, 211, 223, 241, 283, 307, 331, 349, 367, 409, 421, 433, 463, 487, 541, 577, 601, 613, 619, 631, 643, 673, 727, 739, 769, 787, 823, 883, 937, 991, 997, ... (sequence A031157 in the OEIS ).

It has been conjectured that there are infinitely many lucky primes. [4]

See also

Related Research Articles

A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair or (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin or prime pair.

<span class="mw-page-title-main">Goldbach's conjecture</span> Even integers as sums of two primes

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.

<span class="mw-page-title-main">Multiply perfect number</span> Number whose divisors add to a multiple of that number

In mathematics, a multiply perfect number is a generalization of a perfect number.

<span class="mw-page-title-main">Abundant number</span> Number that is less than the sum of its proper divisors

In number theory, an abundant number or excessive number is a positive integer for which the sum of its proper divisors is greater than the number. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. The amount by which the sum exceeds the number is the abundance. The number 12 has an abundance of 4, for example.

In mathematics, a Cullen number is a member of the integer sequence . Cullen numbers were first studied by James Cullen in 1905. The numbers are special cases of Proth numbers.

<span class="mw-page-title-main">Weird number</span> Number which is abundant but not semiperfect

In number theory, a weird number is a natural number that is abundant but not semiperfect. In other words, the sum of the proper divisors of the number is greater than the number, but no subset of those divisors sums to the number itself.

27 is the natural number following 26 and preceding 28.

69 is the natural number following 68 and preceding 70. An odd number and a composite number, 69 is divisible by 1, 3, 23 and 69. 69 is a semiprime because it is a natural number that is the product of exactly two prime numbers, and an interprime between the numbers of 67 and 71. Because 69 is not divisible by any square number other than 1, it is categorised as a square-free integer. 69 is also a Blum integer since the two factors of 69 are both Gaussian primes. In number theory, 69 is a deficient number, arithmetic number and a congruent number.

79 (seventy-nine) is the natural number following 78 and preceding 80.

31 (thirty-one) is the natural number following 30 and preceding 32. It is a prime number.

37 (thirty-seven) is the natural number following 36 and preceding 38.

In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function only multiplies prime numbers.

300 is the natural number following 299 and preceding 301.

<span class="mw-page-title-main">Prime gap</span> Difference between two successive prime numbers

A prime gap is the difference between two successive prime numbers. The n-th prime gap, denoted gn or g(pn) is the difference between the (n + 1)-st and the n-th prime numbers, i.e.

<span class="mw-page-title-main">5</span> Integer number 5

5 (five) is a number, numeral and digit. It is the natural number, and cardinal number, following 4 and preceding 6, and is a prime number.

In mathematics, a Wieferich pair is a pair of prime numbers p and q that satisfy

In mathematics, the Ulam numbers comprise an integer sequence devised by and named after Stanislaw Ulam, who introduced it in 1964. The standard Ulam sequence starts with U1 = 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.

A Fortunate number, named after Reo Fortune, is the smallest integer m > 1 such that, for a given positive integer n, pn# + m is a prime number, where the primorial pn# is the product of the first n prime numbers.

Euler's "lucky" numbers are positive integers n such that for all integers k with 1 ≤ k < n, the polynomial k2k + n produces a prime number.

References

  1. Weisstein, Eric W. "Lucky Number". mathworld.wolfram.com. Retrieved 2020-08-11.
  2. Gardiner, Verna; Lazarus, R.; Metropolis, N.; Ulam, S. (1956). "On certain sequences of integers defined by sieves". Mathematics Magazine . 29 (3): 117–122. doi:10.2307/3029719. ISSN   0025-570X. JSTOR   3029719. Zbl   0071.27002.
  3. Hawkins, D.; Briggs, W.E. (1957). "The lucky number theorem". Mathematics Magazine . 31 (2): 81–84, 277–280. doi:10.2307/3029213. ISSN   0025-570X. JSTOR   3029213. Zbl   0084.04202.
  4. Sloane, N. J. A. (ed.). "SequenceA031157(Numbers that are both lucky and prime)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.

Further reading