A381348 Irregular triangle read by rows in which row n lists the largest subset of Z/nZ fixed by x -> x^2.

0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 3, 4, 0, 1, 2, 4, 0, 1, 0, 1, 4, 7, 0, 1, 5, 6, 0, 1, 3, 4, 5, 9, 0, 1, 4, 9, 0, 1, 3, 9, 0, 1, 2, 4, 7, 8, 9, 11, 0, 1, 6, 10, 0, 1, 0, 1, 0, 1, 4, 7, 9, 10, 13, 16, 0, 1, 4, 5, 6, 7, 9, 11, 16, 17, 0, 1, 5, 16, 0, 1, 4, 7, 9, 15, 16, 18

Offset: 1

Author

Aloe Poliszuk, Feb 20 2025

Keywords

• nonn
• tabf

Comments

Row n has length A277847(n).

Repeated squaring (application of f: x -> x^2) of the set of integers mod n results in a set that is fixed under f. Row n lists this set for modulus n. The number of applications of f to reach this fixed set is A309414(n).

Equivalently, row n lists the set of elements x such that, for some k, x^(2^k) == x (mod n), i.e. those x which are part of a cycle under x -> x^2 mod n.

For prime p of the form 4k + 3 (A002145), row p gives exactly the set of quadratic residues mod p. As such, row p has (p + 1) / 2 elements.

When n is a prime power (A000961) the product of row n (excluding 0) is equivalent to 1 mod n. Otherwise this product is equivalent to 0.

Examples

			Triangle begins:
  (mod 1)     0;
  (mod 2)     0, 1;
  (mod 3)     0, 1;
  (mod 4)     0, 1;
  (mod 5)     0, 1;
  (mod 6)     0, 1, 3, 4;
  (mod 7)     0, 1, 2, 4;
  (mod 8)     0, 1;
  (mod 9)     0, 1, 4, 7;
  (mod 10)    0, 1, 5, 6;
  (mod 11)    0, 1, 3, 4, 5, 9;
  (mod 12)    0, 1, 4, 9;
  (mod 13)    0, 1, 3, 9;
  (mod 14)    0, 1, 2, 4, 7, 8, 9, 11;
  (mod 15)    0, 1, 6, 10;
  (mod 16)    0, 1;
  (mod 17)    0, 1;
              ...
		

Links

• Aloe Poliszuk, First 349 rows, flattened into a sequence of n, a(n) for n = 1..13345

Crossrefs

Cf. A002145, A096008, A096088, A277847, A309414.

Programs

PARI

row(n)=my(p=[0..n>>1], c=[0..n>>1]); until(p==c, p=c; c=Set([lift(Mod(v, n)^2)|v<-c])); return(c);

Python

def row(n):
    l = set(range((n >> 1) + 1))
    while True:
        newl = {x**2 % n for x in l}
        if newl == l: break
        l = newl
    return l