A060443 -id:A060443 - 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

A001265 Table T(n,k) in which n-th row lists prime factors of 2^n - 1 (n >= 2), with repetition.

Original entry on oeis.org

3, 7, 3, 5, 31, 3, 3, 7, 127, 3, 5, 17, 7, 73, 3, 11, 31, 23, 89, 3, 3, 5, 7, 13, 8191, 3, 43, 127, 7, 31, 151, 3, 5, 17, 257, 131071, 3, 3, 3, 7, 19, 73, 524287, 3, 5, 5, 11, 31, 41, 7, 7, 127, 337, 3, 23, 89, 683, 47, 178481, 3, 3, 5, 7, 13, 17, 241

Offset: 2

N. J. A. Sloane

For n > 1, the length of row n is A046051(n). - T. D. Noe, Aug 06 2007

			Table begins:
 n=2: 3;
 n=3: 7;
 n=4: 3, 5;
 n=5: 31;
 n=6: 3, 3, 7;
 n=7: 127;
 n=8: 3, 5, 17;
  ...

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

Max Alekseyev, Rows n = 2..1206, flattened (rows 2..500 from T. D. Noe)
Joerg Arndt, Rows n = 1..1200 of triangle (derived from Brillhart et al.; updated by Jon E. Schoenfield)
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
Jeroen Demeyer, Machine-readable Cunningham Tables
S. S. Wagstaff, Jr., The Cunningham Project
Eric Weisstein's World of Mathematics, Mersenne Number
Chai Wah Wu, Tables from the Cunningham Project in machine-readable JSON format.

Cf. A060443, A182590.

Array[Flatten[ConstantArray[#1, #2] & @@ # & /@ FactorInteger[2^# - 1]] &, 24] // Flatten (* Michael De Vlieger, Dec 04 2017 *)

row(n)= if (n==1, return ([0])); my(f = factor(2^n-1), v = []); for (i=1, #f~, for (j=1, f[i, 2], v = concat(v, f[i,j]))); v; \\ Michel Marcus, Dec 05 2017

Ambiguous rows 0 and 1 removed by Max Alekseyev, Jul 25 2023

A186522 Smallest prime factor of 2^n - 1 having the form k*n + 1.

Original entry on oeis.org

3, 7, 5, 31, 7, 127, 17, 73, 11, 23, 13, 8191, 43, 31, 17, 131071, 19, 524287, 41, 127, 23, 47, 241, 601, 2731, 262657, 29, 233, 31, 2147483647, 257, 599479, 43691, 71, 37, 223, 174763, 79, 41, 13367, 43, 431, 89, 631, 47, 2351, 97, 4432676798593, 251, 103, 53, 6361, 87211, 881, 113, 32377, 59, 179951, 61

Offset: 2

T. D. Noe, Feb 23 2011

nonn

The values of k are in A186283.
From Zhi-Wei Sun, Dec 27 2016: (Start)
For any odd prime p, by Fermat's little theorem p = (p-1) + 1 divides 2^(p-1) - 1, and it is well-known that any prime divisor q of 2^p - 1 must be congruent to 1 modulo p.
Conjecture: a(n) exists for any integer n > 1 (verified for n = 2..300). (End)
Proof of the above conjecture: By Bang's theorem, for each n > 1 except 6 there exists an odd prime p such that the multiplicative order of 2 modulo p is n, and therefore n must divide p-1. Note that a(n) <= p. - Robert Israel and Thomas Ordowski, Sep 08 2017
For prime p, a(p) = 2p + 1 if and only if p is a Lucasian prime (A002515). - Thomas Ordowski, Sep 08 2017

			For n = 4, the prime factors of 2^n - 1 are 3 and 5, but only 5 has the form k * n + 1. Hence a(4) = 5.
a(254) = 56713727820156410577229101238628035243 since this prime number is equal to (2^127+1)/3 and congruent to 1 modulo 127, and 2^127 - 1 is a Mersenne prime.
a(257) = 535006138814359 since this is a prime congruent to 1 modulo 257 and 2^257 - 1 = 535006138814359*p*q with p = 1155685395246619182673033 and q = 374550598501810936581776630096313181393 both prime. - _Zhi-Wei Sun_, Dec 27 2016

Table of n, a(n) for n = 2..1236
GIMPS (Prime95), Mersenne exponent cofactor probable prime PRP.

Cf. A000040, A000225, A060443 (all prime factors of 2^n-1).

Table[p = First/@FactorInteger[2^n - 1]; Select[p, Mod[#1, n] == 1 &, 1][[1]], {n, 2, 60}]

a(n)=my(s=if(n%2,2*n,n));forstep(p=s+1,2^n-1,s, if(Mod(2,p)^n==1&&isprime(p), return(p))) \\ Charles R Greathouse IV, Sep 07 2017

a(n)=my(f=factor(2^n-1)[,1]); for(i=1,#f, if(f[i]%n==1, return(f[i]))) \\ Charles R Greathouse IV, Sep 07 2017

a(p - 1) = p for odd prime p. - Thomas Ordowski, Sep 04 2017
A002326((a(n)-1)/2) divides n for all n > 1. - Thomas Ordowski, Sep 07 2017
a(n) = A186283(n) * n + 1. - Max Alekseyev, Apr 27 2022

Terms to a(300) in b-file from Zhi-Wei Sun, Dec 27 2016
a(301)-a(1200) in b-file from Charles R Greathouse IV, Sep 07 2017
a(1201)-a(1236) in b-file from Max Alekseyev, Apr 27 2022

A152057 Sum of the distinct prime factors of 2^n-1.

Original entry on oeis.org

0, 0, 3, 7, 8, 31, 10, 127, 25, 80, 45, 112, 28, 8191, 173, 189, 282, 131071, 102, 524287, 91, 471, 798, 178528, 286, 2433, 10925, 262737, 320, 3425, 534, 2147483647, 65819, 599598, 174765, 123150, 266, 616318400, 699053, 129646, 61789, 164524720, 5936

Offset: 0

Roger L. Bagula, Nov 22 2008

nonn

Amiram Eldar, Table of n, a(n) for n = 0..1206 (terms 0..500 from Robert Israel)

Cf. A000225, A008472, A046800, A075708.

Row sums of A060443.

sopf:= n -> convert(numtheory:-factorset(n),`+`):
seq(sopf(2^n-1),n=0..100); # Robert Israel, Jan 14 2021

Table[Sum[FactorInteger[2^n - 1][[m]][[1]], {m, 1, Length[FactorInteger[2^n - 1]]}], {n, 0, 50}]

a(n) = A008472(A000225(n)). - Robert Israel, Jan 14 2021

Edited by N. J. A. Sloane, Nov 26 2008

A270600 a(n) is the smallest k > 1 not already in the sequence such that p = prime(n) is a factor of 2^k-1.

Original entry on oeis.org

2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 22, 48, 100, 51, 106, 72, 56, 7, 130, 68, 138, 148, 15, 104, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29

Offset: 2

Felix Fröhlich, Mar 20 2016

nonn

First differs from A014664 at n = 24.
a(n) is the smallest r such that p = prime(n) appears in row r of A060443 and r has not been the smallest such r for any previous p.
6 is not a term of the sequence, since 2^6-1 = 3^2 * 7, but 3 and 7 are already factors of 2^4-1 and 2^3-1 respectively.
Apart from 6, are there any other k > 1 that are not terms of the sequence?

Felix Fröhlich, Table of n, a(n) for n = 2..10000

Cf. A014664, A060443.

nextk(p, k) = my(kk=k+1); while(Mod(2, p)^kk!=1, kk++); kk
isinvec(v, k) = for(x=1, #v, if(v[x]==k, return(1))); return(0)
addtovec(v, k) = my(w=vector(1)); w[1]=k; v=concat(v, w); v
addnextknotinvec(v, p) = my(kk=2); while(isinvec(v, kk), kk=nextk(p, kk)); addtovec(v, kk)
my(i=0, v=[], p=3); while(i < 50, v=addnextknotinvec(v, p); p=nextprime(p+1); i++); v

A292199 Numbers m such that there is a prime divisor p > m of 2^m - 1 not of the form k*m + 1.

Original entry on oeis.org

20, 25, 27, 28, 33, 35, 44, 45, 48, 49, 52, 54, 55, 56, 60, 63, 66, 68, 69, 70, 72, 76, 77, 80, 81, 84, 87, 88, 90, 91, 92, 95, 96, 98, 99, 100, 102, 104, 105, 108, 110, 112, 116, 117, 119, 120, 123, 124, 125, 126, 129, 132, 135, 136, 138, 140, 141, 143, 144, 145, 147, 148, 150

Offset: 1

Thomas Ordowski, Sep 11 2017

nonn

Contains no primes q and no doubled primes 2q.

Are there infinitely many such numbers?

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

Cf. A000040, A000225, A060443, A292188.

Contains A291855.

Terms a(19) onward from Max Alekseyev, Sep 13 2017

A244453 Prime factors of 2^A054723(n)-1, ordered by increasing n, then by increasing size of the factors.

Original entry on oeis.org

23, 89, 47, 178481, 233, 1103, 2089, 223, 616318177, 13367, 164511353, 431, 9719, 2099863, 2351, 4513, 13264529, 6361, 69431, 20394401, 179951, 3203431780337, 193707721, 761838257287, 228479, 48544121, 212885833

Offset: 1

Felix Fröhlich, Jun 28 2014

Subsequence of A060443.

Prime factors of composite Mersenne numbers; A089162 with the Mersenne primes A000668 removed. - Jens Kruse Andersen, Jul 11 2014

			A054723(1) = 11. 2^11-1 = 2047 = 23*89. - _Jens Kruse Andersen_, Jul 11 2014
Triangle begins:
23, 89;
47, 178481;
233, 1103, 2089;
223, 616318177;
13367, 164511353;
431, 9719, 2099863;
2351, 4513, 13264529;
6361, 69431, 20394401;

Jens Kruse Andersen, Table of n, a(n) for n = 1..577
Sergey Nikitin, Euler-Fermat algorithm and some of its applications, 2018.
Sam Wagstaff, The Cunningham Project

Cf. A003260, A016047, A046800, A089162.

Map[FactorInteger, Select[2^Prime@Range@20 - 1, CompositeQ]][[All, All, 1]] // Flatten (* Michael De Vlieger, Nov 20 2018 *)

forprime(n=1, 100, m=2^n-1; if(!isprime(m), f=factor(m); for(i=1, #f~, print1(f[i,1]", ")))) \\ Jens Kruse Andersen, Jul 11 2014

A292188 Composite numbers m such that all prime divisors p > m of 2^m - 1 are of the form p = 2km + 1.

Original entry on oeis.org

8, 9, 15, 21, 24, 32, 39, 51, 57, 64, 65, 75, 85, 93, 111, 115, 121, 133, 183, 201, 217, 265, 267, 279, 303, 305, 309, 321, 341, 381, 415, 417, 427, 445, 671, 745, 771, 807, 813, 843, 879, 889, 1041, 1047, 1059, 1119, 1137, 1203

Offset: 1

Thomas Ordowski, Sep 11 2017

nonn

There are no terms of the forms q-1 and 2q with q prime.

Are there infinitely many the terms m = 3q with q prime?

			For 2^15 - 1 = 7*31*151, 30/15 = 2 and 150/15 = 10, so 15 is a term.
For 2^16 - 1 = 3*5*17*257, 16/16 = 1 is odd, so 16 is not a term.

Cf. A000040, A000225, A060443.

a(13)-a(48) from Max Alekseyev, Sep 11 2017

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-9 of 9 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

A001265 Table T(n,k) in which n-th row lists prime factors of 2^n - 1 (n >= 2), with repetition.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A186522 Smallest prime factor of 2^n - 1 having the form k*n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A152057 Sum of the distinct prime factors of 2^n-1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A270600 a(n) is the smallest k > 1 not already in the sequence such that p = prime(n) is a factor of 2^k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A292199 Numbers m such that there is a prime divisor p > m of 2^m - 1 not of the form k*m + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A244453 Prime factors of 2^A054723(n)-1, ordered by increasing n, then by increasing size of the factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A292188 Composite numbers m such that all prime divisors p > m of 2^m - 1 are of the form p = 2km + 1.