A002586 Smallest prime factor of 2^n + 1. (Formerly M2385 N0947)

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,1

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)

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

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

Example

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

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A023587 A172003 A244801 * A258811 A066845 A014782

Adjacent sequences: A002583 A002584 A002585 * A002587 A002588 A002589

Keyword

nonn,nice,changed

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Jul 06 2000

Definition corrected by Jonathan Sondow, Nov 27 2012

Status

approved