A060839 -id:A060839 - cp's OEIS frontend

A327924 Square array read by ascending antidiagonals: T(m,n) is the number of non-isomorphic groups G such that G is the semidirect product of C_m and C_n, where C_m is a normal subgroup of G and C_n is a subgroup of G.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 4, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 3, 1, 2, 1, 1, 1, 4, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Jianing Song, Sep 30 2019

The semidirect product of C_m and C_n has group representation G = , where r is any number such that r^n == 1 (mod m). Two groups G =  and G' =  are isomorphic if and only if there exists some k, gcd(k,n) = 1 such that r^k == s (mod m), in which case f(x^i*y^j) = x^i*y^(k*j) is an isomorphic mapping from G to G'.
Given m, T(m,n) only depends on the value of gcd(n,psi(m)), psi = A002322 (Carmichael lambda). So each row is periodic with period psi(m). See A327925 for an alternative version.
Every number k occurs in the table. By Dirichlet's theorem on arithmetic progressions, there exists a prime p such that p == 1 (mod 2^(k-1)), then T(p,2^(k-1)) = d(gcd(2^(k-1),p-1)) = k (see the formula below). For example, T(5,4) = 3, T(17,8) = 4, T(17,16) = 5, T(97,32) = 6, T(193,64) = 7, ...
Row m and Row m' are the same if and only if (Z/mZ)* = (Z/m'Z)*, where (Z/mZ)* is the multiplicative group of integers modulo m. The if part is clear; for the only if part, note that the two sequences {(number of x in (Z/mZ)* such that x^n = 1)}{n>=1} and {T(m,n)}{n>=1} determine each other, and the structure of a finite abelian group G is uniquely determined by the sequence {(number of x in G such that x^n = 1)}{n>=1}. - _Jianing Song, May 16 2022

			  m/n  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  10   1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3
  11   1  2  1  2  2  2  1  2  1  4  1  2  1  2  2  2  1  2  1  4
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  2  3  1  4  1  3  2  2  1  6  1  2  2  3  1  4  1  3
  14   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  15   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
  16   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
  17   1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3
  18   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  19   1  2  2  2  1  4  1  2  3  2  1  4  1  2  2  2  1  6  1  2
  20   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
Example shows that T(16,4) = 6: The semidirect product of C_16 and C_4 has group representation G = <x, y|x^16 = y^4 = 1, yxy^(-1) = x^r>, where r = 1, 3, 5, 7, 9, 11, 13, 15. Since 3^3 == 11 (mod 16), 5^3 == 13 (mod 16), <x, y|x^16 = y^4 = 1, yxy^(-1) = x^3> and <x, y|x^16 = y^4 = 1, yxy^(-1) = x^11> are isomorphic, <x, y|x^16 = y^4 = 1, yxy^(-1) = x^5> and <x, y|x^16 = y^4 = 1, yxy^(-1) = x^13> are isomorphic, giving a total of 6 non-isomorphic groups.

Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)
Math Overflow, When are two semidirect products of two cyclic groups isomorphic.
Jianing Song, An equivalent formula.

Cf. A327925, A002322, A000010, A000005.

Cf. also A060594, A060839, A073103, A319099, A319100, A319101, A247257.

numord(n,q) = my(v=divisors(q),r=znstar(n)[2]); sum(i=1,#v,prod(j=1,#r,gcd(v[i],r[j]))*moebius(q/v[i]))
T(m,n) = my(u=divisors(n)); sum(i=1,#u,numord(m,u[i])/eulerphi(u[i]))

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.

A386236 Ratio of the period and the reduced period of the Fibonacci 3-step sequence A000073 mod n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 1, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 1, 3, 1, 3, 1, 3, 1, 1, 1, 1, 3, 1, 3, 3, 1, 1, 3, 3, 3, 3, 1, 3, 1, 1, 3, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 1, 3, 3, 3

Offset: 1

Peter Munn, Jul 16 2025

nonn

The period is A046738(n) and the reduced period is A046737(n).

See also the information in A154754 and A046737.

Peter Munn, Table of n, a(n) for n = 1..1000

Cf. A000073, A046737, A046738.
The equivalent sequence for Fibonacci numbers is A001176.
Cf. A060839 (differs first at n=31), A154754 (restriction to prime indices).

a(n) = A046738(n)/A046737(n).

A115069 a(n) = 3^b(n), where b(n) is #{primes p=1 mod 3 dividing n}.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 3, 1, 3, 1, 1, 3, 1, 1, 1, 3, 1, 3, 3, 3, 1, 1, 3, 3, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 1, 1, 3, 1, 1, 3, 3, 1, 3, 3, 3, 3, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 9, 1, 3, 1, 3, 1, 3, 3, 1

Offset: 1

Steven Finch, Mar 01 2006

Amiram Eldar, Table of n, a(n) for n = 1..10000
Steven Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A005088, A060839.

a:= n-> 3^add(`if`(irem(i[1], 3)=1, 1, 0), i=ifactors(n)[2](n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 17 2019

b[n_] := Count[FactorInteger[n][[All, 1]], p_ /; Mod[p, 3] == 1];
a[1] = 1; a[n_] := 3^b[n];
Table[a[n], {n, 1, 99}] (* Jean-François Alcover, Feb 17 2019 *)

a(n) = 3^#select(x -> x%3 == 1, factor(n)[,1]); \\ Amiram Eldar, Nov 30 2024

a(n) = 3^A005088(n). - R. J. Mathar, May 19 2020
From Amiram Eldar, Nov 30 2024: (Start)
Multiplicative with a(p^e) = 3 if p == 1 (mod 3), and 1 otherwise.
Sum_{k=1..n} a(k) ~ (sqrt(3)/(2*Pi)) * c * n * log(n), where c = Product_{primes p == 1 (mod 3)} (1 - 2/(p*(p+1))) = 0.9410349413195354517900322... (Finch and Sebah, 2006). (End)

a(1)=1 prepended by Alois P. Heinz, Feb 17 2019

Keyword mult added by Amiram Eldar, Nov 30 2024

A224516 Number of solutions to x^4 - x == 0 (mod n).

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 4, 2, 4, 4, 2, 4, 4, 8, 4, 2, 2, 8, 4, 4, 8, 4, 2, 4, 2, 8, 4, 8, 2, 8, 4, 2, 4, 4, 8, 8, 4, 8, 8, 4, 2, 16, 4, 4, 8, 4, 2, 4, 4, 4, 4, 8, 2, 8, 4, 8, 8, 4, 2, 8, 4, 8, 16, 2, 8, 8, 4, 4, 4, 16, 2, 8, 4, 8, 4, 8, 8, 16, 4, 4, 4, 4, 2, 16, 4

Offset: 1

Eric M. Schmidt, Apr 09 2013

			The solutions for n = 7 are 0, 1, 2, and 4.

Eric M. Schmidt, Table of n, a(n) for n = 1..10000

Cf. A034444, A087688, A060839, A000086.

f[3, e_] := If[e == 1, 2, 4]; f[p_, e_] := If[Mod[p, 3] == 2, 2, 4]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 19 2020 *)

def A224516(n) :
    res = 1
    for p, m in factor(n) :
        if (p % 3 == 2) or (p == 3 and m == 1) : res *= 2
        else : res *= 4
    return res

Multiplicative with a(p^e) = 4 for p == 1 (mod 3); a(p^e) = 2 for p == 2 (mod 3); a(3^1) = 2; a(3^e) = 4 for e > 1.

A276919 Number of solutions to x^3 + y^3 + z^3 + t^3 == 1 (mod n) for 1 <= x, y, z, t <= n.

Original entry on oeis.org

1, 8, 27, 64, 125, 216, 336, 512, 1296, 1000, 1331, 1728, 1794, 2688, 3375, 4096, 4913, 10368, 7410, 8000, 9072, 10648, 12167, 13824, 15625, 14352, 34992, 21504, 24389, 27000, 30225, 32768, 35937, 39304, 42000, 82944, 48396, 59280, 48438, 64000, 68921, 72576, 77529, 85184, 162000, 97336

Offset: 1

José María Grau Ribas, Sep 22 2016

It appears that a(n) = n^3 for n in A088232. See also A066498. - Michel Marcus, Oct 11 2016

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A000189, A047726, A060839, A063454, A087412, A087786, A254073, A276920.

JJJ[4, n, lam] = Sum[If[Mod[a^3 + b^3 + c^3 + d^3, n] == Mod[lam, n], 1, 0], {d, 0, n - 1}, {a, 0, n - 1}, {b, 0, n - 1}, {c, 0 , n - 1}]; Table[JJJ[4, n, 1], {n, 1, 50}]

a(n) = sum(x=1, n, sum(y=1, n, sum(z=1, n, sum(t=1, n, Mod(x,n)^3 + Mod(y,n)^3 + Mod(z,n)^3 + Mod(t,n)^3 == 1)))); \\ Michel Marcus, Oct 11 2016

qperms(v) = {my(r=1,t); v = vecsort(v); for(i=1,#v-1, if(v[i]==v[i+1], t++, r*=binomial(i,t+1);t=0));r*=binomial(#v,t+1)}
a(n) = {my(t=0); forvec(v=vector(4,i,[1,n]), if(sum(i=1, 4, Mod(v[i], n)^3)==1, print1(v", "); t+=qperms(v)),1);t} \\ David A. Corneth, Oct 11 2016

def A276919(n):
    ndict = {}
    for i in range(n):
        i3 = pow(i,3,n)
        for j in range(i+1):
            j3 = pow(j,3,n)
            m = (i3+j3) % n
            if m in ndict:
                if i == j:
                    ndict[m] += 1
                else:
                    ndict[m] += 2
            else:
                if i == j:
                    ndict[m] = 1
                else:
                    ndict[m] = 2
    count = 0
    for i in ndict:
        j = (1-i) % n
        if j in ndict:
            count += ndict[i]*ndict[j]
    return count # Chai Wah Wu, Jun 06 2017

A276920 Number of solutions to x^3 + y^3 + z^3 + t^3 == 0 (mod n) for 1 <= x, y, z, t <= n.

Original entry on oeis.org

1, 8, 27, 72, 125, 216, 595, 704, 1539, 1000, 1331, 1944, 3133, 4760, 3375, 5632, 4913, 12312, 8911, 9000, 16065, 10648, 12167, 19008, 16125, 25064, 45927, 42840, 24389, 27000, 35371, 47104, 35937, 39304, 74375, 110808, 58645, 71288, 84591, 88000

Offset: 1

José María Grau Ribas, Sep 22 2016

a(n) = n^3 if n is in A074243. - Robert Israel, Oct 13 2016

			For n = 3, we see that all nondecreasing solutions {x, y, z, t} are in {{1, 1, 1, 3}, {1, 1, 2, 2}, {1, 2, 3, 3}, {2, 2, 2, 3}, {3, 3, 3, 3}}. The numbers in the sets can be ordered in 4, 6, 12, 4 and 1 ways respectively. Therefore, a(3) = 4 + 6 + 12 + 4 + 1 = 27. - _David A. Corneth_, Oct 11 2016

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms n = 1..242 from Robert Israel)

Cf. A000189, A047726, A060839, A063454, A074243, A087412, A087786, A254073, A276919.

CF:= table([[false, false, true] = 12, [true, false, false] = 12, [true, false, true] = 6, [false, false, false] = 24, [true, true, true] = 1, [false, true, true] = 4, [false, true, false] = 12, [true, true, false] = 4]):
f1:= proc(n)
  option remember;
  local count, t, x,y,z,signature;
  if isprime(n) and n mod 3 = 2 then return n^3 fi;
  count:= 0;
  for t from 1 to n do
    for x from 1 to t do
      for y from 1 to x do
        for z from 1 to y do
          if t^3 + x^3 + y^3 + z^3 mod n = 0 then
            signature:= map(evalb,[z=y,y=x,x=t]);
            count:= count + CF[signature];
          fi
  od od od od;
  count
end proc:
f:= proc(n) local t;
    mul(f1(t[1]^t[2]),t=ifactors(n)[2])
end proc:
map(f, [$1..40]); # Robert Israel, Oct 13 2016

JJJ[4, n, lam] = Sum[If[Mod[a^3 + b^3 + c^3 + d^3, n] == Mod[lam, n], 1, 0], {d, 0, n - 1}, {a, 0, n - 1}, {b, 0, n - 1}, {c, 0 , n - 1}]; Table[JJJ[4, n, 0], {n, 1, 50}]

a(n) = sum(x=1, n, sum(y=1, n, sum(z=1, n, sum(t=1, n, Mod(x,n)^3 + Mod(y,n)^3 + Mod(z,n)^3 + Mod(t,n)^3 == 0)))); \\ Michel Marcus, Oct 11 2016

qperms(v) = {my(r=1,t); v = vecsort(v); for(i=1,#v-1, if(v[i]==v[i+1], t++, r*=binomial(i, t+1);t=0));r*=binomial(#v,t+1)}
a(n) = {my(t=0); forvec(v=vector(4,i,[1,n]), if(sum(i=1,4,Mod(v[i],n)^3)==0, t+=qperms(v)),1);t} \\ David A. Corneth, Oct 11 2016

def A276920(n):
    ndict = {}
    for i in range(n):
        i3 = pow(i,3,n)
        for j in range(i+1):
            j3 = pow(j,3,n)
            m = (i3+j3) % n
            if m in ndict:
                if i == j:
                    ndict[m] += 1
                else:
                    ndict[m] += 2
            else:
                if i == j:
                    ndict[m] = 1
                else:
                    ndict[m] = 2
    count = 0
    for i in ndict:
        j = (-i) % n
        if j in ndict:
            count += ndict[i]*ndict[j]
    return count # Chai Wah Wu, Jun 06 2017

A327925 Irregular table read by rows: T(m,n) is the number of non-isomorphic groups G such that G is the semidirect product of C_m and C_n, where C_m is a normal subgroup of G and C_n is a subgroup of G, 1 <= n <= A002322(m).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 2, 2, 1, 4, 1, 4, 1, 2, 2, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 1, 4, 1, 4, 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 1, 6, 1, 2, 2, 2, 1, 4, 1, 4, 1, 6, 1, 4, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 4, 1, 2, 3, 2, 1, 4, 1, 2, 2, 2, 1, 6

Offset: 1

Jianing Song, Sep 30 2019

The semidirect product of C_m and C_n has group representation G = , where r is any number such that r^n == 1 (mod m). Two groups G =  and G' =  are isomorphic if and only if there exists some k, gcd(k,n) = 1 such that r^k == s (mod m), in which case f(x^i*y^j) = x^i*y^(k*j) is an isomorphic mapping from G to G'.
Given m, T(m,n) only depends on the value of gcd(n,psi(m)), psi = A002322 (Carmichael lambda). So each row of A327924 is periodic with period psi(m), so we have this for an alternative version.
Every number k occurs in the table. By Dirichlet's theorem on arithmetic progressions, there exists a prime p such that p == 1 (mod 2^(k-1)), then T(p,2^(k-1)) = d(gcd(2^(k-1),p-1)) = k (see the formula below). For example, T(5,4) = 3, T(17,8) = 4, T(17,16) = 5, T(97,32) = 6, T(193,64) = 7, ...
Row m and Row m' are the same if and only if (Z/mZ)* = (Z/m'Z)*, where (Z/mZ)* is the multiplicative group of integers modulo m. The if part is clear; for the only if part, note that the two sequences {(number of x in (Z/mZ)* such that x^n = 1)}{n>=1} and {T(m,n)}{n>=1} determine each other, and the structure of a finite abelian group G is uniquely determined by the sequence {(number of x in G such that x^n = 1)}{n>=1}. - _Jianing Song, May 16 2022

			Table starts
m = 1: 1;
m = 2: 1;
m = 3: 1, 2;
m = 4: 1, 2;
m = 5: 1, 2, 1, 3;
m = 6: 1, 2;
m = 7: 1, 2, 2, 2, 1, 4;
m = 8: 1, 4;
m = 9: 1, 2, 2, 2, 1, 4;
m = 10: 1, 2, 1, 3;
m = 11: 1, 2, 1, 2, 2, 2, 1, 2, 1, 4;
m = 12: 1, 4;
m = 13: 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 1, 6;
m = 14: 1, 2, 2, 2, 1, 4;
m = 15: 1, 4, 1, 6;
m = 16: 1, 4, 1, 6;
m = 17: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5;
m = 18: 1, 2, 2, 2, 1, 4;
m = 19: 1, 2, 2, 2, 1, 4, 1, 2, 3, 2, 1, 4, 1, 2, 2, 2, 1, 6;
m = 20: 1, 4, 1, 6;
Example shows that T(21,6) = 6: The semidirect product of C_21 and C_6 has group representation G = <x, y|x^21 = y^6 = 1, yxy^(-1) = x^r>, where r = 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20. Since 2^5 == 11 (mod 21), 4^5 == 16 (mod 21), 5^5 == 17 (mod 21), 10^5 == 19 (mod 21), there are actually four pairs of isomorphic groups, giving a total of 8 non-isomorphic groups.

Jianing Song, Table of n, a(n) for n = 1..8346 (the first 200 rows)
Math Overflow, When are two semidirect products of two cyclic groups isomorphic

Cf. A327925, A002322, A000010, A000005.

Cf. also A060594, A060839, A073103, A319099, A319100, A319101, A051194.

numord(n,q) = my(v=divisors(q),r=znstar(n)[2]); sum(i=1,#v,prod(j=1,#r,gcd(v[i],r[j]))*moebius(q/v[i]))
T(m,n) = my(u=divisors(n)); sum(i=1,#u,numord(m,u[i])/eulerphi(u[i]))
Row(m) = my(l=if(m>2,znstar(m)[2][1],1), R=vector(l,n,T(m,n))); R

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.

A115070 a(n) = phi(n)/3^b(n), where b(n) is #{primes p=1 mod 3 dividing n}.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 2, 4, 6, 4, 10, 4, 4, 2, 8, 8, 16, 6, 6, 8, 4, 10, 22, 8, 20, 4, 18, 4, 28, 8, 10, 16, 20, 16, 8, 12, 12, 6, 8, 16, 40, 4, 14, 20, 24, 22, 46, 16, 14, 20, 32, 8, 52, 18, 40, 8, 12, 28, 58, 16, 20, 10, 12, 32, 16, 20, 22, 32, 44, 8, 70, 24, 24, 12, 40, 12, 20, 8, 26, 32, 54

Offset: 1

Steven Finch, Mar 01 2006

Cubic analog of A070306. Always an integer.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A000010, A005088, A070306, A060839, A115069.

with(numtheory):
a:= n-> phi(n)/3^add(`if`(irem(p, 3)=1, 1, 0), p=factorset(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 17 2019

b[n_] := Count[FactorInteger[n][[All, 1]], p_ /; Mod[p, 3] == 1]; b[1] = 0;
a[n_] := EulerPhi[n]/3^b[n];
Table[a[n], {n, 1, 81}] (* Jean-François Alcover, Feb 17 2019 *)
f[p_, e_] := (p - 1)*p^(e - 1)/If[Mod[p, 3] == 1, 3, 1]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 30 2024 *)

{b(n)=my(f=factor(n)[, 1]); sum(i=1, #f, f[i]%3==1)};
{a(n)= eulerphi(n)/3^b(n)};
vector(80, n, a(n)) \\ G. C. Greubel, Feb 17 2019

a(n) = {my(f = factor(n)); prod(i = 1, #f~, (f[i,1]-1)*f[i,1]^(f[i,2]-1)/if(f[i,1] % 3 == 1, 3,1));} \\ Amiram Eldar, Nov 30 2024

From Amiram Eldar, Nov 30 2024: (Start)
a(n) = A000010(n)/3^A005088(n) = A000010(n)/A115069(n).
Multiplicative with a(p^e) = (p-1)*p^(e-1)/3 if p == 1 (mod 3), and (p-1)*p^(e-1) otherwise. (End)

a(1)=1 prepended by Alois P. Heinz, Feb 17 2019

Keyword mult added by Amiram Eldar, Nov 30 2024

cp's OEIS Frontend

A327924 Square array read by ascending antidiagonals: T(m,n) is the number of non-isomorphic groups G such that G is the semidirect product of C_m and C_n, where C_m is a normal subgroup of G and C_n is a subgroup of G.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A386236 Ratio of the period and the reduced period of the Fibonacci 3-step sequence A000073 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A115069 a(n) = 3^b(n), where b(n) is #{primes p=1 mod 3 dividing n}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A224516 Number of solutions to x^4 - x == 0 (mod n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A276919 Number of solutions to x^3 + y^3 + z^3 + t^3 == 1 (mod n) for 1 <= x, y, z, t <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A276920 Number of solutions to x^3 + y^3 + z^3 + t^3 == 0 (mod n) for 1 <= x, y, z, t <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

A327925 Irregular table read by rows: T(m,n) is the number of non-isomorphic groups G such that G is the semidirect product of C_m and C_n, where C_m is a normal subgroup of G and C_n is a subgroup of G, 1 <= n <= A002322(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula