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. They suggest also calling its defining 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, ... (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

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation:

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">Ulam spiral</span> Visualization of the prime numbers formed by arranging the integers into a spiral

The Ulam spiral or prime spiral is a graphical depiction of the set of prime numbers, devised by mathematician Stanisław Ulam in 1963 and popularized in Martin Gardner's Mathematical Games column in Scientific American a short time later. It is constructed by writing the positive integers in a square spiral and specially marking the prime numbers.

<span class="mw-page-title-main">Sieve of Eratosthenes</span> Ancient algorithm for generating prime numbers

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

7 (seven) is the natural number following 6 and preceding 8. It is the only prime number preceding a cube.

<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>

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.

In mathematics, a k-hyperperfect number is a natural number n for which the equality n = 1 + k(σ(n) − n − 1) holds, where σ(n) is the divisor function (i.e., the sum of all positive divisors of n). A hyperperfect number is a k-hyperperfect number for some integer k. Hyperperfect numbers generalize perfect numbers, which are 1-hyperperfect.

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

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.

In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public-key cryptography, and search of prime factors in large numbers.

<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.

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. It has garnered attention throughout history in part because distal extremities in humans typically contain five digits.

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 k2 − k + 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.