Jump to content

Cullen number: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
m Generalizations: Adding web.archive.org links for citations with url-status=live Category:CS1_maint:_url-status
Tags: AWB Reverted
Adding local short description: "Mathematical concept", overriding Wikidata description "number of the form n*(2^n)+1"
 
(23 intermediate revisions by 11 users not shown)
Line 1: Line 1:
{{Short description|Mathematical concept}}
{{pp-semi-indef|small=yes}}
{{pp-semi-indef|small=yes}}
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.
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.
Line 4: Line 5:
== Properties ==
== Properties ==
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:
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}}.
: 1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881 {{OEIS|id=A005849}}.


Still, it is [[conjecture]]d that there are infinitely many Cullen primes.
Still, it is [[conjecture]]d that there are infinitely many Cullen primes.
Line 12: Line 13:


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.

''C<sub>p</sub>'' follows the [[recurrence relation]]
:<math>C_p=4(C_{p-1}+C_{p-2})+1</math>.


== Generalizations ==
== Generalizations ==
Line 21: Line 25:
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).
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>
The least ''n'' such that ''n''·''b''<sup>''n''</sup> + 1 is prime (with question marks if this term is currently unknown) are<ref name="loeh">{{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}}


{|class="wikitable"
{|class="wikitable"
|''b''
!''b''
|numbers ''n'' such that ''n'' × ''b''<sup>''n''</sup> + 1 is prime (these ''n'' are checked up to 101757)
!Numbers ''n'' such that ''n'' × ''b''<sup>''n''</sup> + 1 is prime<ref name="loeh"/>
|[[OEIS]] sequence
![[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)
|{{OEIS link|id=A006093}}
|-
|2
|1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881, ...
|{{OEIS link|id=A005849}}
|-
|-
|3
|3
Line 42: Line 38:
|-
|-
|4
|4
|1, 3, 7, 33, 67, 223, 663, 912, 1383, 3777, 3972, 10669, 48375, ...
|1, 3, 7, 33, 67, 223, 663, 912, 1383, 3777, 3972, 10669, 48375, 1740349, ...
|{{OEIS link|id=A007646}}
|{{OEIS link|id=A007646}}
|-
|-
Line 50: Line 46:
|-
|-
|6
|6
|1, 2, 91, 185, 387, 488, 747, 800, 9901, 10115, 12043, 13118, 30981, 51496, ...
|1, 2, 91, 185, 387, 488, 747, 800, 9901, 10115, 12043, 13118, 30981, 51496, 515516, ..., 4582770
|{{OEIS link|id=A242176}}
|{{OEIS link|id=A242176}}
|-
|-
|7
|7
|34, 1980, 9898, ...
|34, 1980, 9898, 474280, ...
|{{OEIS link|id=A242177}}
|{{OEIS link|id=A242177}}
|-
|-
Line 74: Line 70:
|-
|-
|12
|12
|1, 8, 247, 3610, 4775, 19789, 187895, ...
|1, 8, 247, 3610, 4775, 19789, 187895, 345951, ...
|{{OEIS link|id=A242196}}
|{{OEIS link|id=A242196}}
|-
|-
Line 82: Line 78:
|-
|-
|14
|14
|3, 5, 6, 9, 33, 45, 243, 252, 1798, 2429, 5686, 12509, 42545, ...
|3, 5, 6, 9, 33, 45, 243, 252, 1798, 2429, 5686, 12509, 42545, 1198433, 1486287, 1909683, ...
|{{OEIS link|id=A242197}}
|{{OEIS link|id=A242197}}
|-
|-
Line 98: Line 94:
|-
|-
|18
|18
|1, 3, 21, 23, 842, 1683, 3401, 16839, 49963, 60239, 150940, 155928, ...
|1, 3, 21, 23, 842, 1683, 3401, 16839, 49963, 60239, 150940, 155928, 612497, ...
|{{OEIS link|id=A007648}}
|{{OEIS link|id=A007648}}
|-
|-
Line 106: Line 102:
|-
|-
|20
|20
|3, 6207, 8076, 22356, 151456, ...
|3, 6207, 8076, 22356, 151456, 793181, 993149, ...
|{{OEIS link|id=A338412}}
|{{OEIS link|id=A338412}}
|-
|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, ...
|
|}
|}

<br />


== References ==
== References ==
Line 159: Line 113:
* {{Citation |first=Richard K. |last=Guy |author-link=Richard K. Guy |title=Unsolved Problems in Number Theory |edition=3rd |publisher=[[Springer Verlag]] |location=New York |year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | at=Section B20 }}.
* {{Citation |first=Richard K. |last=Guy |author-link=Richard K. Guy |title=Unsolved Problems in Number Theory |edition=3rd |publisher=[[Springer Verlag]] |location=New York |year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | at=Section B20 }}.
* {{Citation |last=Hooley |first=Christopher |author-link=Christopher Hooley |title=Applications of sieve methods |publisher=[[Cambridge University Press]] |year=1976 |isbn=0-521-20915-3 |pages=115–119 | zbl=0327.10044 | series=Cambridge Tracts in Mathematics | volume=70 }}.
* {{Citation |last=Hooley |first=Christopher |author-link=Christopher Hooley |title=Applications of sieve methods |publisher=[[Cambridge University Press]] |year=1976 |isbn=0-521-20915-3 |pages=115–119 | zbl=0327.10044 | series=Cambridge Tracts in Mathematics | volume=70 }}.
* {{Citation |first=Wilfrid |last=Keller |title=New Cullen Primes |journal=[[Mathematics of Computation]] |volume=64 |issue=212 |year=1995 |pages=1733–1741,S39–S46 |url=https://www.ams.org/mcom/1995-64-212/S0025-5718-1995-1308456-3/S0025-5718-1995-1308456-3.pdf | zbl=0851.11003 | issn=0025-5718 |doi=10.2307/2153382|doi-access=free }}.
* {{Citation |first=Wilfrid |last=Keller |title=New Cullen Primes |journal=[[Mathematics of Computation]] |volume=64 |issue=212 |year=1995 |pages=1733–1741, S39–S46 |url=https://www.ams.org/mcom/1995-64-212/S0025-5718-1995-1308456-3/S0025-5718-1995-1308456-3.pdf | zbl=0851.11003 | issn=0025-5718 |doi=10.2307/2153382|jstor=2153382 |doi-access=free }}.


== External links ==
== External links ==
* Chris Caldwell, [http://primes.utm.edu/top20/page.php?id=6 The Top Twenty: Cullen primes] at The [[Prime Pages]].
* Chris Caldwell, [http://primes.utm.edu/top20/page.php?id=6 The Top Twenty: Cullen primes] at The [[Prime Pages]].
* [http://primes.utm.edu/glossary/page.php?sort=Cullens The Prime Glossary: Cullen number] at The Prime Pages.
* [http://primes.utm.edu/glossary/page.php?sort=Cullens The Prime Glossary: Cullen number] at The Prime Pages.
* Chris Caldwell, [https://primes.utm.edu/top20/page.php?id=42 The Top Twenty: Generalized Cullen] at The Prime Pages.
* {{MathWorld | urlname=CullenNumber | title=Cullen number}}
* {{MathWorld | urlname=CullenNumber | title=Cullen number}}
* [http://www.prothsearch.com/cullen.html Cullen prime: definition and status]{{Dead link|date=July 2020 |bot=InternetArchiveBot |fix-attempted=yes }} (outdated), Cullen Prime Search is now hosted at [[PrimeGrid]]
* [https://web.archive.org/web/20220318135759/http://www.prothsearch.com/cullen.html Cullen prime: definition and status] (outdated), Cullen Prime Search is now hosted at [[PrimeGrid]]
* Paul Leyland, [https://web.archive.org/web/20131219031355/http://www.leyland.vispa.com/numth/factorization/cullen_woodall/cw.html (Generalized) Cullen and Woodall Numbers]
* Paul Leyland, [https://web.archive.org/web/20131219031355/http://www.leyland.vispa.com/numth/factorization/cullen_woodall/cw.html (Generalized) Cullen and Woodall Numbers]


{{Prime number classes|state=collapsed}}
{{Prime number classes|state=collapsed}}
{{Classes of natural numbers}}
{{Classes of natural numbers}}

__NOTOC__


[[Category:Integer sequences]]
[[Category:Integer sequences]]

Latest revision as of 08:46, 30 November 2024

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:

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

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.

Cp follows the recurrence relation

.

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.[2]

As of October 2021, the largest known generalized Cullen prime is 2525532·732525532 + 1. It has 4,705,888 digits and was discovered by Tom Greer, a PrimeGrid participant.[3][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 bp − 1 and bp − 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[5] OEIS sequence
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, 1740349, ... A007646
5 1242, 18390, ...
6 1, 2, 91, 185, 387, 488, 747, 800, 9901, 10115, 12043, 13118, 30981, 51496, 515516, ..., 4582770 A242176
7 34, 1980, 9898, 474280, ... 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, 345951, ... A242196
13 ...
14 3, 5, 6, 9, 33, 45, 243, 252, 1798, 2429, 5686, 12509, 42545, 1198433, 1486287, 1909683, ... 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, 612497, ... A007648
19 6460, ...
20 3, 6207, 8076, 22356, 151456, 793181, 993149, ... A338412

References

  1. ^ 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.
  2. ^ Marques, Diego (2014). "On Generalized Cullen and Woodall Numbers That are Also Fibonacci Numbers" (PDF). Journal of Integer Sequences. 17.
  3. ^ "PrimeGrid Official Announcement" (PDF). Primegrid. 28 August 2021. Retrieved 14 November 2021.
  4. ^ "PrimePage Primes: 2525532 · 73^2525532 + 1". primes.utm.edu. Archived from the original on 2021-09-04. Retrieved 14 November 2021.
  5. ^ a b Löh, Günter (6 May 2017). "Generalized Cullen primes".
  6. ^ Harvey, Steven (6 May 2017). "List of generalized Cullen primes base 101 to 10000".

Further reading