A002586 Smallest prime factor of 2^n + 1.

3, 5, 3, 17, 3, 5, 3, 257, 3, 5, 3, 17, 3, 5, 3, 65537, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5, 3, 641, 3, 5, 3, 17, 3, 5, 3, 257, 3, 5, 3, 17, 3, 5, 3, 193, 3, 5, 3, 17, 3, 5, 3, 257, 3, 5, 3, 17, 3, 5, 3, 274177, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5, 3, 65537, 3, 5, 3, 17, 3, 5

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Conjecture: a(8+48*k) = 257 and a(40+48*k) = 257, where k is a nonnegative integer. - Thomas König, Feb 15 2017

Conjecture is true: 257 divides 2^(8+48*k)+1 and 2^(40+48*k)+1 but no prime < 257 ever does. Similarly, a(24+48*k) = 97. - Robert Israel, Feb 17 2017

From Robert Israel, Feb 17 2017: (Start)

If a(n) = p, there is some m such that a(n+m*j*n) = p for all j.

In particular, every member of the sequence occurs infinitely often.

a(k*n) <= a(n) for any odd k. (End)

Examples

			a(2^k) = 3, 5, 17, 257, 65537 is the k-th Fermat prime 2^(2^k) + 1 = A019434(k) for k = 0, 1, 2, 3, 4. - _Jonathan Sondow_, Nov 28 2012
		

References

• J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
• M. Kraitchik, Recherches sur la Théorie des Nombres, Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 2, p. 85.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Max Alekseyev, Table of n, a(n) for n = 1..3967 (first 500 terms from T. D. Noe)
• J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
• Thomas König, C program using gmp for testing the conjectures that a(8+k*48) = 257 and a(40+k*48) = 257
• E. Lucas, Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240, 289-321. See pages 239 and 240.
• Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.
• S. S. Wagstaff, Jr., The Cunningham Project

Crossrefs

Cf. A000215, A001269, A002587, A019434, A050922, A093179.

Programs

Mathematica

f[n_] := FactorInteger[2^n + 1][[1, 1]]; Array[f, 100] (* Robert G. Wilson v, Nov 28 2012 *)
FactorInteger[#][[1,1]]&/@(2^Range[90]+1) (* Harvey P. Dale, Jul 25 2024 *)

PARI

a(n) = my(m=n%8); if(m, [3, 5, 3, 17, 3, 5, 3][m], factor(2^n+1)[1,1]); \\ Ruud H.G. van Tol, Feb 16 2024

Python

from sympy import primefactors
smallest_primef = []
for n in range(1,87):
    y = (2 ** n) + 1
    smallest_primef.append(min(primefactors(y)))
print(smallest_primef) # Adrienne Leonardo, Dec 29 2024

Formula

a(n) = 3, 5, 3, 17, 3, 5, 3 for n == 1, 2, 3, 4, 5, 6, 7 (mod 8). (Proof. Let n = k*odd with k = 1, 2, or 4. As 2^k = 2, 4, 16 == -1 (mod 3, 5, 17), we get 2^n + 1 = 2^(k*odd) + 1 = (2^k)^odd + 1 == (-1)^odd + 1 == 0 (mod 3, 5, 17). Finally, 2^n + 1 !== 0 (mod p) for prime p < 3, 5, 17, respectively.) - Jonathan Sondow, Nov 28 2012

Extensions

More terms from James Sellers, Jul 06 2000

Definition corrected by Jonathan Sondow, Nov 27 2012