A381802 a(n) = number of distinct residues r mod n of numbers k congruent to r (mod n) such that rad(k) does not divide n, where rad = A007947.

0, 0, 1, 1, 3, 1, 5, 4, 6, 3, 9, 4, 11, 8, 7, 11, 15, 6, 17, 11, 12, 9, 21, 13, 22, 11, 23, 19, 27, 11, 29, 26, 24, 23, 23, 20, 35, 17, 33, 28, 39, 18, 41, 28, 30, 32, 45, 32, 46, 22, 31, 35, 51, 23, 47, 44, 36, 27, 57, 32, 59, 54, 50, 57, 55, 34, 65, 55, 54, 35

Offset: 1

Author

Michael De Vlieger, Mar 14 2025

Keywords

• nonn

Examples

			a(n) = 0 for n = 1..2, since there do not exist any residues mod n that do not represent a power of n.
 n  a(n)  [0..n-1] \ row n of A381801.
------------------------------------------------
 6    1   {5}
10    3   {3,7,9}
12    4   {5,7,10,11}
14    8   {3,5,6,9,10,11,12,13}
15    7   {2,4,7,8,11,13,14}
18    6   {5,7,11,13,15,17}
20   11   {3,6,7,9,11,13,14,15,17,18,19}
21   12   {2,4,5,8,10,11,13,14,16,17,19,20}
22    9   {3,5,7,9,13,15,17,19,21}
24   13   {5,7,10,11,13,14,15,17,19,20,21,22,23}
26   11   {3,5,7,9,11,15,17,19,21,23,25}
28   19   {3,5,6,9,10,11,12,13,15,17,18,19,20,22,23,24,25,26,27}
30   11   {7,11,13,14,17,19,22,23,26,28,29}
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^16, showing prime n in red, proper prime power n in gold, squarefree composite n in green, and n that is neither squarefree nor prime power in blue and magenta, with magenta also representing powerful n that is not a prime power.

Crossrefs

Cf. A000010, A381800, A381801.

Programs

Mathematica

f[x_] := Block[{c, ff, m, r, p, s, w}, c[_] := True;
  ff = FactorInteger[x][[All, 1]]; w = Length[ff]; s = {1};
  Do[Set[p[i], ff[[i]]], {i, w}];
  Do[Set[s, Union@ Flatten@ Join[s, #[[-1, 1]] ] ] &@ Reap@
    Do[m = s[[j]];
      While[Sow@ Set[r, Mod[m*p[i], x]];
       c[r], c[r] = False;
       m *= p[i]], {j, Length[s]}], {i, w}]; s];
{0}~Join~Table[n - Length@ f[n], {n, 2, 120}]

Formula

a(n) = n - A381800(n).

a(n) > 0 for n > 2.

a(n) - phi(n) + 1 >= 0, where phi = A000010.

a(p) = p-2.

a(p^m) = n - m - 1.