TOPICS
Search

Cunningham Number

A Cunningham number is a binomial number of the form C^+/-(b,n)=b^n+/-1 with positive integers b>1 and n. Bases which are perfect powers b^k, with k>1, need not be considered since they correspond to (b^k)^n+/-1=b^(kn)+/-1. Prime numbers of the form C^+/-(b,n) are very rare.

A necessary (but not sufficient) condition for C^+(2,n)=2^n+1 to be prime is that n be of the form n=2^m for a nonnegative integer m. Numbers of the form F_m=C^+(2,2^m)=2^(2^m)+1 are called Fermat numbers, and the only known primes occur for C^+(2,1)=3, C^+(2,2)=5, C^+(2,4)=17, C^+(2,8)=257, and C^+(2,16)=65537 (i.e., m=0, 1, 2, 3, 4). The only other primes C^+(b,n) for bases b<=11 that are not perfect powers and 2<=n<=1000 are C^+(6,2)=37, C^+(6,4)=1297, and C^+(10,2)=101.

C^+(2,n)=2^n+1 is always divisible by 3 when n is odd.

Primes of the form C^-(b,n) are also very rare. The Mersenne numbers M_n=C^-(2,n)=2^n-1 are known to be prime for 52 values of n as of Oct. 2026 (Great Internet Mersenne Prime Search), the first few of which are n=2, 3, 5, 7, 13, 17, 19, ... (OEIS A000043). Such numbers are known as Mersenne primes. There are no other primes C^-(b,n) for bases b<=20 that are not perfect powers and 2<=n<=1000.

Cunningham and Woodall (1925) gathered together all that was known about which numbers C^+/-(b,n) are prime and about their factorizations and published a small book of tables. These tables collected from scattered sources the known prime factors for the bases 2 and 10 and also presented the authors' results of 30 years' work with these and other bases.

Since 1925, many people have worked on filling in these tables. D. H. Lehmer, a well-known mathematician who died in 1991, was for many years a leader of these efforts. Lehmer was a mathematician who was at the forefront of computing as modern electronic computers became a reality. He was also known as the inventor of some ingenious pre-electronic computing devices specifically designed for factoring numbers.

Updated factorizations were published in Brillhart et al. (1988). The tables have been extended by Brent and te Riele (1992) to 13<=b<100, with b^n<10^(255) for b<30 and n<=100 for b>=30. In these tables, all entries with n<=46 were completely factored, and every remaining composite cofactor had at least 81 decimal digits.

See also

Binomial Number, Cullen Number, Fermat Number, Mersenne Number, Proth Number, Repunit, Riesel Number, Sierpiński Number of the First Kind, Woodall Number

Explore with Wolfram|Alpha

References

Brent, R. P. and te Riele, H. J. J. "Factorizations of a^n+/-1, 13<=a<100." Report NM-R9212. Amsterdam, Netherlands: Centrum voor Wiskunde en Informatica, 1992. https://maths-people.anu.edu.au/~brent/pub/pub134.html.Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Tuckerman, B.; and Wagstaff, S. S. Jr. Factorizations of bn±1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, 2nd ed. Providence, RI: Amer. Math. Soc., 1988. https://pubs.ams.org/ebooks/conm/022/.Cunningham, A. J. C. and Woodall, H. J. Factorisation of yn∓1, y=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers (n). London, England: Hodgson, 1925.Great Internet Mersenne Prime Search. "List of Known Mersenne Prime Numbers." https://www.mersenne.org/primes/.Mudge, M. "Not Numerology but Numeralogy!" Personal Computer World, 279-280, 1997.Ribenboim, P. "Numbers k×2^n+/-1." §5.7 in The New Book of Prime Number Records. New York: Springer-Verlag, pp. 355-360, 1996.Sloane, N. J. A. Sequence A000043/M0672 in "The On-Line Encyclopedia of Integer Sequences."Wagstaff, S. S. Jr. "The Cunningham Project." https://homes.cerias.purdue.edu/~ssw/cun/.Wagstaff, S. S. Jr. "The Third Edition of the Cunningham Books." https://homes.cerias.purdue.edu/~ssw/cun/third/.

Referenced on Wolfram|Alpha

Cunningham Number

Cite this as:

Weisstein, Eric W. "Cunningham Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CunninghamNumber.html

Subject classifications