cp's OEIS Frontend

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

%I A059885 #35 Jan 26 2025 02:44:39
%S A059885 2,2,2,6,4,10,2,14,4,16,6,58,2,10,16,88,6,108,6,150,10,54,6,290,18,10,
%T A059885 56,138,14,716,14,144,22,118,40,1088,6,54,90,670,14,730,6,570,356,22,
%U A059885 30,13864,124,342,54,138,14,3912,116,1362,118,238,6,22058,6,110
%N A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.
%C A059885 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) = number of orders of degree-n monic irreducible polynomials over GF(3).
%C A059885 Also, number of primitive factors of 3^n - 1 (cf. A218356). - _Max Alekseyev_, May 03 2022
%H A059885 Max Alekseyev, <a href="/A059885/b059885.txt">Table of n, a(n) for n = 1..690</a> (first 100 terms from Alois P. Heinz)
%F A059885 a(n) = Sum_{ d divides n } mu(n/d)*tau(3^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).
%e A059885 a(2) = |{4,8}| = 2, a(4) = |{5,10,16,20,40,80}| = 6, a(6) = |{7,14,28,52,56,91,104,182,364,728}| = 10.
%p A059885 with(numtheory); A059885 := proc(n) local d,s; s := 0; for d in divisors(n) do s := s+mobius(n/d)*tau(3^d-1); od; RETURN(s); end;
%t A059885 a[n_] := Sum[ MoebiusMu[n/d] * DivisorSigma[0, 3^d - 1], {d, Divisors[n]}]; Table[a[n], {n, 1, 62} ] (* _Jean-François Alcover_, Dec 12 2012 *)
%o A059885 (PARI) a(n) = sumdiv(n, d, moebius(n/d) * numdiv(3^d-1)); \\ _Amiram Eldar_, Jan 25 2025
%Y A059885 Primitive factors of b^n - 1: A059499 (b=2), this sequence (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
%Y A059885 Cf. A000005, A008683, A027376, A057958, A058944, A074477, A143663, A212906, A218356.
%Y A059885 Column k=3 of A212957.
%K A059885 nonn
%O A059885 1,1
%A A059885 _Vladeta Jovovic_, Feb 06 2001