Minimal prime (recreational mathematics)

Last updated

In recreational number theory, a minimal prime is a prime number for which there is no shorter subsequence of its digits in a given base that form a prime. In base 10 there are exactly 26 minimal primes:

Contents

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049 (sequence A071062 in the OEIS ).

For example, 409 is a minimal prime because there is no prime among the shorter subsequences of the digits: 4, 0, 9, 40, 49, 09. The subsequence does not have to consist of consecutive digits, so 109 is not a minimal prime (because 19 is prime). But it does have to be in the same order; so, for example, 991 is still a minimal prime even though a subset of the digits can form the shorter prime 19 by changing the order.

Similarly, there are exactly 32 composite numbers which have no shorter composite subsequence:

4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70, 72, 75, 77, 111, 117, 171, 371, 711, 713, 731 (sequence A071070 in the OEIS ).

There are 146 primes congruent to 1 mod 4 which have no shorter prime congruent to 1 mod 4 subsequence:

5, 13, 17, 29, 37, 41, 61, 73, 89, 97, 101, 109, 149, 181, 233, 277, 281, 349, 409, 433, 449, 677, 701, 709, 769, 821, 877, 881, 1669, 2221, 3001, 3121, 3169, 3221, 3301, 3833, 4969, 4993, 6469, 6833, 6949, 7121, 7477, 7949, 9001, 9049, 9221, 9649, 9833, 9901, 9949, ... (sequence A111055 in the OEIS )

There are 113 primes congruent to 3 mod 4 which have no shorter prime congruent to 3 mod 4 subsequence:

3, 7, 11, 19, 59, 251, 491, 499, 691, 991, 2099, 2699, 2999, 4051, 4451, 4651, 5051, 5651, 5851, 6299, 6451, 6551, 6899, 8291, 8699, 8951, 8999, 9551, 9851, ... (sequence A111056 in the OEIS )

Other bases

Minimal primes can be generalized to other bases. It can be shown that there are only a finite number of minimal primes in every base. Equivalently, every sufficiently large prime contains a shorter subsequence that forms a prime.

bminimal primes in base b (written in base b, the letters A,  B,  C, ... represent values 10, 11, 12, ...)
number of
minimal primes
in base b
1111
210, 112
32, 10, 1113
42, 3, 113
52, 3, 10, 111, 401, 414, 14444, 444418
62, 3, 5, 11, 4401, 4441, 400417
72, 3, 5, 10, 14, 16, 41, 61, 111119
82, 3, 5, 7, 111, 141, 161, 401, 661, 4611, 6101, 6441, 60411, 444641, 44444444115
92, 3, 5, 7, 14, 18, 41, 81, 601, 661, 1011, 110112
102, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 6660004926
112, 3, 5, 7, 10, 16, 18, 49, 61, 81, 89, 94, 98, 9A, 199, 1AA, 414, 919, A1A, AA1, 11A9, 66A9, A119, A911, AAA9, 11144, 11191, 1141A, 114A1, 1411A, 144A4, 14A11, 1A114, 1A411, 4041A, 40441, 404A1, 4111A, 411A1, 44401, 444A1, 44A01, 6A609, 6A669, 6A696, 6A906, 6A966, 90901, 99111, A0111, A0669, A0966, A0999, A0A09, A4401, A6096, A6966, A6999, A9091, A9699, A9969, 401A11, 404001, 404111, 440A41, 4A0401, 4A4041, 60A069, 6A0096, 6A0A96, 6A9099, 6A9909, 909991, 999901, A00009, A60609, A66069, A66906, A69006, A90099, A90996, A96006, A96666, 111114A, 1111A14, 1111A41, 1144441, 14A4444, 1A44444, 4000111, 4011111, 41A1111, 4411111, 444441A, 4A11111, 4A40001, 6000A69, 6000A96, 6A00069, 9900991, 9990091, A000696, A000991, A006906, A040041, A141111, A600A69, A906606, A909009, A990009, 40A00041, 60A99999, 99000001, A0004041, A9909006, A9990006, A9990606, A9999966, 40000A401, 44A444441, 900000091, A00990001, A44444111, A66666669, A90000606, A99999006, A99999099, 600000A999, A000144444, A900000066, A0000000001, A0014444444, 40000000A0041, A000000014444, A044444444441, A144444444411, 40000000000401, A0000044444441, A00000000444441, 11111111111111111, 14444444444441111, 44444444444444111, A1444444444444444, A9999999999999996, 1444444444444444444, 4000000000000000A041, A999999999999999999999, A44444444444444444444444441, 40000000000000000000000000041, 440000000000000000000000000001, 999999999999999999999999999999991, 444444444444444444444444444444444444444444441152
122, 3, 5, 7, B, 11, 61, 81, 91, 401, A41, 4441, A0A1, AAAA1, 44AAA1, AAA0001, AA00000117

The base 12 minimal primes written in base 10 are listed in OEIS:  A110600 .

Number of minimal (probable) primes in base n are

1, 2, 3, 3, 8, 7, 9, 15, 12, 26, 152, 17, 228, 240, 100, 483, 1280, [1] 50, 3463, [2] 651, 2601, [3] 1242, 6021, 306, (17608 or 17609), [4] 5664, [5] 17215, [6] 5784, [7] (57296 or 57297), [8] 220, ...

The length of the largest minimal (probable) prime in base n are

2, 2, 3, 2, 5, 5, 5, 9, 4, 8, 45, 8, 32021, 86, 107, 3545, (≥111334), 33, (≥110986), 449, (≥479150), 764, 800874, 100, (≥136967), (≥8773), (≥109006), (≥94538), (≥174240), 1024, ...

Largest minimal (probable) prime in base n (written in base 10) are

2, 3, 13, 5, 3121, 5209, 2801, 76695841, 811, 66600049, 29156193474041220857161146715104735751776055777, 388177921, ... (next term has 35670 digits) (sequence A326609 in the OEIS )

Number of minimal composites in base n are

1, 3, 4, 9, 10, 19, 18, 26, 28, 32, 32, 46, 43, 52, 54, 60, 60, 95, 77, 87, 90, 94, 97, 137, 117, 111, 115, 131, 123, 207, ...

The length of the largest minimal composite in base n are

4, 4, 3, 3, 3, 4, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, ...

Notes

  1. ↑ This value is only conjectured. For base 17, there are 1279 known minimal (probable) primes and one unsolved family: F1{9}
  2. ↑ This value is only conjectured. For base 19, there are 3462 known minimal (probable) primes and one unsolved family: EE1{6}
  3. ↑ This value is only conjectured. For base 21, there are 2600 known minimal (probable) primes and one unsolved family: G{0}FK
  4. ↑ This value is only conjectured. For base 25, there are 17597 known minimal (probable) primes and twelve unsolved families, but the smallest prime of one of these families (LO{L}8) may or may not be a minimal prime, since another unsolved family is O{L}8
  5. ↑ This value is only conjectured. For base 26, there are 5662 known minimal (probable) primes and two unsolved families: {A}6F and {I}GL
  6. ↑ This value is only conjectured. For base 27, there are 17210 known minimal (probable) primes and five unsolved families
  7. ↑ This value is only conjectured. For base 28, there are 5783 known minimal (probable) primes and one unsolved family: O{A}F
  8. ↑ This value is only conjectured. For base 29, there are 57283 known minimal (probable) primes and fourteen unsolved families, but the smallest prime of one of these families ({F}OPF) may or may not be a minimal prime, since another unsolved family is {F}OP

Related Research Articles

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1. In this case, is unsolvable. Germain’s proof, however, remained unfinished. Through her attempts to solve Fermat's Last Theorem, Germain developed a result now known as Germain's Theorem which states that if p is an odd prime and 2p + 1 is also prime, then p must divide x, y, or z. Otherwise, . This case where p does not divide x, y, or z is called the first case. Sophie Germain’s work was the most progress achieved on Fermat’s last theorem at that time. Latter work by Kummer and others always divided the problem into first and second cases. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.

In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.

In number theory, a Sierpiński number is an odd natural number k such that is composite for all natural numbers n. In 1960, Wacław Sierpiński proved that there are infinitely many odd integers k which have this property.

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.

In recreational mathematics, a repdigit or sometimes monodigit is a natural number composed of repeated instances of the same digit in a positional number system. The word is a portmanteau of repeated and digit. Examples are 11, 666, 4444, and 999999. All repdigits are palindromic numbers and are multiples of repunits. Other well-known repdigits include the repunit primes and in particular the Mersenne primes.

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.

In number theory, a Woodall number (Wn) is any natural number of the form

In mathematics, a Riesel number is an odd natural number k for which is composite for all natural numbers n. In other words, when k is a Riesel number, all members of the following set are composite:

In number theory, a Wagstaff prime is a prime number of the form

A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".

In mathematics, Euclid numbers are integers of the form En = pn# + 1, where pn# is the nth primorial, i.e. the product of the first n prime numbers. They are named after the ancient Greek mathematician Euclid, in connection with Euclid's theorem that there are infinitely many prime numbers.

In number theory, a Thabit number, Thâbit ibn Qurra number, or 321 number is an integer of the form for a non-negative integer n.

A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.

In number theory, a full reptend prime, full repetend prime, proper prime or long prime in base b is an odd prime number p such that the Fermat quotient

The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.

In number theory, a Leyland number is a number of the form

References


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.