cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A277776 Triangle T(n,k) in which the n-th row contains the increasing list of nontrivial square roots of unity mod n; n>=1.

Original entry on oeis.org

3, 5, 5, 7, 4, 11, 7, 9, 9, 11, 8, 13, 5, 7, 11, 13, 17, 19, 13, 15, 11, 19, 15, 17, 10, 23, 6, 29, 17, 19, 14, 25, 9, 11, 19, 21, 29, 31, 13, 29, 21, 23, 19, 26, 7, 17, 23, 25, 31, 41, 16, 35, 25, 27, 21, 34, 13, 15, 27, 29, 41, 43, 20, 37, 11, 19, 29, 31, 41
Offset: 1

Views

Author

Alois P. Heinz, Oct 30 2016

Keywords

Comments

Rows with indices n in A033948 (or with A046144(n)=0) are empty. Indices of nonempty rows are given by A033949.
This is A228179 without the trivial square roots {1, n-1}.
The number of terms in each nonempty row n is even: A060594(n)-2.

Examples

			Row n=8 contains 3 and 5 because 3*3 = 9 == 1 mod 8 and 5*5 = 25 == 1 mod 8.
Triangle T(n,k) begins:
08 :   3,  5;
12 :   5,  7;
15 :   4, 11;
16 :   7,  9;
20 :   9, 11;
21 :   8, 13;
24 :   5,  7, 11, 13, 17, 19;
28 :  13, 15;
30 :  11, 19;

Links

Crossrefs

Columns k=1-2 give: A082568, A357099.
Last elements of nonempty rows give A277777.
Cf. A033948, A033949, A046144, A060594, A228179.

Programs

  • Maple
    T:= n-> seq(`if`(i*i mod n=1, i, [][]), i=2..n-2):
seq(T(n), n=1..100);
# second Maple program:
T:= n-> ({numtheory[rootsunity](2, n)} minus {1, n-1})[]:
seq(T(n), n=1..100);
  • Mathematica
    T[n_] := Table[If[Mod[i^2, n] == 1, i, Nothing], {i, 2, n-2}];
Select[Array[T, 100], # != {}&] // Flatten (* Jean-François Alcover, Jun 18 2018, from first Maple program *)
  • Python
    from itertools import chain, count, islice
from sympy.ntheory import sqrt_mod_iter
def A277776_gen(): # generator of terms
    return chain.from_iterable((sorted(filter(lambda m:1A277776_list = list(islice(A277776_gen(),30)) # Chai Wah Wu, Oct 26 2022

A235384 Number of involutions in the group Aff(Z/nZ).

Original entry on oeis.org

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
Offset: 2

Views

Author

Tom Edgar, Jan 08 2014

Keywords

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.

Examples

			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.

Links

Crossrefs

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

Programs

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

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

A358016 a(n) is the largest k <= n-2 such that k^2 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 5, 1, 1, 1, 7, 1, 1, 11, 9, 1, 1, 1, 11, 13, 1, 1, 19, 1, 1, 1, 15, 1, 19, 1, 17, 23, 1, 29, 19, 1, 1, 25, 31, 1, 29, 1, 23, 26, 1, 1, 41, 1, 1, 35, 27, 1, 1, 34, 43, 37, 1, 1, 49, 1, 1, 55, 33, 51, 43, 1, 35, 47, 41, 1, 55, 1, 1, 49, 39, 43, 53
Offset: 3

Views

Author

Darío Clavijo, Oct 24 2022

Keywords

Comments

It appears that the terms > 1 comprise the sequence A277777.
What is the asymptotic behavior of this sequence? Numerically, it seems like sum_{3 <= n <= x} a(n) is of the order x log x or so. - Charles R Greathouse IV, Oct 27 2022

Links

Crossrefs

Cf. A228179, A277777, A033948, A060594.

Programs

  • Mathematica
    lkn[n_]:=Module[{k=n-2},While[PowerMod[k,2,n]!=1,k--];k]; Array[lkn,80,3] (* Harvey P. Dale, Sep 01 2023 *)
  • PARI
    a(n) = forstep(k=n-2, 1, -1, if ((gcd(k, n) == 1) && (lift(Mod(1,n)/k) == k), return(k));); \\ Michel Marcus, Oct 25 2022
  • PARI
    rootsOfUnity(p,e,pe=p^e)=if(p>2, return(Mod([1,-1],pe))); if(e==1, return(Mod([1],2))); if(e==2, return(Mod([1,3],4))); Mod([1,pe/2-1,pe/2+1,-1],pe)
a(n,f=factor(n))=my(v=apply(x->rootsOfUnity(x[1],x[2]),Col(f)),r,t); forvec(u=vector(#v,i,[1,#v[i]]), t=lift(chinese(vector(#u,i,v[i][u[i]]))); if(t>r && tCharles R Greathouse IV, Oct 26 2022
  • Python
    def a(n):
  for k in range(n - 2, 0, -1):
    if pow(k,2,n) == 1: return k
  • Python
    from sympy.ntheory import sqrt_mod_iter
def A358016(n): return max(filter(lambda k: k<=n-2,sqrt_mod_iter(1,n))) # Chai Wah Wu, Oct 26 2022
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.