A002326 -id:A002326 - cp's OEIS frontend

A049094 Numbers m such that 2^m - 1 is divisible by a square > 1.

6, 12, 18, 20, 21, 24, 30, 36, 40, 42, 48, 54, 60, 63, 66, 72, 78, 80, 84, 90, 96, 100, 102, 105, 108, 110, 114, 120, 126, 132, 136, 138, 140, 144, 147, 150, 155, 156, 160, 162, 168, 174, 180, 186, 189, 192, 198, 200, 204, 210, 216, 220, 222, 228, 231, 234, 240

Offset: 1

Labos Elemer

nonn

Conjecture: 2^n-1 is squarefree iff gcd(n,2^n-1)=1. If true, the conjecture would imply that Mersenne numbers (A001348) are squarefree. - Vladeta Jovovic, Apr 12 2002. But the conjecture is not true: counterexamples are n = 364 and n = 1755, i.e., gcd(364,2^364-1) = 1 and (2^364-1) mod 1093^2 = 0 and gcd(1755,2^1755-1) = 1 and (2^1755-1) mod 3511^2 = 0, cf. A001220. - Vladeta Jovovic, Nov 01 2005. The conjecture is true with assumption that n is not a multiple of A002326((q-1)/2), where q is a Wieferich prime A001220. - Thomas Ordowski, Nov 17 2015
If d|n and 2^d-1 is not squarefree, then 2^n-1 cannot be squarefree. For example, if 6 is in the sequence then 6*d is also. - Enrique Pérez Herrero, Feb 28 2009
If p(p-1)|n then p^2|2^n-1, where p is an odd prime. - Thomas Ordowski, Jan 22 2014
The primitive elements of this sequence are A237043. - Charles R Greathouse IV, Feb 05 2014
Dilcher & Ericksen prove that this sequence is exactly the set of numbers divisible by either t(p)p for a Wieferich prime p>2 or t(p) for a non-Wieferich prime p, where t(p) is the order of 2 modulo p (see Proposition 3.1). - Kellen Myers, Jun 09 2015
If d^2 divides 2^n-1 then d divides n, where n is not a multiple of 364, 1755, ...; i.e., A002326((q-1)/2) for Wieferich primes q, A001220. - Thomas Ordowski, Nov 15 2015
(1, 2^n-1, 2^n) is an abc triple iff 2^n-1 is not squarefree. - William Hu, Jul 04 2024

			a(2)=12 because 2^12 - 1 = 4095 = 5*(3^2)*7*13 is divisible by a square.

R. K. Guy, Unsolved Problems in Number Theory, A3.

Max Alekseyev, Table of n, a(n) for n = 1..296
Karl Dilcher and Larry Ericksen, The Polynomials of Mahler and Roots of Unity, The American Mathematical Monthly, Vol. 122, No. 04 (April 2015), pp. 338-353.
Enrique Pérez Herrero, Mersenne Numbers Treasure Map, Psych Geom blogspot, 02/17/09
Andy Steward, Factorizations of Generalized Repunits [Dead link]

Cf. A001220, A001348, A002326, A014491, A049093, A049096, A049095, A237043, A282242, A282243.

[n: n in [1..250] | not IsSquarefree(2^n-1)]; // Vincenzo Librandi, Jul 14 2015

N:= 250:
B:= Vector(N):
for n from 1 to N do
  if B[n] <> 1 then
    F:= ifactors(2^n-1,easy)[2];
    if max(seq(t[2],t=F)) > 1 or (hastype(F,symbol)
            and not numtheory:-issqrfree(2^n-1)) then
       B[[seq(n*k,k=1..floor(N/n))]]:= 1;
    fi
  fi;
od:
select(t -> B[t]=1, [$1..N]); # Robert Israel, Nov 17 2015

Select[Range[240], !SquareFreeQ[2^#-1]&] (* Vladimir Joseph Stephan Orlovsky, Mar 18 2011 *)

default(factor_add_primes,1);
is(n)=my(f=factor(n>>valuation(n,2))[,1],N,o); for(i=1,#f,if(n%(f[i]-1) == 0, return(1))); N=2^n-1; fordiv(n,d,f=factor(2^d-1)[,1]; for(i=1,#f, if(d==n,return(!issquarefree(N))); o=valuation(N,f[i]); if(o>1, return(1)); N/=f[i]^o)) \\ Charles R Greathouse IV, Feb 02 2014

is(n)=!issquarefree(2^n-1) \\ Charles R Greathouse IV, Feb 04 2014

More terms from Vladeta Jovovic, Apr 12 2002

Definition corrected by Jonathan Sondow, Jun 29 2010

A006694 Number of cyclotomic cosets of 2 mod 2n+1.

Original entry on oeis.org

0, 1, 1, 2, 2, 1, 1, 4, 2, 1, 5, 2, 2, 3, 1, 6, 4, 5, 1, 4, 2, 3, 7, 2, 4, 7, 1, 4, 4, 1, 1, 12, 6, 1, 5, 2, 8, 7, 5, 2, 4, 1, 11, 4, 8, 9, 13, 4, 2, 7, 1, 2, 14, 1, 3, 4, 4, 5, 11, 8, 2, 7, 3, 18, 10, 1, 9, 10, 2, 1, 5, 4, 6, 9, 1, 10, 12, 13, 3, 4, 8, 1, 13, 2, 2, 11, 1, 8, 4, 1, 1, 4, 6, 7, 19, 2, 2, 19, 1, 2

Offset: 0

N. J. A. Sloane, Sep 25 2001

a(0) = 0 by convention.
The number of cycles in permutations constructed from siteswap juggling patterns 1, 123, 12345, 1234567, etc., i.e., the number of ball orbits in such patterns minus one.
Also the number of irreducible polynomial factors of the polynomial (x^(2n+1) - 1) / (x - 1) over GF(2). - V. Raman, Oct 04 2012
Also, a(n) is the number of cycles of the Josephus permutation for n elements and a count of 2. For n >= 1, the Josephus permutation is given by the n-th row of A321298. See Knuth 1997 (exercise 1.3.3-29). - Pontus von Brömssen, Sep 18 2022

			Mod 15 there are 4 cosets: {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}, so a(7) = 4. Mod 13 there is only one coset: {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7}, so a(6) = 1.

Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd edition, Addison-Wesley, 1997.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North Holland, 1977, pp. 104-105.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 0..10000
Christopher Adler and Jean-Paul Allouche, Finite self-similar sequences, permutation cycles, and music composition, Journal of Mathematics and the Arts, 16:3, 244-261, (2022).
J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
Michael Assis, Folding Pi, arXiv:2403.09277 [math.NT], 2024.

Cf. A000010, A000374 (number of factors of x^n - 1 over GF(2)), A002326 (order of 2 mod 2n+1), A037226, A064286, A064287, A081844, A139767, A321298.
A001917 gives cycle counts of such permutations constructed only for odd primes.
Second column of A357217.

with(group); with(numtheory); gen_rss_perm := proc(n) local a, i; a := []; for i from 1 to n do a := [op(a), ((2*i) mod (n+1))]; od; RETURN(a); end; count_of_disjcyc_seq := [seq(nops(convert(gen_rss_perm(2*j),'disjcyc')),j=0..)];

Needs["Combinatorica`"]; f[n_] := Length[ToCycles[Mod[2Range[2n], 2n + 1]]]; Table[f[n], {n, 0, 100}] (* Ray Chandler, Apr 25 2008 *)
f[n_] := Length[FactorList[x^(2n + 1) - 1, Modulus -> 2]] - 2; Table[f[n], {n, 0, 100}] (* Ray Chandler, Apr 25 2008 *)
a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d], {d, Divisors[2n + 1]}] - 1; Table[a[n], {n, 0, 99}] (* Jean-François Alcover, Dec 14 2011, after Joerg Arndt *)

a(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1; /* cf. A081844 */
vector(122, n, a(n-1)) \\ Joerg Arndt, Jan 18 2011

from sympy import totient, n_order, divisors
def A006694(n): return sum(totient(d)//n_order(2,d) for d in divisors((n+1<<1)-1,generator=True) if d>1) # Chai Wah Wu, Apr 09 2024

Conjecture: a((3^n-1)/2) = n. - Vladimir Shevelev, May 26 2008 [This is correct. 2*((3^n-1)/2) + 1 = 3^n and the polynomial (x^(3^n) - 1) / (x - 1) factors over GF(2) into Product_{k=0..n-1} x^(2*3^k) + x^(3^k) + 1. - Joerg Arndt, Apr 01 2019]
a(n) = A081844(n) - 1.
a(n) = A064286(n) + 2*A064287(n).
From Vladimir Shevelev, Jan 19 2011: (Start)
1) a(n)=A037226(n) iff 2n+1 is prime;
2) The only case when a(n) < A037226(n) is n=0;
3) If {C_i}, i=1..a(n), is the set of all cyclotomic cosets of 2 mod (2n+1), then lcm(|C_1|, ..., |C_{a(n)}|) = A002326(n). (End)
a(n) = A000374(2*n + 1) - 1. - Joerg Arndt, Apr 01 2019
a(n) = (Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Additional comments from Antti Karttunen, Jan 05 2000
Extended by Ray Chandler, Apr 25 2008
Edited by N. J. A. Sloane, Apr 27 2008 at the suggestion of Ray Chandler

A049093 Numbers n such that 2^n - 1 is squarefree.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 64, 65, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 81, 82, 83, 85, 86, 87, 88, 89, 91, 92

Offset: 1

Labos Elemer

nonn

Numbers n such that gcd(n, 2^n - 1) = 1 and n is not a multiple of A002326((q - 1)/2), where q is a Wieferich prime A001220. - Thomas Ordowski, Nov 21 2015

If n is in the sequence, then so are all divisors of n. - Robert Israel, Nov 23 2015

			a(7) = 8 because 2^8 - 1 = 255 = 3 * 5 * 17 is squarefree.

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

Complement of A049094.

[n: n in [1..100] | IsSquarefree(2^n-1)]; // Vincenzo Librandi, Nov 22 2015

N:= 400: # to get all terms <= N
# This relies on the fact that the first N+1 members of A000225 have all been factored
# without any further Wieferich primes being found.
V:= Vector(N,1):
V[364 * [$1..N/364]]:= 0:
V[1755 * [$1..N/1755]]:= 0:
for n from 2 to N do
if V[n] = 0 then next fi;
if igcd(n, 2 &^n - 1 mod n) > 1 then
  V[n * [$1..N/n]]:= 0
fi;
od:
select(t -> V[t] = 1, [$1..N]); # Robert Israel, Nov 23 2015

Select[Range@ 92, SquareFreeQ[2^# - 1] &] (* Michael De Vlieger, Nov 21 2015 *)

isok(n) = issquarefree(2^n - 1); \\ Michel Marcus, Dec 19 2013

Terms a(73)-a(910) in b-file from Max Alekseyev, Nov 15 2014, Sep 28 2015

A005420 Largest prime factor of 2^n - 1.

Original entry on oeis.org

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

Offset: 2

N. J. A. Sloane

nonn

			2^6 - 1 = 63 = 3*21 = 9*7, so a(6) = 7.

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Charles R Greathouse IV and Amiram Eldar, Table of n, a(n) for n = 2..1206 (terms up to 500 from T. D. Noe, terms 501..1000 from Charles R Greathouse IV, terms 1001..1206 from Amiram Eldar)
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
factordb.com, Status of 2^1207-1. The factorization of the composite factor C337 of 2^1207-1 with 337 decimal digits is considered by many to be the most desired open factorization problem.
R. K. Guy, Letter to G. B. Huff & N. J. A. Sloane, Aug 1974
S. S. Wagstaff, Jr., The Cunningham Project
Eric Weisstein's World of Mathematics, Mersenne Number

Cf. A000043, A000225, A006530, A002326, A002587.
Cf. similar sequences listed in A274906.
Cf. A337431 (a(n)=a(2n)), A359063 (a(n)=a(2n)=a(4n)), A359088.

[Maximum(PrimeDivisors(2^n-1)): n in [2..45]]; // Vincenzo Librandi, Jul 13 2016

a[n_] := a[n] = FactorInteger[2^n-1] // Last // First; Table[Print[{n, a[n]}, If[2^n-1 == a[n], " Mersenne prime", " "]]; a[n], {n, 2, 127}] (* Jean-François Alcover, Dec 11 2012 *)
Table[FactorInteger[2^n - 1][[-1, 1]], {n, 2, 40}] (* Vincenzo Librandi, Jul 13 2016 *)

for(n=2,44, v=factor(2^n-1)[,1]; print1(v[#v]", "));

a(n) = vecmax(factor(2^n-1)[,1]); \\ Michel Marcus, Dec 15 2022

a(n) = a(2n) iff a(n) > A002587(n). See A337431. - Thomas Ordowski, Jan 07 2014
a(n) = A006530(A000225(n)). - Vincenzo Librandi, Jul 13 2016
a(n) = 2^n-1 = A000225(n) iff n is a Mersenne exponent (A000043). - Bernard Schott, Dec 11 2022

Description corrected by Michael Somos, Feb 24 2002
More terms from Rick L. Shepherd, Aug 22 2002
Incorrect comments removed by Michel Marcus, Dec 15 2022

A141232 Overpseudoprimes to base 2: composite k such that k = A137576((k-1)/2).

Original entry on oeis.org

2047, 3277, 4033, 8321, 65281, 80581, 85489, 88357, 104653, 130561, 220729, 253241, 256999, 280601, 390937, 458989, 486737, 514447, 580337, 818201, 838861, 877099, 916327, 976873, 1016801, 1082401, 1145257, 1194649, 1207361, 1251949, 1252697, 1325843

Offset: 1

Vladimir Shevelev, Jun 16 2008

nonn

Numbers are found by prime factorization of numbers from A001262 and a simple testing of the conditions indicated in comment to A141216.
All composite Mersenne numbers (A001348), Fermat numbers (A000215) and squares of Wieferich primes (A001220) are in this sequence. - Vladimir Shevelev, Jul 15 2008
C. Pomerance proved that this sequence is infinite (see Theorem 4 in the third reference). - Vladimir Shevelev, Oct 29 2011
Odd composite numbers k such that ord(2,k) * ((Sum_{d|k} phi(d)/ord(2,d)) - 1) = k-1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..664 from Michel Marcus)
J. H. Castillo, G. García-Pulgarín and J. M. Velásquez-Soto, q-pseudoprimality: A natural generalization of strong pseudoprimality, arXiv:1412.5226 [math.NT], 2014.
Vladimir Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich primes, arXiv:0806.3412 [math.NT], 2008-2012.
Vladimir Shevelev, Process of "primoverization" of numbers of the form a^n-1, arXiv:0807.2332 [math.NT], 2008.
Vladimir Shevelev, On upper estimate for the overpseudoprime counting function, arXiv:0807.1975 [math.NT], 2008.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, arXiv:1206.0606 [math.NT], 2012.

Cf. A000010, A001262, A141216, A001567, A002326.

A137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #]&] - t + 1];
okQ[n_] := n > 1 && CompositeQ[n] && n == A137576[(n-1)/2];
Reap[For[k = 2, k < 2*10^6, k++, If[okQ[k], Print[k]; Sow[k]]]][[2, 1]] (* Jean-François Alcover, Jan 11 2019, from PARI *)

f(n)=my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isok(n) = (n>1) && !isprime(n) && (n == f((n-1)/2)); \\ Michel Marcus, Oct 05 2018

Sum_{n:a(n)<=x} 1 <= x^(3/4)(1+o(1)).

Name edited by Michel Marcus, Oct 05 2018

A064078 Zsigmondy numbers for a = 2, b = 1: Zs(n, 2, 1) is the greatest divisor of 2^n - 1 (A000225) that is coprime to 2^m - 1 for all positive integers m < n.

Original entry on oeis.org

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 2047, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 8388607, 241, 1082401, 2731, 262657, 3277, 536870911, 331, 2147483647, 65537, 599479, 43691, 8727391, 4033, 137438953471, 174763, 9588151, 61681

Offset: 1

Jens Voß, Sep 04 2001

nonn

By Zsigmondy's theorem, the n-th Zsigmondy number for bases a and b is not 1 except in the three cases (1) a = 2, b = 1, n = 1, (2) a = 2, b = 1, n = 6, (3) n = 2 and a + b is a power of 2.
Composite terms are the maximal overpseudoprimes to base 2 (see A141232) for which the multiplicative order of 2 mod a(n) equals n. - Vladimir Shevelev, Aug 26 2008
a(n) = 2^n - 1 if and only if either n = 1 or n is prime. - Vladimir Shevelev, Sep 30 2008
a(n) == 1 (mod n), 2^(a(n)-1) == 1 (mod a(n)), A002326((a(n)-1)/2) = n. - Thomas Ordowski, Oct 25 2017
If n is odd, then the prime factors of a(n) are congruent to {1,7} mod 8, that is, they have 2 has a quadratic residue, and are congruent to 1 mod 2n. If n is divisible by 8, then the prime factors of a(n) are congruent to 1 mod 16. - Jianing Song, Apr 13 2019
Named after the Austrian mathematician Karl Zsigmondy (1867-1925). - Amiram Eldar, Jun 20 2021

			a(4) = 5 because 2^4 - 1 = 15 and its divisors being 1, 3, 5, 15, only 1 and 5 are coprime to 2^2 - 1 = 3 and 2^3 - 1 = 7, and 5 is the greater of these.
a(5) = 31 because 2^5 - 1 = 31 is prime.
a(6) = 1 because 2^6 - 1 = 63 and its divisors being 1, 3, 7, 9, 21, 63, only 1 is coprime to all of 3, 7, 15, 31.

T. D. Noe, Table of n, a(n) for n=1..1000
Wikipedia, Zsigmondy's theorem.
Karl Zsigmondy, Zur Theorie der Potenzreste, Monatshefte für Mathematik, Vol. 3 (1892), pp. 265-284.

Cf. A000225, A064079, A064080, A064081, A064082, A064083.

Cf. A019320, A063982.

Table[Cyclotomic[n, 2]/GCD[n, Cyclotomic[n, 2]], {n, 40}] (* Alonso del Arte, Mar 14 2013 *)

a(n) = my(m = polcyclo(n, 2)); m/gcd(m,n); \\ Michel Marcus, Mar 07 2015

Denominator of Sum_{d|n} d*moebius(n/d)/(2^d-1). - Vladeta Jovovic, Apr 02 2004
a(n) = A019320(n)/gcd(n, A019320(n)). - T. D. Noe, Apr 13 2010
a(n) = A019320(n)/(A019320(n) mod n) for n > 1. - Thomas Ordowski, Oct 24 2017

More terms from Vladeta Jovovic, Apr 02 2004

Definition corrected by Jerry Metzger, Nov 04 2009

A112927 a(n) is the least prime such that the multiplicative order of 2 mod a(n) equals n, or a(n)=1 if no such prime exists.

Original entry on oeis.org

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 23, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 47, 241, 601, 2731, 262657, 29, 233, 331, 2147483647, 65537, 599479, 43691, 71, 37, 223, 174763, 79, 61681, 13367, 5419, 431, 397, 631, 2796203, 2351, 97, 4432676798593, 251, 103, 53, 6361, 87211

Offset: 1

Vladimir Shevelev, Aug 25 2008

nonn

If a(n) differs from 1, then a(n) is the minimal prime divisor of A064078(n);
a(n)=n+1 iff n+1 is prime from A001122; a(n)=2n+1 iff 2n+1 is prime from A115591.
If a(n) > 1 then a(n) is the index where n occurs first in A014664. - M. F. Hasler, Feb 21 2016
Bang's theorem (special case of Zsigmondy's theorem, see links): a(n)>1 for all n>6. - Jeppe Stig Nielsen, Aug 31 2020

Robert G. Wilson v, Table of n, a(n) for n = 1..1206
Dario Alejandro Alpern, Factorization using the Elliptic Curve Method
Will Edgington, Factored Mersenne Numbers [from Internet Archive Wayback Machine]
Wikipedia, Zsigmondy's theorem

Cf. A002326, A064078, A001122, A115591.

Cf. A112927 (base 2), A143663 (base 3), A112092 (base 4), A143665 (base 5), A379639 (base 6), A379640 (base 7), A379641 (base 8), A379642 (base 9), A007138 (base 10), A379644 (base 11), A252170 (base 12).

A112927(n,f=factor(2^n-1)[,1])=!for(i=1,#f,znorder(Mod(2,f[i]))==n&&return(f[i])) \\ Use the optional 2nd arg to give a list of pseudoprimes to try when factoring of 2^n-1 is too slow. You may try factor(2^n-1,0)[,1]. - M. F. Hasler, Feb 21 2016

A053447 Multiplicative order of 4 mod 2n+1.

Original entry on oeis.org

1, 1, 2, 3, 3, 5, 6, 2, 4, 9, 3, 11, 10, 9, 14, 5, 5, 6, 18, 6, 10, 7, 6, 23, 21, 4, 26, 10, 9, 29, 30, 3, 6, 33, 11, 35, 9, 10, 15, 39, 27, 41, 4, 14, 11, 6, 5, 18, 24, 15, 50, 51, 6, 53, 18, 18, 14, 22, 6, 12, 55, 10, 50, 7, 7, 65, 9, 18, 34, 69, 23, 30, 14, 21, 74, 15, 12, 10, 26

Offset: 0

David W. Wilson

nonn

For a set S = {x, y} (x < y), let f(S) = {2x, y - x}, then a(n) is the smallest k > 0 such that f_k({1, 2n}) = {1, 2n} where f_k(S) denotes iteration for k times. E.g., for n = 3 we have: f_1({1, 6}) = f({1, 6}) = {2, 5}, f_2({1, 6}) = f({2, 5}) = {3, 4}, f_3({1, 6}) = f({3, 4}) = {1, 6}. - Jianing Song, Jan 27 2019
From Jianing Song, Dec 24 2022: (Start)
Let psi = A002322. For n > 0, we have 4^(psi(2*n+1)/2) = 2^psi(2*n+1) == 1 (mod 2*n+1), so a(n) divides psi(2*n+1)/2 => a(n) <= psi(2*n+1)/2 <= n. a(n) = psi(2*n+1)/2 if and only if one of the two following conditions holds: (a) the multiplicative order of 2 modulo 2*n+1 is psi(2*n+1); (b) the multiplicative order of 2 modulo 2*n+1 is psi(2*n+1)/2, and psi(2*n+1) == 2 (mod 4).
Additionally, a(n) = n if and only if 2*n+1 = p is a prime, and one of the two following conditions holds: (a) 2 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of 2 modulo p is (p-1)/2 (in this case, we have p == 7 (mod 8) since 2 is a quadratic residue modulo p). Such primes p are listed in A216371. (End)

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Multiplicative Order

Cf. A050976, A070667-A070675, A002326, A070676, A070677, A070681, A070678, A053451, A070679, A070682, A070680, A070683, A302141.

List([0..80],n->OrderMod(4,2*n+1)); # Muniru A Asiru, Feb 25 2019

[1] cat [Modorder(4, 2*n+1): n in [1..100]]; // Vincenzo Librandi, Apr 01 2014

Table[ MultiplicativeOrder[4, n], {n, 1, 160, 2}] (* Robert G. Wilson v, Apr 05 2011 *)

a(n) = znorder(Mod(4, 2*n+1)); \\ Michel Marcus, Feb 05 2015

Let b = A002326, then a(n) = b(n) if b(n) is odd, otherwise a(n) = b(n)/2. - Joerg Arndt, Feb 03 2019

A059499 a(n) = |{m : multiplicative order of 2 mod m = n}|.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 3, 16, 1, 5, 5, 8, 1, 24, 1, 38, 9, 11, 3, 68, 6, 5, 4, 54, 7, 79, 1, 16, 11, 5, 13, 462, 3, 5, 13, 140, 3, 123, 7, 110, 54, 11, 7, 664, 2, 114, 29, 118, 7, 124, 59, 188, 13, 55, 3, 4456, 1, 5, 82, 96, 5, 353, 3, 118, 11, 485, 7

Offset: 1

Vladeta Jovovic, Feb 04 2001

nonn

Also, number of primitive factors of 2^n - 1 (cf. A212953). - Max Alekseyev, May 03 2022
The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). See A002326.
a(n) is odd iff n is squarefree, A005117. - Thomas Ordowski, Jan 18 2014
The set S for which a(n) = |S| contains an odd number of prime powers p^k, where k > 0 and p == 3 (mod 4), iff n is squarefree and greater than one. - Isaac Saffold, Dec 28 2019

			a(3) = |{7}| = 1, a(4) = |{5,15}| = 2, a(6) = |{9,21,63}| = 3.

Max Alekseyev, Table of n, a(n) for n = 1..1206 (first 200 terms from Alois P. Heinz)

Column k=2 of A212957.
Primitive factors of b^n - 1: this sequence (b=2), A059885 (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A001037, A046801, A058943, A059912, A112927, A212953.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(2^d-1), d=divisors(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, May 31 2012

a[n_] := Sum[ MoebiusMu[n/d] * DivisorSigma[0, 2^d - 1], {d, Divisors[n]}]; Table[a[n], {n, 1, 71} ] (* Jean-François Alcover, Dec 12 2012 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(2^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{d|n} A008683(n/d) * A046801(d) = Sum_{d|A007947(n)} A008683(d) * A046801(n/d). - Max Alekseyev, May 03 2022

a(n) = 1 iff 2^n-1 is noncomposite. a(prime(n)) = 2^A088863(n)-1. - Thomas Ordowski, Jan 16 2014

More terms from John W. Layman, Mar 22 2002

More terms from Alois P. Heinz, May 31 2012

A053446 Multiplicative order of 3 mod m, where gcd(m, 3) = 1.

Original entry on oeis.org

1, 1, 2, 4, 6, 2, 4, 5, 3, 6, 4, 16, 18, 4, 5, 11, 20, 3, 6, 28, 30, 8, 16, 12, 18, 18, 4, 8, 42, 10, 11, 23, 42, 20, 6, 52, 20, 6, 28, 29, 10, 30, 16, 12, 22, 16, 12, 35, 12, 18, 18, 30, 78, 4, 8, 41, 16, 42, 10, 88, 6, 22, 23, 36, 48, 42, 20, 100, 34, 6, 52, 53, 27, 20, 12, 112, 44

Offset: 1

David W. Wilson

nonn

Essentially the same as A050975. - R. J. Mathar, Oct 13 2008

Let k, m be any positive numbers not divisible by 3. Let k <+> m denote that of the two numbers k + m, k + 2*m which is divisible by 3. Finally, for a number t divisible by 3, let t* = t/3^s where s is the 3-adic order of t. Let u = u(n) be the n-th number which is not divisible by 3. Consider the following algorithm of the calculating a(n), similar to the algorithm in A002326: Compute successively r_1 = (1 <+> u)*, r_2 = (r_1 <+> u)*, ..., r_h = (r_(h-1) <+> u)* and finish as soon as r_h = 1. Then a(n) = s(1 <+> u) + s(r_1 <+> u) + ... + s(r_(h-1) <+> u). Note that by a similar algorithm one can compute an arbitrary multiplicative order of a mod b, where gcd(a, b) = 1. - Vladimir Shevelev, Oct 06 2017

			From _Vladimir Shevelev_, Oct 06 2017: (Start)
7 is the fifth number not divisible by 3. According to the algorithm in the comment we have in the form of a "finite continued fraction"
    1 + 14
    ------ + 7
       3
    ---------- + 14
          3
    ----------------- + 7
            3^2
    ---------------------- = 1
               3^2
Summing the exponents of 3 in the denominators, we obtain a(5) = 1 + 1 + 2 + 2 = 6. (End)

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A001651, A002326, A050975.

List(Filtered([1..130],n->Gcd(n,3)=1),n->OrderMod(3,n)); # Muniru A Asiru, Feb 26 2019

MultiplicativeOrder[3, #] & /@ Select[ Range@ 115, GCD[3, #] == 1 &] (* Robert G. Wilson v, Apr 05 2011 *)

lista(nn) = {for (n=1, nn, if (gcd(n,3) == 1, print1(znorder(Mod(3, n)), ", ")););} \\ Michel Marcus, Feb 06 2015

[Mod(3,n).multiplicative_order() for n in (1..115) if gcd(n,3) == 1] # Peter Luschny, Oct 07 2017

a(n) = multiplicative order of 3 modulo floor((3*n-1)/2) = A001651(n), for n >= 1. - Wolfdieter Lang, Sep 28 2020

cp's OEIS Frontend

A049094 Numbers m such that 2^m - 1 is divisible by a square > 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Extensions

A006694 Number of cyclotomic cosets of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A049093 Numbers n such that 2^n - 1 is squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Extensions

A005420 Largest prime factor of 2^n - 1.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A141232 Overpseudoprimes to base 2: composite k such that k = A137576((k-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A064078 Zsigmondy numbers for a = 2, b = 1: Zs(n, 2, 1) is the greatest divisor of 2^n - 1 (A000225) that is coprime to 2^m - 1 for all positive integers m < n.

Views

Author

Keywords

Comments

Examples