login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Table of n, a(n) for n = 2..10000

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) = prod_{1<=i<=k} (p_i^(r_i)+1) if m=0,

...a(n) = 2*prod_{1<=i<=k} (p_i^(r_i)+1) if m=1,

...a(n) = 6*prod_{1<=i<=k} (p_i^(r_i)+1) if m=2,

...a(n) = (4+2^(m-1)+2^m)*prod_{1<=i<=k} (p_i^(r_i)+1) if m>=3.

a(n) = sum_{a in row(n) of A228179} gcd(a+1,n).

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):

seq(a(n), n=2..100);  # Alois P. Heinz, Jan 20 2014

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 *)

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))

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

CROSSREFS

Cf. A002618, A228179, A147848, A060594, A283796.

Sequence in context: A267460 A092989 A065558 * A035280 A244367 A020887

Adjacent sequences:  A235381 A235382 A235383 * A235385 A235386 A235387

KEYWORD

nonn,easy,look,mult,nice,changed

AUTHOR

Tom Edgar, Jan 08 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 3 04:21 EDT 2020. Contains 333195 sequences. (Running on oeis4.)