A086251 -id:A086251 - cp's OEIS frontend

A046800 Number of distinct prime factors of 2^n-1.

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

Offset: 0

Labos Elemer

nonn

			a(6) = 2 because 63 = 3*3*7 has 2 distinct prime factors.

Amiram Eldar, Table of n, a(n) for n = 0..1206 (terms 1..500 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.
Abílio Lemos and Ady Cambraia Junior, On the number of prime factors of Mersenne numbers (2016)

Length of row n of A060443.

Cf. A000225, A046051 (number of prime factors, with repetition, of 2^n-1), A086251.

A046800 := proc(n)
    if n <= 1 then
        0;
    else
        numtheory[factorset](2^n-1) ;
        nops(%) ;
    end if;
end proc:
seq(A046800(n),n=0..100) ; # R. J. Mathar, Nov 10 2017

Table[Length[ FactorInteger [ 2^n -1 ] ], {n, 0, 100}]
Join[{0},PrimeNu/@(2^Range[110]-1)] (* Harvey P. Dale, Mar 09 2015 *)

a(n)=omega(2^n-1) \\ Charles R Greathouse IV, Nov 17 2014

a(n) = Sum_{d|n} A086251(d), Mobius transform of A086251.
a(n) < 0.7 * n; the constant 0.7 cannot be improved below log 2 using only the size of 2^n-1. - Charles R Greathouse IV, Apr 12 2012
a(n) = A001221(2^n-1). - R. J. Mathar, Nov 10 2017

Edited by T. D. Noe, Jul 14 2003

A182590 Number of distinct prime factors of 2^n - 1 of the form k*n + 1.

Original entry on oeis.org

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

Offset: 2

Seppo Mustonen, Nov 22 2010

nonn

From Thomas Ordowski, Sep 08 2017: (Start)
By Bang's theorem, a(n) > 0 for all n > 1, see A186522.
Primes p such that a(p) = 1 are the Mersenne exponents A000043.
Composite numbers m for which a(m) = 1 are A292079.
a(n) >= A086251(n), where equality is for all prime numbers and for some composite numbers (among others for all odd prime powers p^k with k > 1).
Theorem: if n is prime, then a(n) = A046800(n).
Conjecture: if a(n) = A046800(n), then n is prime.
Problem: is a(n) < A046800(n) for every composite n? (End)

			For n=10 the prime factors of 2^n - 1 = 1023 are 3, 11 and 31, and 11 = n+1, 31 = 3n+1. Thus a(10)=2.

Charles R Greathouse IV, Table of n, a(n) for n = 2..1200 (terms 2..200 from Seppo Mustonen, terms 201..786 from Michel Marcus)
S. Mustonen, On prime factors of numbers m^n+-1, 2010.
Seppo Mustonen, On prime factors of numbers m^n+-1 [Local copy]

Cf. A046800, A086251, A186522.

m = 2; n = 2; nmax = 200;
While[n <= nmax, {l = FactorInteger[m^n - 1]; s = 0;
     For[i = 1, i <= Length[l],
      i++, {p = l[[i, 1]];
       If[IntegerQ[(p - 1)/n] == True, s = s + l[[i, 2]]];}];
     a[n] = s;} n++;];
Table[a[n], {n, 2, nmax}]

a(n) = my(f = factor(2^n-1)); sum(k=1, #f~, ((f[k,1]-1) % n)==0); \\ Michel Marcus, Sep 10 2017

Name edited by Thomas Ordowski, Sep 19 2017

A161508 Numbers k such that 2^k-1 has only one primitive prime factor.

Original entry on oeis.org

2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 26, 27, 30, 31, 32, 33, 34, 38, 40, 42, 46, 49, 54, 56, 61, 62, 65, 69, 77, 78, 80, 85, 86, 89, 90, 93, 98, 107, 120, 122, 126, 127, 129, 133, 145, 147, 150, 158, 165, 170, 174, 184, 192, 195, 202, 208

Offset: 1

T. D. Noe, Jun 17 2009

nonn

Also, numbers k such that A086251(k) = 1.
Also, numbers k such that A064078(k) is a prime power.
The corresponding primitive primes are listed in A161509.
The binary expansion of 1/p has period k and this is the only prime with such a period. The binary analog of A007498.
This sequence has many terms in common with A072226. A072226 has the additional term 6; but it does not have terms 18, 20, 21, 54, 147, 342, 602, and 889 (less than 10000).
All known terms that are not in A072226 belong to A333973.

T. D. Noe, Table of n, a(n) for n=1..179
Wikipedia, Unique prime, section Binary unique primes.

Cf. A007498, A064078, A072226, A086251, A144755, A161509, A247071, A333973.

Select[Range[1000], PrimePowerQ[Cyclotomic[ #,2]/GCD[Cyclotomic[ #,2],# ]]&]

is_A161508(n) = my(t=polcyclo(n,2)); isprimepower(t/gcd(t,n)); \\ Charles R Greathouse IV, Nov 17 2014

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

A097406 Largest primitive prime factor of 2^n-1, or a(n) = 1 if no such prime exists.

Original entry on oeis.org

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 89, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 178481, 241, 1801, 2731, 262657, 113, 2089, 331, 2147483647, 65537, 599479, 43691, 122921, 109, 616318177, 174763, 121369, 61681, 164511353, 5419

Offset: 1

Marco Matosic, Aug 16 2004

By Zsigmondy's theorem, a(n) > 1 except for n = 1 or 6.
Conjectures: (1) For every n the highest unique prime factor is of the form kn+1. The values for k are in A097407. (2) For each composite n many factors of the form kn+1 occur intermittently but always singly in any cofactor pair. (3) For each prime n every factor is of the form kn+1.
A prime factor of 2^n-1 is called primitive if it does not divide 2^r-1 for any rA086251.
a(n) is the greatest prime such that the multiplicative order of 2 mod a(n) equals n, or a(n)=1 if no such prime exists. - Jianing Song, Oct 23 2019

Max Alekseyev, Table of n, a(n) for n = 1..1206

Cf. A064078, A097407.

For the smallest primitive prime factor of 2^n-1 see A112927.

isprimitive(p, n) = {for (r=1, n-1, if (((2^r-1) % p) == 0, return (0));); return (1);}
a(n) = {f = factor(2^n-1); forstep(i=#f~, 1, -1, if (isprimitive(f[i, 1], n), return (f[i, 1]));); return (1);} \\ Michel Marcus, Jul 15 2013

a(n) = A006530(A064078(n)). - Jianing Song, Oct 23 2019

More terms and better description from Vladeta Jovovic, Sep 03 2004

a(1) and a(6) changed from 0 to 1 by Jianing Song, Oct 23 2019

A108974 Sort the primes (except 2) according to the multiplicative order of 2 modulo that prime. If two primes have the same order of 2, they are arranged numerically.

Original entry on oeis.org

3, 7, 5, 31, 127, 17, 73, 11, 23, 89, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 47, 178481, 241, 601, 1801, 2731, 262657, 29, 113, 233, 1103, 2089, 331, 2147483647, 65537, 599479, 43691, 71, 122921, 37, 109, 223, 616318177, 174763, 79

Offset: 1

Douglas Stones (dssto1(AT)student.monash.edu.au), Jul 27 2005

nonn

Or, primitive prime divisors of the Mersenne numbers 2^n-1 (see A000225) in their order of occurrence.
Of course the Mersenne primes 2^p-1 (cf. A000043) appear in this sequence.
If all odd positive numbers, not just the odd primes, are sorted in this way, the result is A059912. - Jeppe Stig Nielsen, Feb 13 2020

			The order of 2 modulo 3 is 2 and the order of 2 modulo 7 is 3. So 3 comes before 7.

Charles R Greathouse IV, Table of n, a(n) for n = 1..4275
G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.
Jeppe Stig Nielsen, A108974 arranged as an irregular array.
K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math., 3 (1892), 265-284.

Cf. A000043, A000225, A001348, A014664, A059912, A086251.

a = 1; DeleteDuplicates[Flatten[#[[All, 1]] & /@ FactorInteger[Table[a = 2 a + 1, {i, 1, 30}]]]] (* Horst H. Manninger, Mar 20 2021 *)

do(n)=my(v=List(),P=1,g,t,f); for(k=2,n, t=2^k-1; g=P; while((g=gcd(g,t))>1, t/=g); f=factor(t)[,1]; for(i=1,#f, listput(v,f[i])); P*=t); Vec(v) \\ Charles R Greathouse IV, Sep 23 2016

More terms from Martin Fuller, Sep 25 2006

A086252 a(n) is the smallest k such that 2^k-1 has n primitive prime factors.

Original entry on oeis.org

2, 11, 29, 92, 113, 223, 295, 333, 397, 1076

Offset: 1

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 rA086251 for the number of primitive prime factors in 2^n-1.
No more terms < 673. (2^673-1 is the first that is not completely factored in the linked reference.) - David Wasserman, Feb 22 2005
2^1207-1 is now the first not completely factored number of the form 2^k-1. - Hugo Pfoertner, Aug 06 2019

			a(2) = 11 because 2^11-1 = 23*89, both 23 and 89 have order 11 and the numbers 2^r-1 have only 0 or 1 primitive prime factors.

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.

J. Brillhart et al., Factorizations of b^n +- 1 Available on-line
factordb.com, Factors of 2^1076-1.
factordb.com, Status of 2^n-1 for n>1200.

Cf. A086251.

More terms from David Wasserman, Feb 22 2005

a(10) from Hugo Pfoertner, Aug 06 2019

A143584 Integers that are equal to the multiplicative order of 2 modulo some overpseudoprime to base 2.

Original entry on oeis.org

11, 23, 25, 28, 29, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 50, 51, 52, 53, 55, 57, 58, 59, 60, 63, 64, 66, 67, 68, 70, 71, 72, 73, 74, 75, 76, 79, 81, 82, 83, 84, 87, 88, 91, 92, 94, 95, 96, 97, 99, 100, 101, 102, 103, 104, 105, 106, 108, 109, 110, 111, 112

Offset: 1

Vladimir Shevelev, Aug 25 2008

nonn

A064078(a(n)) is a composite number. The sequence has a positive density since it contains, in particular, numbers of the form 8n+20 for n >= 1 (C. Pomerance, private correspondence). Since, e.g., 38 is not in the sequence, there is not an overpseudoprime m such that ord_m(2)=38.
Phi_{a(n)}(2), the a(n)-th cyclotomic polynomial of x evaluated at x=2 has at least 2 distinct prime factors that are not prime factors of the Phi_k(2) for any positive integer k < a(n). For example, Phi_11(2) = 2^11 - 1 = 2047 = 23 * 89 and Phi_25(2) = 2^20 + 2^15 + 2^10 + 2^5 + 1 = 1082401 = 601 * 1801. Note that p = a(n) is prime if and only if Phi_p(2) = 2^p - 1 is composite. - David Terr, Sep 09 2018
It is easy to prove the statement above. We use the fact that Phi_j(n) and Phi_k(n) are coprime whenever j and k are coprime as well as the fact that an overpseudoprime has at least 2 distinct prime factors. - David Terr, Oct 10 2018
A number k is included iff either 2^k-1 has more than one primitive prime factor (cf. A086251, A161508) or the only primitive prime factor of 2^k-1 is a Wieferich prime (no examples known). - Jeppe Stig Nielsen, Sep 01 2020

Jeppe Stig Nielsen, Table of n, a(n) for n = 1..1000

Cf. A002326, A014664, A064078, A086251, A122929, A141232, A161508.

Cf. A131952 (for the corresponding maximal overpseudoprimes).

isok(k) = my(m=polcyclo(k,2)); m/=gcd(m,k); m!=1&&!isprime(m) \\ Jeppe Stig Nielsen, Sep 01 2020

Name edited by Michel Marcus, Oct 06 2018
More terms from Michel Marcus, Oct 11 2018
Data for terms >= 100 corrected by Jeppe Stig Nielsen, Sep 01 2020

A276172 Number of primitive prime divisors of 3^n - 2^n.

Original entry on oeis.org

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

Offset: 1

Michel Lagneau, Aug 23 2016

nonn

A prime factor of 3^n - 2^n is called primitive if it does not divide 3^r - 2^r for any positive r=2, Zsigmondy's theorem says that there is at least one primitive prime factor except two cases:
(i)   2^6 - 1^6
(ii)  n=2 and a+b is a power of 2.

			a(7) = 2 because 3^7 - 2^7 = 2059 = 29*71 => 29 and 71 do not divide 3^r - 2^r  for r < 7:
3^1 - 2^1 = 1;
3^2 - 2^2 = 5;
3^3 - 2^3 = 19;
3^4 - 2^4 = 65 = 5*13;
3^5 - 2^5 = 211;
3^6 - 2^6 = 665 = 5*7*19.

Amiram Eldar, Table of n, a(n) for n = 1..568
Eric Weisstein's World of Mathematics, Zsigmondy Theorem.

Cf. A001047, A086251, A086257.

f:= n -> nops(select(p -> numtheory:-order(3/2 mod p, p) = n, numtheory:-factorset(3^n-2^n)));
map(f, [$1..100]); # Robert Israel, Sep 14 2016

nMax=100; pLst={}; Table[f=Transpose[FactorInteger[3^n-2^n]][[1]]; f=Complement[f, pLst]; cnt=Length[f]; pLst=Union[pLst, f]; cnt, {n, 1, nMax}]

a(1) corrected by Robert Israel, Sep 14 2016

A292364 Composites m such that each prime factor p > m of 2^m - 1 is a primitive prime factor of 2^m - 1.

Original entry on oeis.org

4, 8, 9, 12, 24, 121

Offset: 1

Thomas Ordowski, Sep 15 2017

From A086251: "A prime factor of 2^n-1 is called primitive if it does not divide 2^r-1 for any r

Are there only finitely many such composite numbers?

From Charlie Neder, Jan 09 2019: (Start)

Equivalently, composite numbers n such that, for each proper divisor d of n, 2^d-1 is n-smooth.

Let S represent the set of numbers such that the greatest prime factor of 2^n-1 is less than n^2. S begins {2,3,4,6,8,9,10,11,12,14,15,18,20,21,24,28,30,36,48,60} (obtained from A005420), and I conjecture that there are no further terms.

For any composite number k, if k has a divisor d >= sqrt(k) that is not in this sequence, then gpf(2^d-1) > d^2 >= k and k is not in this sequence.

If S is complete, there are 15 possible choices of k, the largest of which is 121, and this sequence is complete. (End)

Cf. A002326, A060443, A086251.

lista(nn) = {forcomposite (m=1, nn, f = factor(2^m-1)[,1]~; ok = 1; for (k=1, #f, p = f[k]; if ((p > m) && (znorder(Mod(2, p)) != m), ok = 0; break);); if (ok, print1(m, ", ")););} \\ Michel Marcus, Nov 11 2017

A002326((p-1)/2) = m for every prime factor p > m of 2^m - 1.

Showing 1-10 of 10 results.

cp's OEIS Frontend

A046800 Number of distinct prime factors of 2^n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A182590 Number of distinct prime factors of 2^n - 1 of the form k*n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A161508 Numbers k such that 2^k-1 has only one primitive prime factor.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A097406 Largest primitive prime factor of 2^n-1, or a(n) = 1 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A108974 Sort the primes (except 2) according to the multiplicative order of 2 modulo that prime. If two primes have the same order of 2, they are arranged numerically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A086252 a(n) is the smallest k such that 2^k-1 has n primitive prime factors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions