Sierpinski Number of the Second Kind

A number $k$ satisfying Sierpinski's Composite Number Theorem, i.e., such that $k\cdot 2^n+1$ is Composite for every $n\geq 1$. The smallest known is $k=78{,}557$, but there remain 35 smaller candidates (the smallest of which is 4847) which are known to generate only composite numbers for $n\leq 18,000$ or more (Ribenboim 1996, p. 358).

Let $a(k)$ be smallest $n$ for which $(2k-1)\cdot 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, ... (Sloane's 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, ... (Sloane's 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\cdot 2^n+1$ is $383\cdot 2^{6393}+1$. There are an infinite number of Sierpinski 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, ....

See also Mersenne Number, Riesel Number, Sierpinski's Composite Number Theorem

References

Buell, D. A. and Young, J. ``Some Large Primes and the Sierpinski Problem.'' SRC Tech. Rep. 88004, Supercomputing Research Center, Lanham, MD, 1988.

Jaeschke, G. ``On the Smallest $k$ such that $k\cdot 2^N+1$ are Composite.'' Math. Comput. 40, 381-384, 1983.

Jaeschke, G. Corrigendum to ``On the Smallest $k$ such that $k\cdot 2^N+1$ are Composite.'' Math. Comput. 45, 637, 1985.

Keller, W. ``Factors of Fermat Numbers and Large Primes of the Form $k\cdot 2^n+1$.'' Math. Comput. 41, 661-673, 1983.

Keller, W. ``Factors of Fermat Numbers and Large Primes of the Form $k\cdot 2^n+1$, II.'' In prep.

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 357-359, 1996.

Sierpinski, W. ``Sur un problème concernant les nombres $k\cdot 2^n+1$.'' Elem. d. Math. 15, 73-74, 1960.

Sloane, N. J. A. A046067 and A046068 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.