|
%I #51 Dec 05 2022 04:45:46
%S 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,
%T 28,48,30,48,32,52,48,36,48,60,38,40,56,96,42,64,44,72,60,48,48,112,
%U 50,52,72,84,54,56,72,128,80,60,60,144,62,64,80,100,84
%N Number of involutions in the group Aff(Z/nZ).
%C 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.
%C 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.
%C The sequence is multiplicative: a(k*m) = a(k)*a(m) if m and k are coprime.
%C When n=26, this is the number of affine ciphers where encryption and decryption use the same function.
%H Alois P. Heinz, <a href="/A235384/b235384.txt">Table of n, a(n) for n = 2..10000</a>
%H K. K. A. Cunningham, Tom Edgar, A. G. Helminck, B. F. Jones, H. Oh, R. Schwell and J. F. Vasquez, <a href="http://dx.doi.org/10.1285/i15900932v34n2p23">On the Structure of Involutions and Symmetric Spaces of Dihedral Groups</a>, Note di Mat., Volume 34, No. 2, 2014.
%F 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:
%F ...a(n) = Product_{1<=i<=k} (p_i^(r_i)+1) if m=0,
%F ...a(n) = 2*Product_{1<=i<=k} (p_i^(r_i)+1) if m=1,
%F ...a(n) = 6*Product_{1<=i<=k} (p_i^(r_i)+1) if m=2,
%F ...a(n) = (4+2^(m-1)+2^m)*Product_{1<=i<=k} (p_i^(r_i)+1) if m>=3.
%F a(n) = Sum_{a in row(n) of A228179} gcd(a+1,n).
%F Sum_{k=1..n} a(k) ~ c * n^2, where c = zeta(2)/(2*zeta(3)) = 0.684216... (A335005). - _Amiram Eldar_, Dec 05 2022
%e 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.
%p a:= n-> add(`if`(irem(k^2, n)=1, igcd(n, k+1), 0), k=1..n-1):
%p seq(a(n), n=2..100); # _Alois P. Heinz_, Jan 20 2014
%t 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_ *)
%t 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 *)
%o (Sage)
%o def a(n):
%o L=list(factor(n))
%o if L[0][0]==2:
%o m=L[0][1]
%o L.pop(0)
%o else:
%o m=0
%o order=prod([x[0]^x[1]+1 for x in L])
%o if m==1:
%o order=2*order
%o elif m==2:
%o order=6*order
%o elif m>=3:
%o order=(4+2^(m-1)+2^m)*order
%o return order
%o [a(i) for i in [2..100]]
%o (Sage)
%o def b(n):
%o sum = 0
%o for a in [x for x in range(n) if ((x^2) % n == 1)]:
%o sum += gcd(a+1,n)
%o return sum
%o [b(i) for i in [2..100]]
%o (PARI) A034448(n,f=factor(n))=factorback(vector(#f~,i,f[i,1]^f[i,2]+1))
%o a(n)=my(m=valuation(n,2)); if(m==0,1,m==1,2,m==2,6,4+3<<(m-1))*A034448(n>>m) \\ _Charles R Greathouse IV_, Jul 29 2016
%Y Cf. A002618, A228179, A147848, A060594, A283796, A335005.
%K nonn,easy,look,mult,nice
%O 2,1
%A _Tom Edgar_, Jan 08 2014
|
