cp's OEIS Frontend

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

%I A381348 #67 Apr 07 2025 23:39:10
%S A381348 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,
%T A381348 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,
%U A381348 1,4,5,6,7,9,11,16,17,0,1,5,16,0,1,4,7,9,15,16,18
%N A381348 Irregular triangle read by rows in which row n lists the largest subset of Z/nZ fixed by x -> x^2.
%C A381348 Row n has length A277847(n).
%C A381348 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).
%C A381348 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.
%C A381348 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.
%C A381348 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.
%H A381348 Aloe Poliszuk, <a href="/A381348/b381348.txt">First 349 rows, flattened into a sequence of n, a(n) for n = 1..13345</a>
%e A381348 Triangle begins:
%e A381348   (mod 1)     0;
%e A381348   (mod 2)     0, 1;
%e A381348   (mod 3)     0, 1;
%e A381348   (mod 4)     0, 1;
%e A381348   (mod 5)     0, 1;
%e A381348   (mod 6)     0, 1, 3, 4;
%e A381348   (mod 7)     0, 1, 2, 4;
%e A381348   (mod 8)     0, 1;
%e A381348   (mod 9)     0, 1, 4, 7;
%e A381348   (mod 10)    0, 1, 5, 6;
%e A381348   (mod 11)    0, 1, 3, 4, 5, 9;
%e A381348   (mod 12)    0, 1, 4, 9;
%e A381348   (mod 13)    0, 1, 3, 9;
%e A381348   (mod 14)    0, 1, 2, 4, 7, 8, 9, 11;
%e A381348   (mod 15)    0, 1, 6, 10;
%e A381348   (mod 16)    0, 1;
%e A381348   (mod 17)    0, 1;
%e A381348               ...
%o A381348 (Python)
%o A381348 def row(n):
%o A381348     l = set(range((n >> 1) + 1))
%o A381348     while True:
%o A381348         newl = {x**2 % n for x in l}
%o A381348         if newl == l: break
%o A381348         l = newl
%o A381348     return l
%o A381348 (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);
%Y A381348 Cf. A002145, A096008, A096088, A277847, A309414.
%K A381348 nonn,tabf
%O A381348 1,12
%A A381348 _Aloe Poliszuk_, Feb 20 2025