cp's OEIS Frontend

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

%I A381798 #7 Mar 14 2025 20:05:08
%S A381798 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,
%T A381798 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,
%U A381798 12,2,7,11,7,9,18,2,11,14,23,2,12,2,38,24,22,14,17
%N A381798 Number of residues r such that p^m is congruent to r (mod n), where prime p | n and m >= 0.
%C A381798 Number of power residues r (mod n) of prime powers p^m such that p | n and m >= 0.
%C A381798 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.
%C A381798 This sequence is card(union(S(p,n))) where S(p,n) is taken across prime factors p | n.
%H A381798 Michael De Vlieger, <a href="/A381798/b381798.txt">Table of n, a(n) for n = 1..5000</a>
%H A381798 Michael De Vlieger, <a href="/A381798/a381798.png">Log log scatterplot of a(n)</a>, 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.
%F A381798 a(1) = 1.
%F A381798 a(p) = 2 since S(p,p) = {0, 1}.
%F A381798 a(p^m) = m+1 since S(p,p^m) = {0} U {p^i, i < m}.
%e A381798 Table of n, a(n) for select values of n, showing the residues listed in row n of A381799:
%e A381798  n  a(n)  row n of A381799.
%e A381798 ------------------------------------------------
%e A381798  1    1   {0}
%e A381798  2    2   {0,1}
%e A381798  4    3   {0,1,2}
%e A381798  6    4   {1,2,3,4}
%e A381798  8    4   {0,1,2,4}
%e A381798 10    6   {1,2,4,5,6,8}
%e A381798 12    6   {1,2,3,4,8,9}
%e A381798 14    5   {1,2,4,7,8}
%e A381798 15    7   {1,3,5,6,9,10,12}
%e A381798 18    9   {1,2,3,4,8,9,10,14,16}
%e A381798 20    7   {1,2,4,5,8,12,16}
%e A381798 21    8   {1,3,6,7,9,12,15,18}
%e A381798 22   12   {1,2,4,6,8,10,11,12,14,16,18,20}
%e A381798 24    7   {1,2,3,4,8,9,16}
%e A381798 26   14   {1,2,4,6,8,10,12,13,14,16,18,20,22,24}
%e A381798 28    7   {1,2,4,7,8,16,21}
%e A381798 30   11   {1,2,3,4,5,8,9,16,21,25,27}
%e A381798 33    8   {1,3,9,11,12,15,22,27}
%e A381798 34   10   {1,2,4,8,16,17,18,26,30,32}
%e A381798 35   11   {1,5,7,10,14,15,20,21,25,28,30}
%e A381798 36   11   {1,2,3,4,8,9,16,20,27,28,32}
%e A381798 a(1) = 1 since 1 is the empty product.
%e A381798 a(2) = 2 since S(2,2) = {0, 1}.
%e A381798 a(4) = 3 since S(2,4) = {1,2,0}.
%e A381798 a(6) = 4 since {1,2,3,4} is the union of S(2,6) = {1,2,4} and S(3,6) = {1,3}.
%e A381798 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}.
%e A381798 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}.
%e A381798 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.
%t A381798 {1}~Join~Table[CountDistinct@ Flatten@ Map[(p = #; NestWhileList[Mod[p*#, n] &, 1, UnsameQ, All]) &, FactorInteger[n][[All, 1]] ], {n, 2, 120}]
%Y A381798 Cf. A000961, A381799.
%K A381798 nonn
%O A381798 1,2
%A A381798 _Michael De Vlieger_, Mar 07 2025