cp's OEIS Frontend

A076336 (Provable) Sierpiński numbers: odd numbers n such that for all k >= 1 the numbers n*2^k + 1 are composite.

%I A076336 #164 Apr 25 2025 05:28:47
%S A076336 78557,271129,271577,322523,327739,482719,575041,603713,903983,934909,
%T A076336 965431,1259779,1290677,1518781,1624097,1639459,1777613,2131043,
%U A076336 2131099,2191531,2510177,2541601,2576089,2931767,2931991,3083723,3098059,3555593,3608251
%N A076336 (Provable) Sierpiński numbers: odd numbers n such that for all k >= 1 the numbers n*2^k + 1 are composite.
%C A076336 "Provable" in the definition means provable by any method (whether using a covering set or not). - _N. J. A. Sloane_, Aug 03 2024
%C A076336 It is only a conjecture that this sequence is complete up to 3000000 - there may be missing terms.
%C A076336 It is conjectured that 78557 is the smallest Sierpiński number. - _T. D. Noe_, Oct 31 2003
%C A076336 Sierpiński numbers may be proved by exhibiting a periodic sequence p of prime divisors with p(k) | n*2^k+1 and disproved by finding a prime n*2^k+1. It is conjectured by some people that numbers that cannot be proved to be Sierpiński by this method are non-Sierpiński. However, some numbers resist both proof and disproof. - _David W. Wilson_, Jan 17 2005 [Edited by _N. J. A. Sloane_, Aug 03 2024]
%C A076336 Sierpiński showed that this sequence is infinite.
%C A076336 There are four related sequences that arise in this context:
%C A076336 S1: Numbers n such that n*2^k + 1 is composite for all k (this sequence)
%C A076336 S2: Odd numbers n such that 2^k + n is composite for all k (apparently it is conjectured that S1 and S2 are the same sequence)
%C A076336 S3: Numbers n such that n*2^k + 1 is prime for all k (empty)
%C A076336 S4: Numbers n such that 2^k + n is prime for all k (empty)
%C A076336 The following argument, due to Michael Reid, attempts to show that S3 and S4 are empty: If p is a prime divisor of n + 1, then for k = p - 1, the term (either n*2^k + 1 or 2^k + n) is a multiple of p (and also > p, so not prime). [However, David McAfferty points that for the case S3, this argument fails if p is of the form 2^m-1. So it may only be a conjecture that the set S3 is empty. - _N. J. A. Sloane_, Jun 27 2021]
%C A076336 a(1) = 78557 is also the smallest odd n for which either n^p*2^k + 1 or n^p + 2^k is composite for every k > 0 and every prime p greater than 3. - _Arkadiusz Wesolowski_, Oct 12 2015
%C A076336 n = 4008735125781478102999926000625 = (A213353(1))^4 is in this sequence but is thought not to satisfy the conjecture mentioned by _David W. Wilson_ above. For this multiplier, all n*2^(4m + 2) + 1 are composite by an Aurifeuillean factorization. Only the remaining cases, n*2^k + 1 where k is not 2 modulo 4, are covered by a finite set of primes (namely {3, 17, 97, 241, 257, 673}). See Izotov link for details (although with another prime set). - _Jeppe Stig Nielsen_, Apr 14 2018
%C A076336 Conjecture: if S is a (provable) Sierpiński number, then there exists a prime P such that S^p is also a Sierpiński number for every prime p > P. - _Thomas Ordowski_, Jul 12 2022
%C A076336 Problem: are there odd numbers K such that K - 2^m is a Sierpiński number for every 1 < 2^m < K? If so, then all positive values of (K - 2^m)*2^n + 1 are composite. Also, by the dual Sierpiński conjecture, K - 2^m + 2^n is composite for every 1 < 2^m < K and for every n > 0. Note that, by the dual Sierpiński conjecture, if p is an odd prime and 1 < 2^m < p, then there exists n such that (p - 2^m)*2^n + 1 is prime. So if such a number K exists, it must be composite. - _Thomas Ordowski_, Jul 20 2022
%C A076336 From _M. F. Hasler_, Jul 23 2022: (Start)
%C A076336 1) The above Conjecture is true for Sierpiński numbers provable by a "covering set", with P equal to the largest prime factor of the elements of that set*, according to the explanation from Michael Filaseta posted Jul 12 2022 on the SeqFan mailing list, cf. links. (*More generally: for S^p with any p coprime to all elements of the covering set, but not necessarily prime.)
%C A076336 2) Wilson's comment from 2005 (also the first part, not only the conjecture) is misleading if not wrong because there are provable Sierpiński numbers for which a covering set is not known (maybe even believed not to exist), as explained by Nielsen in his above comment from 2018. (End)
%D A076336 R. K. Guy, Unsolved Problems in Number Theory, Section B21.
%D A076336 C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 420.
%D A076336 Paulo Ribenboim, The Book of Prime Number Records, 2nd. ed., 1989, p. 282.
%D A076336 Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 237-238.
%H A076336 T. D. Noe and Arkadiusz Wesolowski, <a href="/A076336/b076336.txt">Table of n, a(n) for n = 1..15000</a> (T. D. Noe supplied 13394 terms which came from McLean. a(1064), a(7053), and a(13397)-a(15000) from Arkadiusz Wesolowski.)
%H A076336 Chris Caldwell, <a href="https://t5k.org/glossary/page.php?sort=RieselNumber">Riesel number</a>
%H A076336 Chris Caldwell, <a href="https://t5k.org/glossary/page.php?sort=SierpinskiNumber">Sierpinski number</a>
%H A076336 Michael Filaseta, quoted by T. Ordowski, <a href="https://web.archive.org/web/*/http://list.seqfan.eu/oldermail/seqfan/2022-July/021539.html">Re: Is it true?</a> SeqFan mailing list, Jul 12 2022
%H A076336 Michael Filaseta, Jacob Juillerat, and Thomas Luckner, <a href="https://arxiv.org/abs/2209.10646">Consecutive primes which are widely digitally delicate and Brier numbers</a>, arXiv:2209.10646 [math.NT], 2022.
%H A076336 Carrie E. Finch-Smith and R. Scottfield Groth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Finch/finchs1.html">Arbitrarily Long Sequences of Sierpiński Numbers that are the Sum of a Sierpiński Number and a Mersenne Number</a>, Journal of Integer Sequences, Vol. 28 (2025), Article 25.2.4. See p. 22.
%H A076336 Yves Gallot, <a href="http://yves.gallot.pagesperso-orange.fr/papers/smallbrier.pdf">A search for some small Brier numbers</a>, 2000.
%H A076336 Dan Ismailescu and Peter Seho Park, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.html">On Pairwise Intersections of the Fibonacci, Sierpiński, and Riesel Sequences</a>, Journal of Integer Sequences, 16 (2013), #13.9.8.
%H A076336 Anatoly S. Izotov, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/33-3/izotov.pdf">A Note on Sierpinski Numbers</a>, Fibonacci Quarterly (1995), pp. 206-207.
%H A076336 G. Jaeschke, <a href="http://www.jstor.org/stable/2007382">On the Smallest k Such that All k*2^N + 1 are Composite</a>, Mathematics of Computation, Vol. 40, No. 161 (Jan., 1983), pp. 381-384.
%H A076336 J. McLean, <a href="/A076336/a076336a.html">Searching for large Sierpinski numbers</a> [Cached copy]
%H A076336 J. McLean, <a href="/A076336/a076336b.html">Brier Numbers</a> [Cached copy]
%H A076336 Don Reble, <a href="/A076336/a076336.pdf">Proofs concerning S3 and S4</a>
%H A076336 Carlos Rivera, <a href="http://www.primepuzzles.net/problems/prob_029.htm">Problem 29. Brier numbers</a>, The Prime Puzzles and Problems Connection.
%H A076336 Payam Samidoost, <a href="http://sierpinski.insider.com/dual">Dual Sierpinski problem search page</a> [Broken link?]
%H A076336 Payam Samidoost, <a href="/A076336/a076336c.html">Dual Sierpinski problem search page</a> [Cached copy]
%H A076336 Payam Samidoost, <a href="http://sierpinski.insider.com/4787">4847</a> [Broken link?]
%H A076336 Payam Samidoost, <a href="/A076336/a076336d.html">4847</a> [Cached copy]
%H A076336 W. Sierpiński, <a href="http://dx.doi.org/10.5169/seals-20713">Sur un problème concernant les nombres k * 2^n + 1</a>, Elem. Math., 15 (1960), pp. 73-74.
%H A076336 Seventeen or Bust, <a href="http://www.seventeenorbust.com/">A Distributed Attack on the Sierpinski Problem</a>
%H A076336 N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=3RAYoaKMckM">A Nasty Surprise in a Sequence and Other OEIS Stories</a>, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/sloane85BD.pdf">Slides</a> [Mentions this sequence]
%H A076336 Jeremiah T. Southwick, <a href="https://scholarcommons.sc.edu/etd/5879/">Two Inquiries Related to the Digits of Prime Numbers</a>, Ph. D. Dissertation, University of South Carolina (2020).
%H A076336 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html">Sierpiński Number of the Second Kind</a>
%H A076336 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sierpi%C5%84ski_number">Sierpiński number</a>.
%Y A076336 Cf. A003261, A052333, A076335, A076337, A101036, A137715, A263169, A305473, A306151.
%K A076336 nonn,hard,nice
%O A076336 1,1
%A A076336 _N. J. A. Sloane_, Nov 07 2002