A381798 Number of residues r such that p^m is congruent to r (mod n), where prime p | n and m >= 0.

1, 2, 2, 3, 2, 4, 2, 4, 3, 6, 2, 6, 2, 5, 7, 5, 2, 9, 2, 7, 8, 12, 2, 7, 3, 14, 4, 7, 2, 11, 2, 6, 8, 10, 11, 11, 2, 20, 5, 9, 2, 14, 2, 14, 12, 13, 2, 10, 3, 23, 19, 15, 2, 22, 7, 8, 20, 30, 2, 12, 2, 7, 11, 7, 9, 18, 2, 11, 14, 23, 2, 12, 2, 38, 24, 22, 14, 17

Offset: 1

Author

Michael De Vlieger, Mar 07 2025

Keywords

• nonn

Comments

Number of power residues r (mod n) of prime powers p^m such that p | n and m >= 0.

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.

This sequence is card(union(S(p,n))) where S(p,n) is taken across prime factors p | n.

Examples

			Table of n, a(n) for select values of n, showing the residues listed in row n of A381799:
 n  a(n)  row n of A381799.
------------------------------------------------
 1    1   {0}
 2    2   {0,1}
 4    3   {0,1,2}
 6    4   {1,2,3,4}
 8    4   {0,1,2,4}
10    6   {1,2,4,5,6,8}
12    6   {1,2,3,4,8,9}
14    5   {1,2,4,7,8}
15    7   {1,3,5,6,9,10,12}
18    9   {1,2,3,4,8,9,10,14,16}
20    7   {1,2,4,5,8,12,16}
21    8   {1,3,6,7,9,12,15,18}
22   12   {1,2,4,6,8,10,11,12,14,16,18,20}
24    7   {1,2,3,4,8,9,16}
26   14   {1,2,4,6,8,10,12,13,14,16,18,20,22,24}
28    7   {1,2,4,7,8,16,21}
30   11   {1,2,3,4,5,8,9,16,21,25,27}
33    8   {1,3,9,11,12,15,22,27}
34   10   {1,2,4,8,16,17,18,26,30,32}
35   11   {1,5,7,10,14,15,20,21,25,28,30}
36   11   {1,2,3,4,8,9,16,20,27,28,32}
a(1) = 1 since 1 is the empty product.
a(2) = 2 since S(2,2) = {0, 1}.
a(4) = 3 since S(2,4) = {1,2,0}.
a(6) = 4 since {1,2,3,4} is the union of S(2,6) = {1,2,4} and S(3,6) = {1,3}.
a(10) = 6 since {1,2,4,5,6,8} is the union of S(2,10) = {1,2,4,8,6} and S(5,10) = {1,5}.
a(12) = 6 since {1,2,3,4,8,9} is the union of S(2,12) = {1,2,4,8} and S(3,12) = {1,3,9}.
a(30) = 11 since {1,2,3,4,5,8,9,16,21,25,27} is the union of S(2,30) = {1,2,4,8,16}, S(3,30) = {1,3,9,27,21}, and S(5,30) = {1,5,25}, etc.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..5000
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2310, showing a(n) for prime n in red, a(n) for proper prime power n in gold, a(n) such that n is squarefree and composite in green, and a(n) such that n is neither squarefree nor prime power in blue and magenta, where the latter color also signifies n is powerful but not a prime power.

Crossrefs

Cf. A000961, A381799.

Programs

Mathematica

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

Formula

a(1) = 1.

a(p) = 2 since S(p,p) = {0, 1}.

a(p^m) = m+1 since S(p,p^m) = {0} U {p^i, i < m}.