TOPICS
Search

Sierpiński Number of the Second Kind

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A Sierpiński number of the second kind is a number k satisfying Sierpiński's composite number theorem, i.e., a Proth number k such that k·2^n+1 is composite for every n>=1.

The smallest known example is k=78,557, proved in 1962 by J. Selfridge, 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 2003 (Peterson 2003, Helm and Norris). The following table summarizes numbers subsequently found to be prime by "seventeen or bust," leaving only five candidates remaining as of November 2016.

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
Nov. 6, 2016P. Szabolcs10223·2^(31172165)+1

The following table lists the known primes together with the only remaining candidates which, as Jan. 2008, are the six numbers 10223, 21181, 22699, 24737, 55459, and 67607. A list of primes found by the project is also maintained by Caldwell (http://primes.utm.edu/bios/page.php?id=429).

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

Consider now restricting Sierpiński numbers of the second kind to those with prime k. The smallest proved prime Sierpiński number is 271129. A distributed computing project to find examples of k·2^m+1 that are prime with k smaller than the proven lower limit is currently underway (Caldwell). Note that the smallest candidates include three prime candidates from the "seventeen or bust" list: 10223, 22699, 67607. A list of primes found by the project is maintained by Caldwell (http://primes.utm.edu/bios/page.php?id=564).

Let a(k) be smallest n for which (2k-1)·2^n+1 is prime, then 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 n are 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.

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

The smallest odd k such that k+2^n is composite for all n<k are 773, 2131, 2491, 4471, 5101, ... (OEIS A033919).

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

See also

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

Baillie, R.; Cormack, G.; and Williams, H. C. "The Problem of Sierpinski Concerning k·2n+1." Math. Comput. 37, 229-231, 1981.Ballinger, R. "The Sierpinski Problem: Definition and Status." http://www.prothsearch.net/sierp.html.Broadhurst, D. "Might Jean Complexify SoB?" primeform group posting. Oct. 30, 2005. http://groups.yahoo.com/group/primeform/message/6620/.Caldwell, C. "The Prime Sierpinski Problem." http://primes.utm.edu/bios/page.php?id=564.Caldwell, C. "Seventeen or Bust." http://primes.utm.edu/bios/page.php?id=429.Buell, D. A. and Young, J. "Some Large Primes and the Sierpiński Problem." SRC Tech. Rep. 88004, Supercomputing Research Center, Lanham, MD, 1988.Helm, L. Press release upon discovery of 27653×2^(9167433)+1. June 15, 2005. http://www.seventeenorbust.com/documents/press-061505.mhtml.Helm, L. Press release upon discovery of 19249·2^(13018586)+1. May 5, 2007. http://www.seventeenorbust.com/documents/press-050507.mhtml.Helm, L. and Norris, D. "Seventeen or Bust: A Distributed Attack on the Sierpinski Problem." http://www.seventeenorbust.com/.Helm, L. and Norris, D. "Seventeen or Bust: A Distributed Attack on the Sierpinski Problem--Project Statistics." http://www.seventeenorbust.com/stats/.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. http://www.sciencenews.org/20030111/mathtrek.asp."The Prime Sierpinski Project." http://www.mersenneforum.org/showthread.php?t=2665.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 Web Resource. https://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html

Subject classifications