Cullen number

In mathematics, a Cullen number is a natural number of the form $n \cdot 2^n + 1$ (written $C_n$). Cullen numbers were first studied by Fr. James Cullen in 1905. Cullen numbers are special cases of Proth numbers.

Properties

In 1976 Christopher Hooley showed that the natural density of positive integers $n \leq x$ for which C_n is a prime is of the order o(x) for $x\to\infty$. 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 · 2^n+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:

1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881 (sequence A005849 in OEIS).

Still, it is conjectured that there are infinitely many Cullen primes.

As of February 2016, the largest known Cullen prime is 6679881 × 2^6679881 + 1. It is a megaprime with 2,010,852 digits and was discovered by a PrimeGrid participant from Japan.^[2]

A Cullen number C_n 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 C_m(k) for each m(k) = (2^k − 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 C_p is also prime.

Generalizations

Sometimes, a generalized Cullen number base b is defined to be a number of the form n × bⁿ + 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.

According to Fermat 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ⁿ must be congruent to 1 mod p (since bⁿ is a power of b^{p - 1} and b^{p - 1} is congruent to 1 mod p). Thus, n × bⁿ + 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ⁿ + 1 is prime, then b must be divisible by 3 (except b = 1).

Least n such that n × bⁿ + 1 is prime are^[3][4]

1, 1, 2, 1, 1242, 1, 34, 5, 2, 1, 10, 1, ... (sequence A240234 in OEIS)

b	numbers n such that n × b^n + 1 is prime (these n are checked up to 100000)	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, ...	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, ...	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	...
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, ...

As of September 2015, the largest known generalized Cullen prime is 427194 × 113⁴²⁷¹⁹⁴ + 1. It has 877,069 digits and was discovered by a PrimeGrid participant from United States.^[5]

References

1. Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence sequences. Mathematical Surveys and Monographs 104. Providence, RI: American Mathematical Society. p. 94. ISBN 0-8218-3387-1. Zbl 1033.11006.
2. "The Prime Database: 6679881*2^6679881+1", Chris Caldwell's The Largest Known Primes Database, retrieved December 22, 2009
3. List of generalized Cullen primes base 3 to 100
4. List of generalized Cullen primes base 101 to 10000
5. "The Prime Database: 427194 · 113^427194 + 1", Chris Caldwell's The Largest Known Primes Database, retrieved January 30, 2012

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 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 (outdated), Cullen Prime Search is now hosted at PrimeGrid
• Paul Leyland, Generalized Cullen and Woodall Numbers