A381802 - OEIS

%I #7 Mar 22 2025 19:05:15

%S 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,

%T 27,11,29,26,24,23,23,20,35,17,33,28,39,18,41,28,30,32,45,32,46,22,31,

%U 35,51,23,47,44,36,27,57,32,59,54,50,57,55,34,65,55,54,35

%N 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.

%H Michael De Vlieger, <a href="/A381802/b381802.txt">Table of n, a(n) for n = 1..10000</a>

%H Michael De Vlieger, <a href="/A381802/a381802.png">Log log scatterplot of a(n)</a>, 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.

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

%F a(n) > 0 for n > 2.

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

%F a(p) = p-2.

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

%e a(n) = 0 for n = 1..2, since there do not exist any residues mod n that do not represent a power of n.

%e  n  a(n)  [0..n-1] \ row n of A381801.

%e ------------------------------------------------

%e  6    1   {5}

%e 10    3   {3,7,9}

%e 12    4   {5,7,10,11}

%e 14    8   {3,5,6,9,10,11,12,13}

%e 15    7   {2,4,7,8,11,13,14}

%e 18    6   {5,7,11,13,15,17}

%e 20   11   {3,6,7,9,11,13,14,15,17,18,19}

%e 21   12   {2,4,5,8,10,11,13,14,16,17,19,20}

%e 22    9   {3,5,7,9,13,15,17,19,21}

%e 24   13   {5,7,10,11,13,14,15,17,19,20,21,22,23}

%e 26   11   {3,5,7,9,11,15,17,19,21,23,25}

%e 28   19   {3,5,6,9,10,11,12,13,15,17,18,19,20,22,23,24,25,26,27}

%e 30   11   {7,11,13,14,17,19,22,23,26,28,29}

%t f[x_] := Block[{c, ff, m, r, p, s, w}, c[_] := True;

%t   ff = FactorInteger[x][[All, 1]]; w = Length[ff]; s = {1};

%t   Do[Set[p[i], ff[[i]]], {i, w}];

%t   Do[Set[s, Union@ Flatten@ Join[s, #[[-1, 1]] ] ] &@ Reap@

%t     Do[m = s[[j]];

%t       While[Sow@ Set[r, Mod[m*p[i], x]];

%t        c[r], c[r] = False;

%t        m *= p[i]], {j, Length[s]}], {i, w}]; s];

%t {0}~Join~Table[n - Length@ f[n], {n, 2, 120}]

%Y Cf. A000010, A381800, A381801.

%K nonn

%O 1,5

%A _Michael De Vlieger_, Mar 14 2025