cp's OEIS Frontend

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

%I A059886 #55 Mar 15 2025 14:01:02
%S A059886 2,2,4,4,6,16,6,8,26,38,14,68,6,54,84,16,6,462,6,140,132,110,14,664,
%T A059886 120,118,128,188,62,4456,6,96,364,118,498,7608,30,118,180,568,30,9000,
%U A059886 30,892,3974,494,62,5360,24,8024,1524,892,62,9600,3050,1784,372,446
%N A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.
%C A059886 The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
%C A059886 a(n) is the number of orders of degree-n monic irreducible polynomials over GF(4).
%C A059886 Also, number of primitive factors of 4^n - 1. - _Max Alekseyev_, May 03 2022
%H A059886 Max Alekseyev, <a href="/A059886/b059886.txt">Table of n, a(n) for n = 1..1128</a> (first 160 terms from Alois P. Heinz)
%F A059886 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).
%e A059886 a(1) = |{1,3}| = 2, a(2) = |{5,15}| =2, a(3) = |{7,9,21,63}| =4, a(4) = |{17,51,85,255}| = 4.
%p A059886 with(numtheory):
%p A059886 a:= n-> add(mobius(n/d)*tau(4^d-1), d=divisors(n)):
%p A059886 seq(a(n), n=1..60);  # _Alois P. Heinz_, Oct 12 2012
%t A059886 a[n_] := DivisorSum[n, MoebiusMu[n/#]*DivisorSigma[0, 4^# - 1]&]; Array[a, 100] (* _Jean-François Alcover_, Nov 11 2015 *)
%o A059886 (PARI) a(n) = sumdiv(n, d, moebius(n/d) * numdiv(4^d-1)); \\ _Amiram Eldar_, Jan 25 2025
%Y A059886 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).
%Y A059886 Cf. A000005, A008683, A027377, A053447, A057957, A058948, A112092, A274906.
%Y A059886 Column k=4 of A212957.
%K A059886 nonn
%O A059886 1,1
%A A059886 _Vladeta Jovovic_, Feb 06 2001