A002184 -id:A002184 - cp's OEIS frontend

A086251 Number of primitive prime factors of 2^n - 1.

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

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 r < n. Equivalently, p is a primitive prime factor of 2^n - 1 if ord(2,p) = n. Zsigmondy's theorem says that there is at least one primitive prime factor for n > 1, except for n=6. See A086252 for those n that have a record number of primitive prime factors.
Number of odd primes p such that A002326((p-1)/2) = n. Number of occurrences of number n in A014664. - Thomas Ordowski, Sep 12 2017
The prime factors are not counted with multiplicity, which matters for a(364)=4 and a(1755)=6. - Jeppe Stig Nielsen, Sep 01 2020

			a(11) = 2 because 2^11 - 1 = 23*89 and both 23 and 89 have order 11.

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

Cf. A046800, A046051 (number of prime factors, with repetition, of 2^n-1), A086252, A002588, A005420, A002184, A046801, A049093, A049094, A059499, A085021, A097406, A112927, A237043.

Join[{0}, Table[cnt=0; f=Transpose[FactorInteger[2^n-1]][[1]]; Do[If[MultiplicativeOrder[2, f[[i]]]==n, cnt++ ], {i, Length[f]}]; cnt, {n, 2, 200}]]

a(n) = sumdiv(n, d, moebius(n/d)*omega(2^d-1)); \\ Michel Marcus, Sep 12 2017

a(n) = my(m=polcyclo(n, 2)); omega(m/gcd(m,n)) \\ Jeppe Stig Nielsen, Sep 01 2020

a(n) = Sum{d|n} mu(n/d) A046800(d), inverse Mobius transform of A046800.
a(n) <= A182590(n). - Thomas Ordowski, Sep 14 2017
a(n) = A001221(A064078(n)). - Thomas Ordowski, Oct 26 2017

Terms to a(500) in b-file from T. D. Noe, Nov 11 2010
Terms a(501)-a(1200) in b-file from Charles R Greathouse IV, Sep 14 2017
Terms a(1201)-a(1206) in b-file from Max Alekseyev, Sep 11 2022

A002588 a(n) = largest noncomposite factor of 2^(2n+1) - 1.

Original entry on oeis.org

1, 7, 31, 127, 73, 89, 8191, 151, 131071, 524287, 337, 178481, 1801, 262657, 2089, 2147483647, 599479, 122921, 616318177, 121369, 164511353, 2099863, 23311, 13264529, 4432676798593, 131071, 20394401, 201961, 1212847, 3203431780337

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the largest noncomposite factor of A147590(n). - César Aguilera, Jul 31 2019

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. 84.
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).

Max Alekseyev, Table of n, a(n) for n = 0..602 (terms 1..494 from Sean A. Irvine)
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

Cf. A002184, A005420, A147590.

[1] cat [Maximum(PrimeDivisors(2^(2*n+1) - 1)): n in [1..60]]; // Vincenzo Librandi, Aug 02 2019

Table[FactorInteger[2^(2 n + 1) - 1] [[-1, 1]], {n, 0, 30}] (* Vincenzo Librandi, Aug 02 2019 *)

a(n) = if (n==0, 1, vecmax(factor(2^(2*n+1) - 1)[, 1])); \\ Michel Marcus, Aug 03 2019

More terms from Don Reble, Nov 14 2006

A344681 a(n) is the smallest k > n such that 2^(k-n) == 1 (mod k).

Original entry on oeis.org

1, 3, 20737, 9, 7, 25, 31, 15, 127, 17, 73, 15, 23, 33, 3479, 21, 31, 65, 131071, 51, 524287, 31, 127, 33, 47, 69, 31, 39, 49, 43, 233, 87, 1361567, 45, 89, 51, 71, 73, 223, 57, 79, 65, 13367, 51, 431, 63, 73, 69, 2351, 97, 127, 63, 103, 65, 6361, 73, 89, 63, 721, 87, 179951

Offset: 0

Thomas Ordowski, Aug 17 2021

nonn

Smallest odd k > n such that 2^k == 2^n (mod k).
a(n) is the smallest odd k > n such that A002326((k-1)/2) divides k-n.
If a(n) is a prime p, then 2^(n-1) == 1 (mod p).
Note that a(2n+2) <= A002184(n) for n > 0.
If p is an odd prime, then a(p) <= p^2.

Michel Marcus, Table of n, a(n) for n = 0..149

Cf. A002184, A002326, A346988.

a[0] = 1; a[n_] := Module[{k = n + 1}, While[PowerMod[2, k - n, k] != 1, k++];
k]; Array[a, 60, 0] (* Amiram Eldar, Aug 17 2021 *)

a(n) = my(k=n+1); while(Mod(2, k)^(k-n) != 1, k++); k; \\ Michel Marcus, Aug 17 2021

def a(n):
    if n == 0: return 1
    k = n + 1
    while pow(2, k-n, k) != 1: k += 1
    return k
print([a(n) for n in range(61)]) # Michael S. Branicky, Aug 17 2021

More terms from Amiram Eldar, Aug 17 2021

cp's OEIS Frontend

A086251 Number of primitive prime factors of 2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A002588 a(n) = largest noncomposite factor of 2^(2n+1) - 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A344681 a(n) is the smallest k > n such that 2^(k-n) == 1 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions