Cullen number: Difference between revisions
→External links: cat. |
Joel Brennan (talk | contribs) m reworded introduction to remove parenthetical, some formatting edits |
||
Line 1: | Line 1: | ||
{{pp-semi-indef|small=yes}} |
{{pp-semi-indef|small=yes}} |
||
In [[mathematics]], a '''Cullen number''' is a member of the [[ |
In [[mathematics]], a '''Cullen number''' is a member of the [[integer sequence]] <math>C_n = n \cdot 2^n + 1</math> (where <math>n</math> is a [[natural number]]). Cullen numbers were first studied by [[James Cullen (mathematician)|James Cullen]] in 1905. The numbers are special cases of [[Proth number]]s. |
||
== Properties == |
== Properties == |
||
In 1976 [[Christopher Hooley]] showed that the [[natural density]] of positive |
In 1976 [[Christopher Hooley]] showed that the [[natural density]] of positive [[integer]]s <math>n \leq x</math> for which ''C''<sub>''n''</sub> is a [[prime number|prime]] is of the [[Big O notation#Little-o notation|order]] ''o''(''x'') for <math>x \to \infty</math>. In that sense, [[almost all]] Cullen numbers are [[composite number|composite]].<ref name=EPSW94>{{cite book | last1=Everest | first1=Graham | last2=van der Poorten | first2=Alf | author2-link=Alfred van der Poorten | last3=Shparlinski | first3=Igor | last4=Ward | first4=Thomas | title=Recurrence sequences | series=Mathematical Surveys and Monographs | volume=104 | location=[[Providence, RI]] | publisher=[[American Mathematical Society]] | year=2003 | isbn=0-8218-3387-1 | zbl=1033.11006 | page=94 }}</ref> Hooley's proof was reworked by Hiromi Suyama to show that it works for any sequence of numbers ''n'' · 2<sup>''n'' + ''a''</sup> + ''b'' where ''a'' and ''b'' are integers, and in particular also for [[Woodall number]]s. The only known '''Cullen primes''' are those for ''n'' equal to: |
||
: 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881 {{OEIS|id=A005849}}. |
: 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881 {{OEIS|id=A005849}}. |
||
Still, it is |
Still, it is [[conjecture]]d that there are infinitely many Cullen primes. |
||
As of March 2020, the largest known generalized Cullen prime is 2805222 |
As of March 2020, the largest known generalized Cullen prime is 2805222 · 25<sup>2805222</sup> + 1. It has 3,921,539 digits and was discovered by Tom Greer, a [[PrimeGrid]] participant.<ref>{{Cite web|url=https://www.primegrid.com/download/gc25-2805222.pdf|title=PrimeGrid Official Announcement|date=2 September 2019|website=Primegrid|access-date=13 March 2020}}</ref><ref>{{Cite web|url=https://primes.utm.edu/primes/page.php?id=129893|title=The Prime Database: 2805222*5^5610444+1|website=Chris Caldwell's The Largest Known Primes Database|access-date=13 March 2020}}</ref> |
||
A Cullen number ''C<sub>n</sub> |
A Cullen number ''C''<sub>''n''</sub> is [[divisibility|divisible]] by ''p'' = 2''n'' − 1 if ''p'' is a [[prime number]] of the form 8''k'' − 3; furthermore, it follows from [[Fermat's little theorem]] that if ''p'' is an [[parity (mathematics)|odd]] prime, then ''p'' divides ''C''<sub>''m''(''k'')</sub> for each ''m''(''k'') = (2<sup>''k''</sup> − ''k'') |
||
(''p'' |
(''p'' − 1) − ''k'' (for ''k'' > 0). It has also been shown that the prime number ''p'' divides ''C''<sub>(''p'' + 1)/2</sub> when the [[Jacobi symbol]] (2 | ''p'') is −1, and that ''p'' divides ''C''<sub>(3''p'' − 1)/2</sub> when the Jacobi symbol (2 | ''p'') is +1. |
||
It is unknown whether there exists a prime number ''p'' such that ''C''<sub>''p''</sub> is also prime. |
It is unknown whether there exists a prime number ''p'' such that ''C''<sub>''p''</sub> is also prime. |
||
Line 17: | Line 17: | ||
== Generalizations == |
== Generalizations == |
||
Sometimes, a '''generalized Cullen number base ''b''''' is defined to be a number of the form ''n'' |
Sometimes, a '''generalized Cullen number base ''b''''' is defined to be a number of the form ''n'' · ''b''<sup>''n''</sup> + 1, where ''n'' + 2 > ''b''; if a prime can be written in this form, it is then called a '''generalized Cullen prime'''. [[Woodall number]]s are sometimes called '''Cullen numbers of the second kind'''.<ref>{{Cite journal|last=Marques|first=Diego|year=2014|title=On Generalized Cullen and Woodall Numbers That are Also Fibonacci Numbers|url=https://cs.uwaterloo.ca/journals/JIS/VOL17/Marques/marques5r2.pdf|journal=Journal of Integer Sequences|volume=17}}</ref> |
||
According to [[Fermat's little theorem]], if there is a prime ''p'' such that ''n'' is divisible by ''p'' |
According to [[Fermat's little theorem]], if there is a prime ''p'' such that ''n'' is divisible by ''p'' − 1 and ''n'' + 1 is divisible by ''p'' (especially, when ''n'' = ''p'' − 1) and ''p'' does not divide ''b'', then ''b''<sup>''n''</sup> must be [[modular arithmetic|congruent]] to 1 mod ''p'' (since ''b''<sup>''n''</sup> is a power of ''b''<sup> ''p'' − 1</sup> and ''b''<sup> ''p'' − 1</sup> is congruent to 1 mod ''p''). Thus, ''n'' · ''b''<sup>''n''</sup> + 1 is divisible by ''p'', so it is not prime. For example, if some ''n'' congruent to 2 mod 6 (i.e. 2, 8, 14, 20, 26, 32, ...), ''n'' · ''b''<sup>''n''</sup> + 1 is prime, then ''b'' must be divisible by 3 (except ''b'' = 1). |
||
The least ''n'' such that ''n'' · ''b''<sup>''n''</sup> + 1 is prime (with question marks if this term is currently unknown) are<ref>{{cite web|url=http://guenter.loeh.name/gc/status.html |title=Generalized Cullen primes |date=6 May 2017 |last=Löh |first=Günter }}</ref><ref>{{cite web|url=http://harvey563.tripod.com/GClist.txt |title=List of generalized Cullen primes base 101 to 10000 |date=6 May 2017 |last=Harvey |first=Steven }}</ref> |
|||
:1, 1, 2, 1, 1242, 1, 34, 5, 2, 1, 10, 1, ?, 3, 8, 1, 19650, 1, 6460, 3, 2, 1, 4330, 2, 2805222, 117, 2, 1, ?, 1, 82960, 5, 2, 25, 304, 1, 36, 3, 368, 1, 1806676, 1, 390, 53, 2, 1, ?, 3, ?, 9665, 62, 1, 1341174, 3, ?, 1072, 234, 1, 220, 1, 142, 1295, 8, 3, 16990, 1, 474, 129897, ?, 1, 13948, 1, ?, 3, 2, 1161, 12198, 1, 682156, 5, 350, 1, 1242, 26, 186, 3, 2, 1, 298, 14, 101670, 9, 2, 775, 202, 1, 1374, 63, 2, 1, ... {{OEIS|id=A240234}} |
:1, 1, 2, 1, 1242, 1, 34, 5, 2, 1, 10, 1, ?, 3, 8, 1, 19650, 1, 6460, 3, 2, 1, 4330, 2, 2805222, 117, 2, 1, ?, 1, 82960, 5, 2, 25, 304, 1, 36, 3, 368, 1, 1806676, 1, 390, 53, 2, 1, ?, 3, ?, 9665, 62, 1, 1341174, 3, ?, 1072, 234, 1, 220, 1, 142, 1295, 8, 3, 16990, 1, 474, 129897, ?, 1, 13948, 1, ?, 3, 2, 1161, 12198, 1, 682156, 5, 350, 1, 1242, 26, 186, 3, 2, 1, 298, 14, 101670, 9, 2, 775, 202, 1, 1374, 63, 2, 1, ... {{OEIS|id=A240234}} |
||
Revision as of 19:56, 13 January 2021
In mathematics, a Cullen number is a member of the integer sequence (where is a natural number). Cullen numbers were first studied by James Cullen in 1905. The numbers are special cases of Proth numbers.
Properties
In 1976 Christopher Hooley showed that the natural density of positive integers for which Cn is a prime is of the order o(x) for . In that sense, almost all Cullen numbers are composite.[1] Hooley's proof was reworked by Hiromi Suyama to show that it works for any sequence of numbers n · 2n + a + b where a and b are integers, and in particular also for Woodall numbers. The only known Cullen primes are those for n equal to:
- 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881 (sequence A005849 in the OEIS).
Still, it is conjectured that there are infinitely many Cullen primes.
As of March 2020, the largest known generalized Cullen prime is 2805222 · 252805222 + 1. It has 3,921,539 digits and was discovered by Tom Greer, a PrimeGrid participant.[2][3]
A Cullen number Cn is divisible by p = 2n − 1 if p is a prime number of the form 8k − 3; furthermore, it follows from Fermat's little theorem that if p is an odd prime, then p divides Cm(k) for each m(k) = (2k − k) (p − 1) − k (for k > 0). It has also been shown that the prime number p divides C(p + 1)/2 when the Jacobi symbol (2 | p) is −1, and that p divides C(3p − 1)/2 when the Jacobi symbol (2 | p) is +1.
It is unknown whether there exists a prime number p such that Cp is also prime.
Generalizations
Sometimes, a generalized Cullen number base b is defined to be a number of the form n · bn + 1, where n + 2 > b; if a prime can be written in this form, it is then called a generalized Cullen prime. Woodall numbers are sometimes called Cullen numbers of the second kind.[4]
According to Fermat's little theorem, if there is a prime p such that n is divisible by p − 1 and n + 1 is divisible by p (especially, when n = p − 1) and p does not divide b, then bn must be congruent to 1 mod p (since bn is a power of b p − 1 and b p − 1 is congruent to 1 mod p). Thus, n · bn + 1 is divisible by p, so it is not prime. For example, if some n congruent to 2 mod 6 (i.e. 2, 8, 14, 20, 26, 32, ...), n · bn + 1 is prime, then b must be divisible by 3 (except b = 1).
The least n such that n · bn + 1 is prime (with question marks if this term is currently unknown) are[5][6]
- 1, 1, 2, 1, 1242, 1, 34, 5, 2, 1, 10, 1, ?, 3, 8, 1, 19650, 1, 6460, 3, 2, 1, 4330, 2, 2805222, 117, 2, 1, ?, 1, 82960, 5, 2, 25, 304, 1, 36, 3, 368, 1, 1806676, 1, 390, 53, 2, 1, ?, 3, ?, 9665, 62, 1, 1341174, 3, ?, 1072, 234, 1, 220, 1, 142, 1295, 8, 3, 16990, 1, 474, 129897, ?, 1, 13948, 1, ?, 3, 2, 1161, 12198, 1, 682156, 5, 350, 1, 1242, 26, 186, 3, 2, 1, 298, 14, 101670, 9, 2, 775, 202, 1, 1374, 63, 2, 1, ... (sequence A240234 in the OEIS)
b | numbers n such that n × bn + 1 is prime (these n are checked up to 101757) | OEIS sequence |
1 | 1, 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, 138, 148, 150, 156, 162, 166, 172, 178, 180, 190, 192, 196, 198, 210, 222, 226, 228, 232, 238, 240, 250, 256, 262, 268, 270, 276, 280, 282, 292, ... (all primes minus 1) | A006093 |
2 | 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881, ... | A005849 |
3 | 2, 8, 32, 54, 114, 414, 1400, 1850, 2848, 4874, 7268, 19290, 337590, 1183414, ... | A006552 |
4 | 1, 3, 7, 33, 67, 223, 663, 912, 1383, 3777, 3972, 10669, 48375, ... | A007646 |
5 | 1242, 18390, ... | |
6 | 1, 2, 91, 185, 387, 488, 747, 800, 9901, 10115, 12043, 13118, 30981, 51496, ... | A242176 |
7 | 34, 1980, 9898, ... | A242177 |
8 | 5, 17, 23, 1911, 20855, 35945, 42816, ..., 749130, ... | A242178 |
9 | 2, 12382, 27608, 31330, 117852, ... | A265013 |
10 | 1, 3, 9, 21, 363, 2161, 4839, 49521, 105994, 207777, ... | A007647 |
11 | 10, ... | |
12 | 1, 8, 247, 3610, 4775, 19789, 187895, ... | A242196 |
13 | ... | |
14 | 3, 5, 6, 9, 33, 45, 243, 252, 1798, 2429, 5686, 12509, 42545, ... | A242197 |
15 | 8, 14, 44, 154, 274, 694, 17426, 59430, ... | A242198 |
16 | 1, 3, 55, 81, 223, 1227, 3012, 3301, ... | A242199 |
17 | 19650, 236418, ... | |
18 | 1, 3, 21, 23, 842, 1683, 3401, 16839, 49963, 60239, 150940, 155928, ... | A007648 |
19 | 6460, ... | |
20 | 3, 6207, 8076, 22356, 151456, ... | |
21 | 2, 8, 26, 67100, ... | |
22 | 1, 15, 189, 814, 19909, 72207, ... | |
23 | 4330, 89350, ... | |
24 | 2, 8, 368, ... | |
25 | 2805222, ... | |
26 | 117, 3143, 3886, 7763, 64020, 88900, ... | |
27 | 2, 56, 23454, ..., 259738, ... | |
28 | 1, 48, 468, 2655, 3741, 49930, ... | |
29 | ... | |
30 | 1, 2, 3, 7, 14, 17, 39, 79, 87, 99, 128, 169, 221, 252, 307, 3646, 6115, 19617, 49718, ... |
References
- ^ Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence sequences. Mathematical Surveys and Monographs. Vol. 104. Providence, RI: American Mathematical Society. p. 94. ISBN 0-8218-3387-1. Zbl 1033.11006.
- ^ "PrimeGrid Official Announcement" (PDF). Primegrid. 2 September 2019. Retrieved 13 March 2020.
- ^ "The Prime Database: 2805222*5^5610444+1". Chris Caldwell's The Largest Known Primes Database. Retrieved 13 March 2020.
- ^ Marques, Diego (2014). "On Generalized Cullen and Woodall Numbers That are Also Fibonacci Numbers" (PDF). Journal of Integer Sequences. 17.
- ^ Löh, Günter (6 May 2017). "Generalized Cullen primes".
- ^ Harvey, Steven (6 May 2017). "List of generalized Cullen primes base 101 to 10000".
Further reading
- Cullen, James (December 1905), "Question 15897", Educ. Times: 534.
- Guy, Richard K. (2004), Unsolved Problems in Number Theory (3rd ed.), New York: Springer Verlag, Section B20, ISBN 0-387-20860-7, Zbl 1058.11001.
- Hooley, Christopher (1976), Applications of sieve methods, Cambridge Tracts in Mathematics, vol. 70, Cambridge University Press, pp. 115–119, ISBN 0-521-20915-3, Zbl 0327.10044.
- Keller, Wilfrid (1995), "New Cullen Primes" (PDF), Mathematics of Computation, 64 (212): 1733–1741, S39–S46, doi:10.2307/2153382, ISSN 0025-5718, Zbl 0851.11003.
External links
- Chris Caldwell, The Top Twenty: Cullen primes at The Prime Pages.
- The Prime Glossary: Cullen number at The Prime Pages.
- Weisstein, Eric W. "Cullen number". MathWorld.
- Cullen prime: definition and status[permanent dead link ] (outdated), Cullen Prime Search is now hosted at PrimeGrid
- Paul Leyland, (Generalized) Cullen and Woodall Numbers