There exist infinitely many Odd Integers such that is Composite for every . Numbers with this property are called Riesel Numbers, and analogous numbers with the minus sign replaced by a plus are called Sierpinski Numbers of the Second Kind. The smallest known Riesel number is , but there remain 963 smaller candidates (the smallest of which is 659) which generate only composite numbers for all which have been checked (Ribenboim 1996, p. 358).
Let be smallest for which is Prime, then the first few values are 2, 0, 2, 1, 1, 2, 3, 1, 2, 1, 1, 4, 3, 1, 4, 1, 2, 2, 1, 3, 2, 7, ... (Sloane's A046069), and second smallest are 3, 1, 4, 5, 3, 26, 7, 2, 4, 3, 2, 6, 9, 2, 16, 5, 3, 6, 2553, ... (Sloane's A046070).
See also Cunningham Number, Mersenne Number, Sierpinski's Composite Number Theorem, Sierpinski Number of the Second Kind
References
Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, p. 357, 1996.
Riesel, H. ``Några stora primtal.'' Elementa 39, 258-260, 1956.
Sloane, N. J. A. Sequences
A046067,
A046068,
A046069, and
A046070
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html.