A046799 -id:A046799 - cp's OEIS frontend

A366636 Number of distinct prime divisors of 7^n + 1.

1, 1, 2, 2, 2, 3, 4, 3, 3, 3, 4, 3, 5, 3, 3, 5, 3, 2, 5, 3, 4, 6, 5, 2, 4, 4, 4, 4, 6, 2, 8, 4, 4, 6, 5, 9, 8, 3, 3, 7, 6, 5, 6, 8, 5, 10, 6, 2, 6, 10, 8, 6, 5, 5, 8, 10, 8, 7, 6, 5, 9, 2, 5, 12, 4, 7, 11, 4, 5, 6, 8, 3, 9, 4, 3, 9, 7, 10, 8, 5, 6, 8, 5, 3, 12

Offset: 0

Sean A. Irvine, Oct 15 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..387

Cf. A034491, A001221, A057937, A227575, A366632, A366637, A366638, A366639.

Cf. A046799, A366580, A366605, A366615, A366627, A366655, A366664, A119704, A366686, A366712.

PrimeNu[7^Range[0,84] + 1] (* Paul F. Marrero Romero, Nov 11 2023 *)

for(n = 0, 100, print1(omega(7^n + 1), ", "))

a(n) = omega(7^n+1) = A001221(A034491(n)).

A366664 Number of distinct prime divisors of 9^n + 1.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 3, 4, 2, 4, 3, 4, 6, 4, 4, 5, 2, 4, 4, 4, 5, 7, 5, 4, 4, 6, 4, 5, 6, 4, 7, 5, 2, 6, 5, 8, 8, 5, 6, 7, 5, 5, 10, 7, 6, 8, 4, 4, 6, 9, 6, 8, 7, 6, 9, 7, 9, 9, 5, 3, 11, 6, 4, 11, 6, 7, 9, 9, 7, 6, 9, 5, 6, 6, 6, 11, 4, 8, 7, 5, 4, 7, 5, 5, 11

Offset: 0

Sean A. Irvine, Oct 15 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 0..345

Cf. A062396, A001221, A057935, A366660, A366665, A366666, A366667.

Cf. A046799, A366580, A366605, A366615, A366627, A366636, A366655, A119704, A366686, A366712.

PrimeNu[9^Range[0,90]+1] (* Harvey P. Dale, Jul 04 2024 *)

for(n = 0, 100, print1(omega(9^n + 1), ", "))

a(n) = omega(9^n+1) = A001221(A062396(n)).

a(n) = A366580(2*n). - Max Alekseyev, Jan 08 2024

A086257 Number of primitive prime factors of 2^n+1.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 1, 1, 2, 2, 1, 2, 2, 3, 2, 2, 2, 3, 1, 1, 2, 2, 1, 2, 1, 4, 2, 2, 1, 3, 3, 2, 2, 2, 2, 2, 2, 2, 3, 1, 1, 4, 1, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 4, 1, 3, 3, 4, 1, 2, 3, 4, 5, 2, 1, 4, 1, 3, 3, 3, 3, 1, 2, 3, 2, 1, 4, 3, 2, 4, 1, 4, 2, 1

Offset: 0

T. D. Noe, Jul 14 2003

A prime factor of 2^n+1 is called primitive if it does not divide 2^r+1 for any rA086258 for those n that have a record number of primitive prime factors.

			a(14) = 2 because 2^14+1 = 5*29*113 and 29 and 113 do not divide 2^r+1 for r < 14.

Max Alekseyev, Table of n, a(n) for n = 0..1128 (terms 0..500 from T. D. Noe; terms 501..1062 from Amiram Eldar)
Eric Weisstein's World of Mathematics, Zsigmondy Theorem

Excluding a(0) = 1, forms a bisection of A086251.

Cf. A046799 (number of distinct prime factors of 2^n+1), A054992 (number of prime factors, with repetition, of 2^n+1), A086258.

nMax=200; pLst={}; Table[f=Transpose[FactorInteger[2^n+1]][[1]]; f=Complement[f, pLst]; cnt=Length[f]; pLst=Union[pLst, f]; cnt, {n, 0, nMax}]

For n > 0, a(n) = A086251(2*n). - Max Alekseyev, Sep 06 2022

A066263 Numbers k such that 2^k + 1 has just two distinct prime factors.

Original entry on oeis.org

5, 6, 7, 9, 10, 11, 12, 13, 17, 19, 20, 23, 28, 31, 32, 40, 43, 61, 64, 79, 92, 101, 104, 127, 128, 148, 167, 191, 199, 256, 313, 347, 356, 596, 692, 701, 1004, 1228, 1268, 1709, 2617, 3539, 3824, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369

Offset: 1

Benoit Cloitre, Dec 31 2001

nonn

From Giuseppe Coppoletta, May 16 2017: (Start)
All terms after a(52) refer to probabilistic primality tests for 2^a(n) + 1 (see Caldwell's link for the list of the largest certified Wagstaff primes). After a(58), 267017, 269987, 374321, 986191, 4031399 and 4101572 are also terms, but there still remains the remote possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much farther in the numbering (see comments in A000978).
For the relation with Fermat numbers and for the primality of odd terms, see comments in A073936. The terms 9 and 10 give a value of 2^n + 1 which is not squarefree, so they are not in A073936. For the rest, the actually known terms of the two sequences coincide. In order to verify if any other term could be found hereafter that is not in A073936, all we have to do is to examine the terms for which 2^n + 1 is not squarefree. Considering that 3 divides 2^a(n) + 1 for any odd term a(n) and using Zsigmondy's and Mihăilescu-Catalan's theorems (see links), one can verify that any nonsquarefree term greater than 9 has to be of the form a(n) = 2^j * Fj, where Fj is the Fermat prime 2^2^j + 1. So basically we have to see if ((Fj-1)^Fj + 1)/(Fj)^2 is a prime or the power of a prime for any Fermat prime Fj. The case j = 1 gives the term a(n) = 10 because (4^5 + 1)/5^2 = 41 is a prime, while for j = 2, (16^17 + 1)/17^2 = 354689 * 2879347902817 is composite. Similarly (256^257 + 1)/257^2 is neither a prime nor the power of a prime, so there is no contribution from the cases j = 2, 3 (see also comments in A127317).
For j = 4 and for any possible other Fermat prime which could be found later, the question is still open, in the sense that it is not actually known if n = 16 * F4 = 1048592 is a term or not. That seems very unlikely, but in order to decide that question for j = 4, one would have to check if (2^1048592 + 1)/65537^2 is a prime or the power of a prime. As this number has 315649 digits, I wonder if it is possible to handle it with the existing primality tests.
(End)

			3 and 4 are not terms because 2^3 + 1 and 2^4 + 1 have only a single prime factor (counted without multiplicity).
6 and 10 are terms because 2^6 + 1 = 5 * 13 and 2^10 + 1 = 5^2 * 41 have two distinct prime factors.

Giuseppe Coppoletta, Table of n, a(n) for n = 1..63
Jack Brennen, Primes of the form (4^p+1)/5^t, Seqfan (Mar 15 2017).
C. Caldwell's The Top Twenty Wagstaff primes.
Mersennewiki, Factorizations Of Cunningham Numbers C+(2,n) (tables).
Samuel S. Wagstaff, The Cunningham Project.
Eric Weisstein's World of Mathematics, Catalan's Conjecture.
Eric Weisstein's World of Mathematics, Zsigmondy Theorem.

Cf. A073936, A107036, A000978, A057182, A127317, A283657, A283364, A092559, A046799.

f[n_] := First[ Transpose[ FactorInteger[2^n + 1]]]; Select[ Range[100], Length[f[ # ]] == 2 & ]
Select[Range[1300],PrimeNu[2^#+1]==2&] (* Harvey P. Dale, Nov 28 2014 *)

isok(k) = #factor(2^k+1)~ == 2; \\ Michel Marcus, Nov 14 2017

A001221(2^a(n) + 1) = 2.

Edited by Robert G. Wilson v, Jan 03 2002

a(40)-a(52) by Giuseppe Coppoletta, May 02 2017

A067886 Numbers k such that 2^k+1 and 2^k-1 have the same number of distinct prime factors.

Original entry on oeis.org

2, 3, 6, 9, 11, 14, 15, 18, 21, 23, 27, 29, 33, 42, 47, 51, 53, 54, 57, 69, 71, 73, 74, 81, 82, 86, 95, 101, 105, 111, 113, 114, 115, 121, 129, 130, 138, 141, 142, 165, 167, 169, 179, 181, 199, 203, 209, 213, 230, 233, 235, 243, 250, 255, 258, 277, 279, 306, 307

Offset: 1

Benoit Cloitre, Mar 02 2002

nonn

Numbers k such that omega(2^k+1) = omega(2^k-1).

Amiram Eldar, Table of n, a(n) for n = 1..141

Cf. A001221, A046799, A046800.

[k: k in [2..307] | #PrimeDivisors(2^k-1) eq #PrimeDivisors(2^k+1) ]; // Marius A. Burtea, Feb 13 2020

sndpQ[n_]:=Module[{c=2^n},PrimeNu[c+1]==PrimeNu[c-1]]; Select[Range[ 250], sndpQ] (* Harvey P. Dale, Feb 04 2016 *)

isok(k) = omega(2^k-1) == omega(2^k+1); \\ Michel Marcus, Feb 13 2020

More terms from Rick L. Shepherd, May 14 2002

More terms from Amiram Eldar, Feb 13 2020

A060444 Table T(n,k) in which n-th row lists prime factors of 2^n + 1 (n >= 0), without repetition.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Rows have irregular lengths.

The length of row n is A046799(n).

			Triangle begins:
  2;
  3;
  5;
  3,17;
  3,11;
  5,13;
  3,43;
  257;
  ...

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.

T. D. Noe, Rows n = 0..500 of triangle, flattened (derived from Brillhart et al.)
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
S. S. Wagstaff, Jr., The Cunningham Project.
Chai Wah Wu, Tables from the Cunningham Project in machine-readable JSON format.

Cf. A001269 (factors with repetition), A046799 (number of prime divisors).

Flatten[Table[Transpose[FactorInteger[2^n+1]][[1]],{n,0,25}]] (* Harvey P. Dale, Aug 10 2011 *)

apply( A060444_row(n)=factor(2^n+1)[,1]~, [0..10]) \\ M. F. Hasler, Nov 19 2018

A283364 Numbers m such that both numbers 2^m +- 1 have at most 2 distinct prime factors.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 17, 19, 23, 31, 61, 101, 127, 167, 199, 347

Offset: 1

Vladimir Shevelev, Mar 06 2017

If a(n) > 9 then a(n) is prime. Proof: If k = 2*m > 9 then 2^(2*m)-1 has at least 3 factors; being 3, (2^m - 1) / 3 and 2^m + 1 which excludes even numbers > 9.
If k = 2*m + 1 > 9 is not prime then k = p*q, q, p > 3 so 2^(p*q) + 1 is divisible by 3, 2^p + 1 and 2^q + 1. If p = q then 2^(p^2) + 1 is divisible by 3, 2^p + 1 and (2^p^2 + 1) / (2^p + 1) > 2^p + 1. Which excludes odd composite numbers > 9 and completes the proof. [comments reworded by David A. Corneth, Nov 23 2019]
Any further terms are > 1122. - Lucas A. Brown, Oct 21 2024

Cf. A001221, A046799, A046800, A067886.

Select[Range@ 200, Times @@ Boole@ Map[PrimeNu@ # <= 2 &, 2^# + {-1, 1}] == 1 &] (* Michael De Vlieger, Mar 06 2017 *)
Select[Range[350],Max[PrimeNu[2^#+{1,-1}]]<3&] (* Harvey P. Dale, Dec 23 2017 *)

isok(n) = omega(2^n+1)<=2 && omega(2^n-1)<=2;
for(n=1, 347, if(isok(n)==1, print1(n,", "))); \\ Indranil Ghosh, Mar 06 2017

More terms from Peter J. C. Moses, Mar 06 2017

A283657 Numbers m such that 2^m + 1 has at most 2 distinct prime factors.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17, 19, 20, 23, 28, 31, 32, 40, 43, 61, 64, 79, 92, 101, 104, 127, 128, 148, 167, 191, 199, 256, 313, 347, 356, 596, 692, 701, 1004, 1228, 1268, 1709, 2617, 3539, 3824, 5807, 10501, 10691, 11279, 12391, 14479

Offset: 1

Vladimir Shevelev, Mar 13 2017

nonn

Using comment in A283364, note that if a(n) is odd > 9, then it is prime.
503 <= a(41) <= 596. - Robert Israel, Mar 13 2017
Could (4^p + 1)/5^t be prime, where p is prime, 5^t is the highest power of 5 dividing 4^p + 1, other than for p=2, 3 and 5? - Vladimir Shevelev, Mar 14 2017
In his message to seqfans from Mar 15 2017, Jack Brennen beautifully proved that there are no more primes of such form. From his proof one can see also that there are no terms of the form 2*p > 10 in the sequence. - Vladimir Shevelev, Mar 15 2017
Where A046799(n)=2. - Robert G. Wilson v, Mar 15 2017
From Giuseppe Coppoletta, May 16 2017: (Start)
The only terms that are not in A066263 are those m giving 2^m + 1 = prime (i.e. m = 0 and any number m such that 2^m + 1 is a Fermat prime) and the values of m giving 2^m + 1 = power of a prime, giving m = 3 as the only possible case (by Mihăilescu-Catalan's result, see links).
For the relation with Fermat numbers and for other possible terms to check, see comments in A073936 and A066263.
All terms after a(59) refer to probabilistic primality tests for 2^a(n) + 1  (see Caldwell's link for the list of the largest certified Wagstaff primes).
After a(65), the values 267017, 269987, 374321, 986191, 4031399 and 4101572 are also terms, but there still remains the remote possibility of some gaps in between. In addition, 13347311 and 13372531 are also terms, but possibly much further along in the numbering (see comments in A000978).
(End).

			0 is a term as 2^0 + 1 = 2 is a prime.
10 is a term as 2^10 + 1 = 5^2 * 41.
14 is not a term as 2^14 + 1 = 5 * 29 * 113.

Giuseppe Coppoletta, Table of n, a(n) for n = 1..65
Jack Brennen, Primes of the form (4^p+1)/5^t, Seqfan (Mar 15 2017).
C. Caldwell's The Top Twenty Wagstaff primes.
Mersennewiki, Factorizations Of Cunningham Numbers C+(2,n) (tables).
Samuel S. Wagstaff, The Cunningham Project.
Eric Weisstein's World of Mathematics, Catalan's Conjecture.
Eric Weisstein's World of Mathematics, Zsigmondy Theorem.

Cf. A002587, A046799, A283364, A073936, A000978, A127317, A092559, A019434, A066263.

Contains 4*A057182.

# this uses A002587[i] for i<=500, e.g., from the b-file for that sequence
count:= 0:
for i from 0 to 500 do
  m:= 0;
  r:= (2^i+1);
  if i::odd then
    m:= 1;
    r:= r/3^padic:-ordp(r,3);
  elif i > 2 then
    q:= max(numtheory:-factorset(i));
    if q > 2 then
      m:= 1;
      r:= r/B[i/q]^padic:-ordp(r,A002587[i/q]);
    fi
  fi;
  if r mod B[i] = 0 then m:= m+1;
      j:= padic:-ordp(r, A002587[i]);
      r:= r/B[i]^j;
  fi;
  mmax:= m;
  if isprime(r) then m:= m+1; mmax:= m
  elif r > 1 then mmax:= m+2
  fi;
  if mmax <= 2 or (m <= 1 and m + nops(numtheory:-factorset(r)) <= 2) then
       count:= count+1;
     A[count]:= i;
  fi
od:
seq(A[i],i=1..count); # Robert Israel, Mar 13 2017

Select[Range[0, 313], PrimeNu[2^# + 1]<3 &] (* Indranil Ghosh, Mar 13 2017 *)

for(n=0, 313, if(omega(2^n + 1)<3, print1(n,", "))) \\ Indranil Ghosh, Mar 13 2017

a(16)-a(38) from Peter J. C. Moses, Mar 13 2017
a(39)-a(40) from Robert Israel, Mar 13 2017
a(41)-a(65) from Giuseppe Coppoletta, May 08 2017

A337811 Numbers k such that the number of distinct prime factors of 2^k - 1 is less than the corresponding count for 2^k + 1.

Original entry on oeis.org

1, 5, 7, 13, 17, 19, 25, 26, 31, 34, 35, 37, 38, 41, 46, 49, 59, 61, 62, 65, 67, 77, 78, 83, 85, 89, 91, 93, 97, 98, 103, 107, 109, 118, 122, 123, 125, 127, 131, 133, 134, 137, 139, 143, 145, 147, 149, 153, 157, 170, 173, 175, 177, 185, 186, 189, 193, 194, 195

Offset: 1

Hugo Pfoertner, Sep 23 2020

nonn

Cf. A046799, A046800, A067886, A337810, A337812, A337813.

Select[Range[200],PrimeNu[2^#-1]Harvey P. Dale, Nov 04 2023 *)

PARI
```
for(n=1,200,if(omega(2^n-1)
				
```

A337813 Numbers k such that the number of distinct prime factors of 2^k - 1 is greater than the corresponding count for 2^k + 1.

Original entry on oeis.org

4, 8, 10, 12, 16, 20, 22, 24, 28, 30, 32, 36, 39, 40, 43, 44, 45, 48, 50, 52, 55, 56, 58, 60, 63, 64, 66, 68, 70, 72, 75, 76, 79, 80, 84, 87, 88, 90, 92, 94, 96, 99, 100, 102, 104, 106, 108, 110, 112, 116, 117, 119, 120, 124, 126, 128, 132, 135, 136, 140, 144

Offset: 1

Hugo Pfoertner, Sep 23 2020

nonn

Cf. A046799, A046800, A067886, A337810, A337811, A337812.

for(n=1,150,if(omega(2^n-1)>omega(2^n+1),print1(n,", ")))

cp's OEIS Frontend

A366636 Number of distinct prime divisors of 7^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A366664 Number of distinct prime divisors of 9^n + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A086257 Number of primitive prime factors of 2^n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A066263 Numbers k such that 2^k + 1 has just two distinct prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A067886 Numbers k such that 2^k+1 and 2^k-1 have the same number of distinct prime factors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A060444 Table T(n,k) in which n-th row lists prime factors of 2^n + 1 (n >= 0), without repetition.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A283364 Numbers m such that both numbers 2^m +- 1 have at most 2 distinct prime factors.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A283657 Numbers m such that 2^m + 1 has at most 2 distinct prime factors.