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

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,4

Comments

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

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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 *)

Crossrefs

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.

Sequence in context: A100053 A029194 A246582 * A113322 A007380 A369813

Adjacent sequences: A059496 A059497 A059498 * A059500 A059501 A059502

Keyword

nonn

Author

Vladeta Jovovic, Feb 04 2001

Extensions

More terms from John W. Layman, Mar 22 2002

More terms from Alois P. Heinz, May 31 2012

Status

approved