A381800 a(n) = number of distinct residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

1, 2, 2, 3, 2, 5, 2, 4, 3, 7, 2, 8, 2, 6, 8, 5, 2, 12, 2, 9, 9, 13, 2, 11, 3, 15, 4, 9, 2, 19, 2, 6, 9, 11, 12, 16, 2, 21, 6, 12, 2, 24, 2, 16, 15, 14, 2, 16, 3, 28, 20, 17, 2, 31, 8, 12, 21, 31, 2, 28, 2, 8, 13, 7, 10, 32, 2, 13, 15, 35, 2, 20, 2, 39, 29, 24

Offset: 1

Author

Michael De Vlieger, Mar 07 2025

Keywords

• nonn

Examples

			 n  a(n)  row n of A381801
----------------------------------------------
 1    1   {0}
 2    2   {0,1}
 3    2   {0,1}
 4    3   {0,1,2}
 6    5   {0,1,2,3,4}
 8    4   {0,1,2,4}
10    7   {0,1,2,4,5,6,8}
12    8   {0,1,2,3,4,6,8,9}
14    6   {0,1,2,4,7,8}
15    8   {0,1,3,5,6,9,10,12}
18   12   {0,1,2,3,4,6,8,9,10,12,14,16}
20    9   {0,1,2,4,5,8,10,12,16}
21    9   {0,1,3,6,7,9,12,15,18}
22   13   {0,1,2,4,6,8,10,11,12,14,16,18,20}
24   11   {0,1,2,3,4,6,8,9,12,16,18}
26   15   {0,1,2,4,6,8,10,12,13,14,16,18,20,22,24}
28    9   {0,1,2,4,7,8,14,16,21}
30   19   {0,1,2,3,4,5,6,8,9,10,12,15,16,18,20,21,24,25,27}
36   16   {0,1,2,3,4,6,8,9,12,16,18,20,24,27,28,32}
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..5000
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..5000, 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.
• Michael De Vlieger, Faster code for A381800 and A381801, 2025.

Crossrefs

Cf. A000005, A010846, A024619, A051953, A381798, A381801.

Programs

Mathematica

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

Formula

a(n) = length of row n of A381801.

a(1) = 1 since 1 is the empty product.

A010846(n) <= a(n) <= A051953(n).

a(n) >= 2 for n > 1.

For prime p, a(p) = A010846(p^m) = A000005(p^m) = A381798(p) = 2.

For prime power p^m, m > 0, a(p^m) = A010846(p^m) = A000005(p^m) = A381798(p^m) = m+1.

For n in A024619, a(n) > A381798(n).