| Displaying 1-4 of 4 results found.
page
1
Number of prime factors of 2^n + 1 (counted with multiplicity).
+10
29
1, 1, 2, 1, 2, 2, 2, 1, 4, 3, 2, 2, 2, 3, 4, 1, 2, 4, 2, 2, 4, 3, 2, 3, 4, 4, 6, 2, 3, 6, 2, 2, 5, 4, 5, 4, 3, 4, 4, 2, 3, 6, 2, 3, 7, 5, 3, 3, 3, 7, 6, 3, 3, 6, 6, 3, 5, 3, 4, 4, 2, 5, 7, 2, 6, 6, 3, 4, 5, 7, 3, 5, 3, 5, 7, 4, 6, 10, 2, 3, 10, 5, 6, 5, 4, 5, 5, 4, 4, 11, 6, 2, 5, 4, 5, 3, 5, 6, 9, 6, 2, 9, 3
EXAMPLE
a(3) = 2 because 2^3 + 1 = 9 = 3*3.
MATHEMATICA
a[q_] := Module[{x, n}, x=FactorInteger[2^n+1]; n=Length[x]; Sum[Table[x[i]][2]], {i, n}][j]], {j, n}]]
CROSSREFS
Cf. A000051, A002586, A002587, A003260, A001222, A001269, A001348, A054988, A054989, A054990, A054991, A000978. Cf. A046051 (number of prime factors of 2^n-1). Cf. A086257 (number of primitive prime factors).
AUTHOR
Arne Ring (arne.ring(AT)epost.de), May 30 2000
EXTENSIONS
Terms to a(500) in b-file from T. D. Noe, Nov 10 2007 Deleted duplicate (and broken) Wagstaff link. - N. J. A. Sloane, Jan 18 2019
Smallest prime factor of 2^n + 1.
(Formerly M2385 N0947)
+10
15
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
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 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
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
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
Table T(n,k) in which n-th row lists prime factors of 2^n + 1 (n >= 0), without repetition.
+10
4
2, 3, 5, 3, 17, 3, 11, 5, 13, 3, 43, 257, 3, 19, 5, 41, 3, 683, 17, 241, 3, 2731, 5, 29, 113, 3, 11, 331, 65537, 3, 43691, 5, 13, 37, 109, 3, 174763, 17, 61681, 3, 43, 5419, 5, 397, 2113, 3, 2796203, 97, 257, 673, 3, 11, 251, 4051
COMMENTS
Rows have irregular lengths.
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.
LINKS
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
EXAMPLE
Triangle begins:
2;
3;
5;
3,17;
3,11;
5,13;
3,43;
257;
...
MATHEMATICA
Flatten[Table[Transpose[FactorInteger[2^n+1]][[1]], {n, 0, 25}]] (* Harvey P. Dale, Aug 10 2011 *)
CROSSREFS
Cf. A001269 (factors with repetition), A046799 (number of prime divisors).
A list of primes written in order of their first appearance in a table of prime factorizations of 2^k+1, k=1,2,... .
+10
1
3, 5, 17, 11, 13, 43, 257, 19, 41, 683, 241, 2731, 29, 113, 331, 65537, 43691, 37, 109, 174763, 61681, 5419, 397, 2113, 2796203, 97, 673, 251, 4051, 53, 157, 1613, 87211, 15790321, 59, 3033169, 61, 1321, 715827883
COMMENTS
This sequence has the property that if a(n) appears first in the table as a prime factor of 2^m+1 for some m then a(n)=2*k*m+1 for some k.
When, for some m, 2^m+1 has more than one prime factor appearing in the table for the first time, we adopt the convention of entering them in ascending order. For example, the entries ..., 29, 113, ... both arise from 2^14+1.
EXAMPLE
2^1+1=3, 2^2+1=5, 2^3+1=3^2 and 2^4+1=17. Thus a(1)=3, a(2)=5 and a(3)=17, on noting that 2^3+1 contributes no new prime factors.
MATHEMATICA
DeleteDuplicates[Flatten[Table[Transpose[FactorInteger[2^k+1]][[1]], {k, 50}]]] (* Harvey P. Dale, Mar 30 2014 *)
PROG
(PARI) lista(n)=prs = Set(); for (k=1, n, f = factor(2^k+1); for (i=1, length(f~), onef = f[i, 1]; if (! setsearch(prs, onef), print1(onef, ", "); prs = setunion(prs, Set(onef)); ); ); ); \\ Michel Marcus, Apr 18 2013 (PARI) G=1; for(n=1, 500, g=gcd(f=2^n+1, G); while(g>1, g=gcd(g, f/=g)); f=factor(f)[, 1]; if(#f, for(i=1, #f, print1(f[i]", ")); G*=factorback(f))) \\ Charles R Greathouse IV, Jan 03 2018
Search completed in 0.033 seconds
| 