A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.

2, 2, 4, 4, 6, 16, 6, 8, 26, 38, 14, 68, 6, 54, 84, 16, 6, 462, 6, 140, 132, 110, 14, 664, 120, 118, 128, 188, 62, 4456, 6, 96, 364, 118, 498, 7608, 30, 118, 180, 568, 30, 9000, 30, 892, 3974, 494, 62, 5360, 24, 8024, 1524, 892, 62, 9600, 3050, 1784, 372, 446

Offset: 1

Author

Vladeta Jovovic, Feb 06 2001

Keywords

• nonn

Comments

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).

a(n) is the number of orders of degree-n monic irreducible polynomials over GF(4).

Also, number of primitive factors of 4^n - 1. - Max Alekseyev, May 03 2022

Examples

			a(1) = |{1,3}| = 2, a(2) = |{5,15}| =2, a(3) = |{7,9,21,63}| =4, a(4) = |{17,51,85,255}| = 4.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 1..1128 (first 160 terms from Alois P. Heinz)

Crossrefs

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), this sequence (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).

Cf. A000005, A008683, A027377, A053447, A057957, A058948, A112092, A274906.

Column k=4 of A212957.

Programs

Maple

with(numtheory):
a:= n-> add(mobius(n/d)*tau(4^d-1), d=divisors(n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Oct 12 2012

Mathematica

a[n_] := DivisorSum[n, MoebiusMu[n/#]*DivisorSigma[0, 4^# - 1]&]; Array[a, 100] (* Jean-François Alcover, Nov 11 2015 *)

PARI

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

Formula

a(n) = Sum_{ d divides n } mu(n/d)*tau(4^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).