TOPICS
Search

Sierpiński Number of the Second Kind

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A Sierpiński number of the second kind is an odd positive integer k such that k·2^n+1 is composite for every positive integer n.

The smallest known example is k=78,557, proved by J. Selfridge in 1962 (Baillie et al. 1981, p. 229), but the fate of a number of smaller candidates remains to be determined before this number can be established as the smallest such number. As of 1996, 35 candidates remained (Ribenboim 1996, p. 358), a number which had been reduced to 17 by the beginning of 2002 (Peterson 2003).

In March 2002, L. K. Helm and D. A. Norris began a distributed computing effort dubbed "seventeen or bust" to eliminate the remaining candidates. With the aid of collaborators across the globe, this number was reduced to 12 as of December 2002 (Peterson 2003, Helm and Norris). The following table summarizes numbers subsequently found to be prime by "seventeen or bust" and its successor PrimeGrid subproject, leaving five candidates as of Oct. 2026 (PrimeGrid).

dateparticipantnumber
Dec. 6, 20035359·2^(5054502)+1
Jun. 8, 2005D. Gordon27653·2^(9167433)+1
Oct. 15, 2005R. Hassler4847·2^(3321063)+1
May 5, 2007K. Agafonov19249·2^(13018586)+1
Oct. 30, 2007S. Sunde33661·2^(7031232)+1
Oct. 31, 2016P. Szabolcs10223·2^(31172165)+1

The following table lists the known primes together with the five remaining candidates as of Oct. 2026, namely 21181, 22699, 24737, 55459, and 67607. A list of primes found by the project is also maintained by Caldwell (https://t5k.org/bios/page.php?id=429).

kprimedigitsCaldwell
48474847·2^(3321063)+1999744https://t5k.org/primes/page.php?id=75994
53595359·2^(5054502)+11521561https://t5k.org/primes/page.php?id=67719
1022310223·2^(31172165)+19383761https://t5k.org/primes/page.php?id=122473
1924919249·2^(13018586)+13918990https://t5k.org/primes/page.php?id=80385
21181
22699
24737
2765327653·2^(9167433)+12759677https://t5k.org/primes/page.php?id=74836
2843328433·2^(7830457)+12357207https://t5k.org/primes/page.php?id=73145
3366133661·2^(7031232)+12116617https://t5k.org/primes/page.php?id=82804
4413144131·2^(995972)+1299823https://t5k.org/primes/page.php?id=62867
4615746157·2^(698207)+1210186https://t5k.org/primes/page.php?id=62865
5476754767·2^(1337287)+1402569https://t5k.org/primes/page.php?id=62869
55459
6556765567·2^(1013803)+1305190https://t5k.org/primes/page.php?id=62866
67607
6910969109·2^(1157446)+1348431https://t5k.org/primes/page.php?id=62868

Consider now restricting Sierpiński numbers of the second kind to those with prime k. The smallest known prime Sierpiński number is 271129. Searches test smaller prime multipliers k by seeking primes of the form k·2^m+1 (Caldwell). As of Oct. 2026, the remaining candidates include two prime candidates from the "seventeen or bust" list, 22699 and 67607. A list of primes found by the project is maintained by Caldwell (https://t5k.org/bios/page.php?id=564).

For a positive integer k, let a(k) be the smallest nonnegative integer n for which (2k-1)·2^n+1 is prime, with a(k)=-1 if no such n exists. The first few values are 0, 1, 1, 2, 1, 1, 2, 1, 3, 6, 1, 1, 2, 2, 1, 8, 1, 1, 2, 1, 1, 2, 2, 583, ... (OEIS A046067). The second smallest such n, with value -1 if it does not exist, is given by 1, 2, 3, 4, 2, 3, 8, 2, 15, 10, 4, 9, 4, 4, 3, 60, 6, 3, 4, 2, 11, 6, 9, 1483, ... (OEIS A046068). Quite large n can be required to obtain the first prime even for small k. For example, the smallest prime of the form 383·2^n+1 is 383·2^(6393)+1 (Baillie et al. 1981, p. 230).

There are an infinite number of Sierpiński numbers which are prime.

The smallest odd positive integers k such that k+2^n is composite for every integer n with 0<=n<k are 773, 2131, 2491, 4471, 5101, ... (OEIS A033919).

For integers n>=1 and Gaussian integers k=10+3i, 25+3i, or 40+3i, k·2^n+1 is never a Gaussian prime (E. Pegg, Jr., pers. comm., Feb. 6, 2003; Broadhurst 2005).

See also

Brier Number, Colbert Number, Mersenne Number, Pierpont Prime, Prime Number, Proth Number, Riesel Number, Sierpiński's Composite Number Theorem, Titanic Prime

Explore with Wolfram|Alpha

References

--. "The Prime Sierpinski Project." https://www.mersenneforum.org/node/2328.Baillie, R.; Cormack, G.; and Williams, H. C. "The Problem of Sierpiński Concerning k·2^n+1." Math. Comput. 37, 229-231, 1981. https://doi.org/10.1090/S0025-5718-1981-0616376-2.Ballinger, R. "The Sierpinski Problem: Definition and Status." http://www.prothsearch.com/sierp.html.Update a linkBroadhurst, D. "Might Jean Complexify SoB?" primeform group posting. Oct. 30, 2005. http://groups.yahoo.com/group/primeform/message/6620/Buell, D. A. and Young, J. "Some Large Primes and the Sierpiński Problem." SRC Tech. Rep. 88004, Supercomputing Research Center, Lanham, MD, 1988.Caldwell, C. "The Prime Sierpinski Problem." https://t5k.org/bios/page.php?id=564.Caldwell, C. "Seventeen or Bust." https://t5k.org/bios/page.php?id=429.Helm, L. and Norris, D. "Seventeen or Bust: A Distributed Attack on the Sierpinski Problem." https://web.archive.org/web/20160405211049/http://seventeenorbust.com:80/.Helm, L. and Norris, D. "Seventeen or Bust: A Distributed Attack on the Sierpinski Problem--Project Statistics." https://web.archive.org/web/20160321082846/http://www.seventeenorbust.com/stats/.Helm, L. Press release upon discovery of 19249·2^(13018586)+1. May 5, 2007. https://web.archive.org/web/20070630235507/http://www.seventeenorbust.com/documents/press-050507.mhtml.Helm, L. Press release upon discovery of 27653×2^(9167433)+1. June 15, 2005. https://web.archive.org/web/20051023071359/http://www.seventeenorbust.com/documents/press-061505.mhtml.Jaeschke, G. "On the Smallest k Such That k·2^N+1 Are Composite." Math. Comput. 40, 381-384, 1983.Jaeschke, G. Corrigendum to "On the Smallest k Such That k·2^N+1 Are Composite." Math. Comput. 45, 637, 1985.Keller, W. "Factors of Fermat Numbers and Large Primes of the Form k·2^n+1." Math. Comput. 41, 661-673, 1983.Keller, W. "Factors of Fermat Numbers and Large Primes of the Form k·2^n+1, II." In prep.Peterson, I. "MathTrek: A Remarkable Dearth of Primes." Jan. 13, 2003. https://www.sciencenews.org/article/remarkable-dearth-primes.PrimeGrid. "Seventeen or Bust Subproject." 2016. https://www.primegrid.com/download/SOB-31172165.pdf.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 357-359, 1996.Sierpiński, W. "Sur un problème concernant les nombres k·2^n+1." Elem. d. Math. 15, 73-74, 1960.Sloane, N. J. A. Sequences A033919, A046067, and A046068 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Sierpiński Number of the Second Kind

Cite this as:

Weisstein, Eric W. "Sierpiński Number of the Second Kind." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html

Subject classifications