cp's OEIS Frontend

Let b(n) be the number of primes dividing n which are congruent to 1 (mod 3) (sequence A005088); then a(n) is 3^b(n) if n is not divisible by 9 and 3^(b(n) + 1) if n is divisible by 9.

Multiplicative with a(3) = 1, a(3^e) = 3, e >= 2, a(p^e) = 3 for primes p of the form 3k+1, a(p^e) = 1 for primes p of the form 3k+2. - David W. Wilson, May 22 2005 [Corrected by Jianing Song, Oct 21 2022]

If the multiplicative group of integers modulo n has (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then a(n) = Product_{i=1..r} gcd(3,k_r). - Jianing Song, Oct 21 2022

Multiplicative with a(2) = 1, a(4) = 2, a(2^e) = 4 for e >= 3; a(3) = 2, a(3^e) = 6 if e >= 2; for other primes p, a(p^e) = 6 if p == 1 (mod 6), a(p^e) = 2 if p == 5 (mod 6).

If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(6, k_i).

a(n) = A060594(n)*A060839(n).

For n > 2, a(n) = A060839(n)*2^A046072(n).

a(n) = A060594(n) iff n is not divisible by 9 and no prime factor of n is congruent to 1 mod 6, that is, n in A088232.

a(n) = A000010(n)/A293483(n). - Jianing Song, Nov 10 2019

Sum_{k=1..n} a(k) ~ c * n * log(n)^3, where c = (1/Pi^4) * Product_{p prime == 1 (mod 6)} (1 - (12*p-4)/(p+1)^3) = 0.0075925601... (Finch et al., 2010). - Amiram Eldar, Mar 26 2021

Conjecture: a(2^e) = 1 for e <= 1; a(2^e) = 2^(e-1) for e >= 1; a(5)=4; a(5^e) = 4*5^(e-2) for e > 1; a(p^e) = (p-1)*p^(e-1) for p == {2,3,4} (mod 5); a(p^e) = (p-1)*p^(e-1)/5 for p == 1 (mod 5). - R. J. Mathar, Oct 13 2017

a(n) = A000010(n)/A319099(n). This implies that the conjecture above is true. - Jianing Song, Nov 10 2019

Multiplicative with a(7) = 1, a(7^e) = 7 if e >= 2; for other primes p, a(p^e) = 7 if p == 1 (mod 7), a(p^e) = 1 otherwise.

If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(7, k_i).

a(n) = A000010(n)/A293484(n). - Jianing Song, Nov 10 2019

Multiplicative with a(p^e) = p^min(e-1, 4) if p = 2, gcd(8, p-1) if p > 2. - Jianing Song, Nov 10 2019

Multiplicative with a(p^e) = 4 if p^e = 25 or p == 1 (mod 5) and e = 1, otherwise 0.

If (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then T(n,k) = Product_{i=1..r} gcd(k,k_r).

T(p^e,k) = gcd((p-1)*p^(e-1),k) for odd primes p. T(2,k) = 1, T(2^e,k) = 2*gcd(2^(e-2),k) if k is even and 1 if k is odd.

A327924(n,k) = Sum_{q|n} T(n,k) * (Sum_{s|n/q} mu(s)/phi(s*q)).

T(m,n) = Sum_{d|n} (number of elements x such that ord(x,m) = d)/phi(d), where ord(x,m) is the multiplicative order of x modulo m, phi = A000010. There is a version to compute the terms more conveniently, see the links section. [Proof: let (Z/mZ)* denote the multiplicative group modulo m. For every d|n, the elements in (Z/mZ)* having order d are put into different equivalence classes, where each class is of the form {a^k: gcd(k,n)=1}. The size of each equivalence class is the number of different residues modulo d of the numbers that are coprime to n, which is phi(d). - Jianing Song, Sep 17 2022]

Equivalently, T(m,n) = Sum_{d|gcd(n,psi(m))} (number of elements x such that ord(x,m) = d)/phi(d). - Jianing Song, May 16 2022 [This is because the order of elements in (Z/mZ)* must divide psi(m). - Jianing Song, Sep 17 2022]

Let U(m,q) be the number of solutions to x^q == 1 (mod m):

T(m,1) = U(m,1) = 1;

T(m,2) = U(m,2) = A060594(m);

T(m,3) = (1/2)*U(m,3) + (1/2)*U(m,1) = (1/2)*A060839(m) + 1/2;

T(m,4) = (1/2)*U(m,4) + (1/2)*U(m,2) = (1/2)*A073103(m) + 1/2;

T(m,5) = (1/4)*U(m,5) + (3/4)*U(m,1) = (1/4)*A319099(m) + 3/4;

T(m,6) = (1/2)*U(m,6) + (1/2)*U(m,2) = (1/2)*A319100(m) + 1/2;

T(m,7) = (1/6)*U(m,7) + (5/6)*U(m,1) = (1/6)*A319101(m) + 5/6;

T(m,8) = (1/4)*U(m,8) + (1/4)*U(m,4) + (1/2)*U(m,2) = (1/4)*A247257(m) + (1/4)*A073103(m) + (1/2)*A060594(m);

T(m,9) = (1/6)*U(m,9) + (1/3)*U(m,3) + (1/2)*U(m,1);

T(m,10) = (1/4)*U(m,10) + (3/4)*U(m,2).

For odd primes p, T(p^e,n) = d(gcd(n,(p-1)*p^(e-1))), d = A000005; for e >= 3, T(2^e,n) = 2*(min{v2(n),e-2}+1) for even n and 1 for odd n, where v2 is the 2-adic valuation.

T(m,n) = Sum_{d|n} (number of elements x such that ord(x,m) = d)/phi(d), where ord(x,m) is the multiplicative order of x modulo m, phi = A000010.

Equivalently, T(m,n) = Sum_{d|gcd(n,psi(m))} (number of elements x such that ord(x,m) = d)/phi(d). - Jianing Song, May 16 2022

For odd primes p, T(p^e,n) = d(gcd(n,(p-1)*p^(e-1))) = A051194((p-1)*p^(e-1),n), d = A000005; for e >= 3, T(2^e,n) = 2*(v2(n)+1) for even n and 1 for odd n, where v2 is the 2-adic valuation.