A073103 -id:A073103 - 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.

A073503 Numbers n such that the number of solutions to x^4 == 1 (mod n) is twice the number of solutions of x^2 == 1 (mod n).

Original entry on oeis.org

5, 10, 13, 15, 16, 17, 20, 25, 26, 29, 30, 32, 34, 35, 37, 39, 40, 41, 45, 48, 50, 51, 52, 53, 55, 58, 60, 61, 64, 68, 70, 73, 74, 75, 78, 82, 87, 89, 90, 91, 95, 96, 97, 100, 101, 102, 104, 105, 106, 109, 110, 111, 112, 113, 115, 116, 117, 119, 120, 122, 123, 125

Offset: 1

Benoit Cloitre, Aug 19 2002

Conjectures: 2n > a(n) or 2n < a(n) for infinitely many values of n and abs(a(n)-2n) < sqrt(n) for n > 45. a(n)=2n for n = 318, 338, 350, 488, 490, 492, 494,...

Numbers divisible by 16 which have no prime factors = 1 mod 4, together with numbers not divisible by 16 which have exactly one prime factor = 1 mod 4. This refutes the conjectures. - Charles R Greathouse IV, Apr 16 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A060594, A073103.

Select[Range[3, 125], Length[Reduce[x^4 - 1 == 0, x, Modulus -> #]] == 2*Length[Reduce[x^2 - 1 == 0, x, Modulus -> #]] &] (* Jayanta Basu, Jul 01 2013 *)

is(n)=my(v=factor(n)[,1]%4, s=sum(i=1,#v,v[i]==1), e=valuation(n, 2)); s==(e<4) \\ Charles R Greathouse IV, Apr 16 2012

a(n) seems to be asymptotic to 2n.

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.

A167857 Numbers whose divisors are represented by an integer polynomial.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 10, 11, 13, 17, 19, 22, 23, 25, 29, 31, 34, 37, 41, 43, 46, 47, 49, 53, 55, 58, 59, 61, 67, 71, 73, 79, 82, 83, 85, 89, 91, 94, 97, 101, 103, 106, 107, 109, 113, 115, 118, 121, 127, 131, 133, 137, 139, 142, 145, 149, 151, 157, 163, 166, 167, 169, 171

Offset: 1

T. D. Noe, Nov 13 2009

nonn

That is, these numbers n have the property that there is a polynomial f(x) with integer coefficients whose values at x=0..tau(n)-1 are the divisors of n, where tau(n) is the number of divisors of n.

Every prime has this property, as do 1 and 9, the squares of primes of the form 6k+1, and semiprimes p*q with p and q both primes of the form 3k-1 or 3k+1. Terms of the form p^2*q also appear. We can find terms of the form p^m for any m. For example, 2311^13 is the smallest 13th power that appears. For any m, it seems that p^m appears for p a prime of the form k*m#+1, where m# is the product of the primes up to m. Are there terms with three distinct prime divisors?

			The divisors of 55 are (1, 5, 11, 55). The polynomial 1+15x-17x^2+6x^3 takes these values at x=0..3.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A108164, A108166, A112774 (forms of semiprimes)
Cf. A002476 (primes of the form 6k+1)
Cf. A132230 (primes of the form 30k+1)
Cf. A073103 (primes of the form 210k+1)
Cf. A073917 (least prime of the form k*prime(n)#+1)

Select[Range[1000], And @@ IntegerQ /@ CoefficientList[Expand[InterpolatingPolynomial[Divisors[ # ], x+1]], x] &]

is(n)=my(d=divisors(n));denominator(content(polinterpolate([0..#d-1],d))) == 1 \\ Charles R Greathouse IV, Jan 29 2016

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

A073503 Numbers n such that the number of solutions to x^4 == 1 (mod n) is twice the number of solutions of x^2 == 1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A167857 Numbers whose divisors are represented by an integer polynomial.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI