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,12

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.

Links

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

Example

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;
              ...

Prog

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

Crossrefs

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

Sequence in context: A087666 A061353 A016653 * A096088 A107681 A021298

Adjacent sequences: A381345 A381346 A381347 * A381349 A381350 A381351

Keyword

nonn,tabf

Author

Aloe Poliszuk, Feb 20 2025

Status

approved