|
|
A235384
|
|
Number of involutions in the group Aff(Z/nZ).
|
|
2
|
|
|
2, 4, 6, 6, 8, 8, 16, 10, 12, 12, 24, 14, 16, 24, 28, 18, 20, 20, 36, 32, 24, 24, 64, 26, 28, 28, 48, 30, 48, 32, 52, 48, 36, 48, 60, 38, 40, 56, 96, 42, 64, 44, 72, 60, 48, 48, 112, 50, 52, 72, 84, 54, 56, 72, 128, 80, 60, 60, 144, 62, 64, 80, 100, 84
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
Aff(Z/nZ) is the group of functions on Z/nZ of the form x->ax+b where a and b are elements of Z/nZ and gcd(a,n)=1.
Since Aff(Z/nZ) is isomorphic to the automorphism group of the dihedral group with 2n elements (when n>=3), this is the number of automorphisms of the dihedral group with 2n elements that have order 1 or 2.
The sequence is multiplicative: a(k*m) = a(k)*a(m) if m and k are coprime.
When n=26, this is the number of affine ciphers where encryption and decryption use the same function.
|
|
LINKS
|
K. K. A. Cunningham, Tom Edgar, A. G. Helminck, B. F. Jones, H. Oh, R. Schwell and J. F. Vasquez, On the Structure of Involutions and Symmetric Spaces of Dihedral Groups, Note di Mat., Volume 34, No. 2, 2014.
|
|
FORMULA
|
Suppose n = 2^m*p_1^(r_1)*p_2^(r_2)*...*p_k^(r_k) where each p_i>2 is prime, r_i>0 for all i, and m>=0 is the prime factorization of n, then:
...a(n) = Product_{1<=i<=k} (p_i^(r_i)+1) if m=0,
...a(n) = 2*Product_{1<=i<=k} (p_i^(r_i)+1) if m=1,
...a(n) = 6*Product_{1<=i<=k} (p_i^(r_i)+1) if m=2,
...a(n) = (4+2^(m-1)+2^m)*Product_{1<=i<=k} (p_i^(r_i)+1) if m>=3.
a(n) = Sum_{a in row(n) of A228179} gcd(a+1,n).
Sum_{k=1..n} a(k) ~ c * n^2, where c = zeta(2)/(2*zeta(3)) = 0.684216... (A335005). - Amiram Eldar, Dec 05 2022
|
|
EXAMPLE
|
Since 18 = 2*3^2, we get a(18) = 2*(3^2+1) = 20. Since 120 = 2^3*3*5, we have a(120) = (4+2^2+2^3)*(3+1)*(5+1) = 384.
|
|
MAPLE
|
a:= n-> add(`if`(irem(k^2, n)=1, igcd(n, k+1), 0), k=1..n-1):
|
|
MATHEMATICA
|
a[n_] := Sum[If[Mod[k^2, n] == 1, GCD[n, k+1], 0], {k, 1, n-1}]; Table[a[n], {n, 2, 100}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)
f[p_, e_] := p^e + 1; f[2, 1] = 2; f[2, 2] = 6; f[2, e_] := 3*2^(e - 1) + 4; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100, 2] (* Amiram Eldar, Dec 05 2022 *)
|
|
PROG
|
(Sage)
def a(n):
L=list(factor(n))
if L[0][0]==2:
m=L[0][1]
L.pop(0)
else:
m=0
order=prod([x[0]^x[1]+1 for x in L])
if m==1:
order=2*order
elif m==2:
order=6*order
elif m>=3:
order=(4+2^(m-1)+2^m)*order
return order
[a(i) for i in [2..100]]
(Sage)
def b(n):
sum = 0
for a in [x for x in range(n) if ((x^2) % n == 1)]:
sum += gcd(a+1, n)
return sum
[b(i) for i in [2..100]]
(PARI) A034448(n, f=factor(n))=factorback(vector(#f~, i, f[i, 1]^f[i, 2]+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|