Base-independent classifications of prime numbers

Classifications of primes NOT depending on their base representation.

(see also: base-dependent classifications of prime numbers)

Prime numbers by form

Here $\scriptstyle n\,$ is a nonnegative integer and $\scriptstyle q\,$ is a prime related in some way to the prime $\scriptstyle p\,$ listed.

Primes in arithmetic progressions: a n + b, gcd(a, b) = 1

Primes coprime to 4 (primes in 4 n ± 1)

Except for the prime 2 (prime factor of 4), all primes are coprime to 4.

$4n-1\,$ Non-Pythagorean primes

A002145 {3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, 283, 307, 311, 331, 347, 359, 367, 379, ...}

These primes are also primes among the Gaussian integers (see Gaussian primes).

$4n+1\,$ Pythagorean odd primes (note that the even prime $2=1^{2}+1^{2}=(1-i)(1+i)$ is also Pythagorean)

A002144 {5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181, 193, 197, 229, 233, 241, 257, 269, 277, 281, 293, 313, 317, 337, 349, 353, 373, 389, 397, 401, ...}

However, among the Gaussian integers, these numbers are composites (see Gaussian composites). For example, $\scriptstyle 5\,=\,(1-2i)(1+2i).\,$

Primes coprime to 6 (primes in 6 n ± 1)

Except for the primes 2 and 3 (prime factors of 6), all primes are coprime to 6.

$6n-1\,$

A007528 {5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293, 311, 317, 347, 353, 359, 383, 389, ...}

$6n+1\,$

A002476 {7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199, 211, 223, 229, 241, 271, 277, 283, 307, 313, 331, 337, 349, 367, 373, 379, 397, 409, ...}

Primes coprime to 30 (primes in 30 n ± 1, 30 n ± 7, 30 n ± 11, 30 n ± 13)

Except for the primes 2, 3 and 5 (prime factors of 30), all primes are coprime to 30.

$30n-13\,$

A039949 {17, 47, 107, 137, 167, 197, 227, 257, 317, 347, 467, 557, 587, 617, 647, 677, 797, 827, 857, 887, 947, 977, 1097, 1187, 1217, 1277, 1307, 1367, 1427, 1487, 1607, 1637, 1667, 1697, ...}

$30n-11\,$

A132234 {19, 79, 109, 139, 199, 229, 349, 379, 409, 439, 499, 619, 709, 739, 769, 829, 859, 919, 1009, 1039, 1069, 1129, 1249, 1279, 1399, 1429, 1459, 1489, 1549, 1579, 1609, 1669, 1699, ...}

$30n-7\,$

A132235 {23, 53, 83, 113, 173, 233, 263, 293, 353, 383, 443, 503, 563, 593, 653, 683, 743, 773, 863, 953, 983, 1013, 1103, 1163, 1193, 1223, 1283, 1373, 1433, 1493, 1523, 1553, 1583, 1613, ...}

$30n-1\,$

A132236 {29, 59, 89, 149, 179, 239, 269, 359, 389, 419, 449, 479, 509, 569, 599, 659, 719, 809, 839, 929, 1019, 1049, 1109, 1229, 1259, 1289, 1319, 1409, 1439, 1499, 1559, 1619, 1709, 1889, ...}

$30n+1\ \,$

A132230 {31, 61, 151, 181, 211, 241, 271, 331, 421, 541, 571, 601, 631, 661, 691, 751, 811, 991, 1021, 1051, 1171, 1201, 1231, 1291, 1321, 1381, 1471, 1531, 1621, 1741, 1801, 1831, 1861, ...}

$30n+7\,$

A132231 {7, 37, 67, 97, 127, 157, 277, 307, 337, 367, 397, 457, 487, 547, 577, 607, 727, 757, 787, 877, 907, 937, 967, 997, 1087, 1117, 1237, 1297, 1327, 1447, 1567, 1597, 1627, 1657, 1747, ...}

$30n+11\,$

A132232 {11, 41, 71, 101, 131, 191, 251, 281, 311, 401, 431, 461, 491, 521, 641, 701, 761, 821, 881, 911, 941, 971, 1031, 1061, 1091, 1151, 1181, 1301, 1361, 1451, 1481, 1511, 1571, 1601, ...}

$30n+13\,$

A132233 {13, 43, 73, 103, 163, 193, 223, 283, 313, 373, 433, 463, 523, 613, 643, 673, 733, 823, 853, 883, 1033, 1063, 1093, 1123, 1153, 1213, 1303, 1423, 1453, 1483, 1543, 1663, 1693, 1723, ...}

Primes in quadratic progressions: a n² + b n + c

Primes in n² - 1 or n² + 1

$n^{2}-1=(n-1)(n+1)\,$ Almost-square primes

{3}

The only way to get a prime is for $\scriptstyle n-1\,$ to be 1, thus 3 is the only almost-square prime.

$n^{2}+1\,$ Landau primes, or quasi-square primes

A002496 {2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, 1601, 2917, 3137, 4357, 5477, 7057, 8101, 8837, 12101, 13457, 14401, 15377, ...}

Primes in k² + n²

Fouvry-Iwaniec primes: primes of the form k² + p² where p is a prime

Fouvry-Iwaniec primes: primes of the form $\scriptstyle k^{2}+p^{2}\,$ where $\scriptstyle p\,$ is a prime.

A185086 {5, 13, 29, 41, 53, 61, 73, 89, 109, 113, 137, 149, 157, 173, 193, 229, 233, 269, 281, 293, 313, 317, 349, 353, 373, 389, 397, 409, 433, ...}

A?????? Primes that are sums of the squares of two primes.

{13, 29, 41, 53, 73, 89, 109, ...}

Primes of the form k² + m² where k and m are coprime composite numbers

A?????? Primes that are sums of the squares of two coprime composite numbers.

{97, ...}

A108655 Primes that are sums of the squares of two semiprimes.

{97, 181, 241, 277, 421, 457, 541, 641, 661, 709, 757, 821, 1109, 1117, 1237, 1301, 1381, 1597, 1621, 1669, 1709, 1901, 2069, 2341, 2381, 2417, 2437, 2557, 2617, 2677, 2741, 2797, ...}

Primes in superpolynomial progressions

Primes in 2^k - 1 or 2^k + 1

$2^{k}-1\,$ Mersenne primes (where $\scriptstyle k\,$ must be some prime $\scriptstyle q\,$, as a necessary but not sufficient condition)

A000668 {3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, ...}

It is conjectured that there are an infinity of Mersenne primes (although it has not been proved yet...)

See also primes as differences of powers.

$2^{k}+1\,$ Fermat primes (where $\scriptstyle k\,$ must be a power of 2, as a necessary but not sufficient condition, i.e. $\scriptstyle k\,=\,2^{n},\,n\,\geq \,0\,$)

A019434 {3, 5, 17, 257, 65537, ...no more?}

This might be the complete list (only $\scriptstyle F_{0}\,$ to $\scriptstyle F_{4}\,$ are known to be prime,) although it has not been proved yet...

Nearly primorial primes

Cf. primorial.

$n\sharp -1\,$ Almost-primorial primes

A057705 {5, 29, 2309, 30029, 304250263527209, 23768741896345550770650537601358309, ...}

$n\sharp +1\,$ Quasi-primorial primes

A018239 {2, 3, 7, 31, 211, 2311, 200560490131, ...}

2 as the empty product (valued 1, the multiplicative identity) + 1, corresponding to the 0^th primorial.

Nearly LCM primes

Cf. LCM.

${\text{lcm}}(1,\ldots ,k)-1\,$, where k is the n-th prime power A000961(n). (Primes in A208768.) Almost-LCM primes

A057824 {5, 11, 59, 419, 839, 232792559, 5354228879, 2329089562799, 144403552893599, 442720643463713815199, 591133442051411133755680799, ...}

${\text{lcm}}(1,\ldots ,k)+1\,$, where k is the n-th prime power A000961(n). (Primes in A051452.) Quasi-LCM primes

A049536 {2, 3, 7, 13, 61, 421, 2521, 232792561, 26771144401, 72201776446801, 442720643463713815201, 718766754945489455304472257065075294401, ...}

Nearly compositorial primes

Cf. compositorial.

${\tfrac {n!}{n\sharp }}-1\,$ is prime Almost-compositorial primes

A?????? {3, 3, 23, 23, 191, ...}

Numbers $\scriptstyle n\,$ such that ${\tfrac {n!}{n\sharp }}-1\,$ is prime.

A140293 {4, 5, 6, 7, 8, 16, 17, 21, 34, 39, 45, 50, 72, 73, 76, 133, 164, 202, 216, 221, 280, 281, 496, 605, 2532, 2967, 3337, 8711, 10977, 13724, ...}

${\tfrac {n!}{n\sharp }}+1\,$ Quasi-compositorial primes

A?????? {?, ...}

Numbers $\scriptstyle n\,$ such that ${\tfrac {n!}{n\sharp }}+1\,$ is prime.

A140294 {0, 1, 2, 3, 4, 5, 8, 14, 20, 26, 34, 56, 104, 153, 182, 194, 217, 230, 280, 281, 462, 463, 529, 1445, 2515, 3692, 6187, 6851, 13917, ...}

Numbers $\scriptstyle n\,$ such that ${\tfrac {n!}{n\sharp }}-1\,$ and ${\tfrac {n!}{n\sharp }}+1\,$ is a twin prime pair.

A140315 {4, 5, 8, 34, 280, 281, ...}

Nearly subfactorial primes

Cf. subfactorial.

$!n-1\,$ Almost-subfactorial primes

A?????? {?, ...}

$!n+1\,$ Quasi-subfactorial primes

A?????? {?, ...}

Nearly factorial primes

Cf. factorial.

$n!-1\,$ Almost-factorial primes

A055490 {5, 29, 2309, 30029, 304250263527209, 23768741896345550770650537601358309, ...}

$n!+1\,$ Quasi-factorial primes

A088332 {2, 3, 7, 39916801, 10888869450418352160768000001, 13763753091226345046315979581580902400000001, ...}

Nearly fibonorial primes

Cf. fibonorial.

$\prod _{i=1}^{n}{F_{i}}-1\,$ Almost-fibonorial primes

A?????? {5, 29, 239, 3119, 65519, 2227679, 122522399, 10904493599, ...}

$\prod _{i=1}^{n}{F_{i}}+1\,$ Quasi-fibonorial primes

A053413 {2, 2, 3, 7, 31, 241, 3121, 65521, 1879127177606120717127879344567470740879360001, ...}

Prime numbers by relation to other primes

Exponents of Mersenne primes: primes $\scriptstyle q\,$ such that $\scriptstyle p\,=\,2^{q}-1\,$ is prime.

A000043 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, ...}

Exponents of Mersenne primes that are themselves Mersenne primes: primes $\scriptstyle r\,$ such that $\scriptstyle q\,=\,2^{r}-1\,$ is prime and such that $\scriptstyle p\,=\,2^{q}-1\,$ is prime.

A103901: {3, 7, 31, 127, ...more?}

Only these four terms are known...

Sophie Germain primes primes $\scriptstyle p\,$ such that $\scriptstyle 2p+1\,$ is also prime

A005384 {2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, ...}

Safe primes: primes $\scriptstyle p\,$ such that $\scriptstyle {\frac {p-1}{2}}\,$ is also prime

A005385 {5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, ...}

Primes which are simultaneously safe primes and Sophie Germain primes: intersection of safe primes and Sophie Germain primes

A059455 {5, 11, 23, 83, 179, 359, 719, 1019, 1439, 2039, 2063, 2459, 2819, 2903, 2963, 3023, 3623, 3779, 3803, 3863, 4919, 5399, 5639, ...}

Balanced primes (of order one): primes which are the average of the previous prime and the following prime.

A006562 {5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, 1103, 1123, 1187, 1223, 1367, 1511, 1747, 1753, 1907, 2287, 2417, 2677, 2903, 2963, 3307, 3313, 3637, 3733, ...}

Primes related to the prime counting function

Ramanujan primes

Main article page: Ramanujan primes

Prime constellations

Main article page: Prime constellations