A381799 Irregular triangle read by rows, where row n is a list of residues of powers of prime factors of n (mod n).

0, 0, 1, 0, 1, 0, 1, 2, 0, 1, 1, 2, 3, 4, 0, 1, 0, 1, 2, 4, 0, 1, 3, 1, 2, 4, 5, 6, 8, 0, 1, 1, 2, 3, 4, 8, 9, 0, 1, 1, 2, 4, 7, 8, 1, 3, 5, 6, 9, 10, 12, 0, 1, 2, 4, 8, 0, 1, 1, 2, 3, 4, 8, 9, 10, 14, 16, 0, 1, 1, 2, 4, 5, 8, 12, 16, 1, 3, 6, 7, 9, 12, 15, 18

Offset: 1

Author

Michael De Vlieger, Mar 07 2025

Keywords

• nonn
• tabf

Comments

Define S(p,n) to be the set of residues r (mod n) taken by the power range of prime divisor p, i.e., {p^m, m >= 1}. Examples: S(2,10) = {1, 2, 4, 8, 6}, while S(2,8) = {0, 1, 2, 4} and S(2,12) = {1, 2, 4, 8}; S(3,6) = {1, 3}, S(3,9) = {0, 1, 3}, S(3,12) = {1, 3, 9}, etc.

Define T(n) to be the (sorted) union of S(p,n) for all prime factors p | n.

Row n of this table is T(n).

For n > 1, the intersection of row n of this table and row n of A038566 is {1}. Thus, 1 appears in each row except for n = 1, since p^0 = 1 for all primes p | n.

The number 0 appears in T(p^m) (where p is prime and m >= 1) since p^m is congruent to 0 (mod p^m).

Zero does not appear in T(n) for n in A024619.

Examples

			Triangle begins:
 n   row n
--------------------------
 1:  0;
 2:  0, 1;
 3:  0, 1;
 4:  0, 1, 2;
 5:  0, 1;
 6:  1, 2, 3, 4;
 7:  0, 1;
 8:  0, 1, 2, 4;
 9:  0, 1, 3;
10:  1, 2, 4, 5, 6, 8;
11:  0, 1;
12:  1, 2, 3, 4, 8, 9; etc.
For n = 10, we have S(2,10) = {1, 2, 4, 8, 6}, S(5,10) = {1, 5}, thus T(10) = {1, 2, 4, 5, 6, 8}.
For n = 12, we have S(2,12) = {1, 2, 4, 8}, S(3,12) = {1, 3, 9}, thus T(12) = {1, 2, 3, 4, 8, 9}.
For n = 16, we have S(2,16) = {1, 2, 4, 8, 0}, thus T(16) = {0, 1, 2, 4, 8}.
For n = 30, we have S(2,30) = {1, 2, 4, 8, 16}, S(3,30) = {1, 3, 9, 27, 21}, and S(5,30) = {1, 5, 25}, so T(30) = {1, 2, 3, 4, 5, 8, 9, 16, 21, 25, 27}, etc.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..17305 (rows n = 1..500, flattened.)
• Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..36, showing reduced residues mod n in gray and labeling terms in row n. The number n appears on the left in red italic, and row length A381798(n) in blue at right.
• Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..5000.

Crossrefs

Cf. A024619, A038566, A121998, A381798.

Programs

Mathematica

{{0}}~Join~Table[Union@ Flatten@ Map[(p = #; NestWhileList[Mod[p*#, n] &, 1, UnsameQ, All]) &, FactorInteger[n][[All, 1]] ], {n, 2, 30}]

Formula

Row 1 = {0} since 1 is the empty product.

For prime p, row p is {0, 1}.

For proper prime power p^m, m > 1, row p^m is the union of {0} and p^i, i < m.

A381798(n) = length of row n.