cp's OEIS Frontend

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.

%I A381802 #7 Mar 22 2025 19:05:15
%S A381802 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 A381802 27,11,29,26,24,23,23,20,35,17,33,28,39,18,41,28,30,32,45,32,46,22,31,
%U A381802 35,51,23,47,44,36,27,57,32,59,54,50,57,55,34,65,55,54,35
%N 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.
%H A381802 Michael De Vlieger, <a href="/A381802/b381802.txt">Table of n, a(n) for n = 1..10000</a>
%H A381802 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 A381802 a(n) = n - A381800(n).
%F A381802 a(n) > 0 for n > 2.
%F A381802 a(n) - phi(n) + 1 >= 0, where phi = A000010.
%F A381802 a(p) = p-2.
%F A381802 a(p^m) = n - m - 1.
%e A381802 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 A381802  n  a(n)  [0..n-1] \ row n of A381801.
%e A381802 ------------------------------------------------
%e A381802  6    1   {5}
%e A381802 10    3   {3,7,9}
%e A381802 12    4   {5,7,10,11}
%e A381802 14    8   {3,5,6,9,10,11,12,13}
%e A381802 15    7   {2,4,7,8,11,13,14}
%e A381802 18    6   {5,7,11,13,15,17}
%e A381802 20   11   {3,6,7,9,11,13,14,15,17,18,19}
%e A381802 21   12   {2,4,5,8,10,11,13,14,16,17,19,20}
%e A381802 22    9   {3,5,7,9,13,15,17,19,21}
%e A381802 24   13   {5,7,10,11,13,14,15,17,19,20,21,22,23}
%e A381802 26   11   {3,5,7,9,11,15,17,19,21,23,25}
%e A381802 28   19   {3,5,6,9,10,11,12,13,15,17,18,19,20,22,23,24,25,26,27}
%e A381802 30   11   {7,11,13,14,17,19,22,23,26,28,29}
%t A381802 f[x_] := Block[{c, ff, m, r, p, s, w}, c[_] := True;
%t A381802   ff = FactorInteger[x][[All, 1]]; w = Length[ff]; s = {1};
%t A381802   Do[Set[p[i], ff[[i]]], {i, w}];
%t A381802   Do[Set[s, Union@ Flatten@ Join[s, #[[-1, 1]] ] ] &@ Reap@
%t A381802     Do[m = s[[j]];
%t A381802       While[Sow@ Set[r, Mod[m*p[i], x]];
%t A381802        c[r], c[r] = False;
%t A381802        m *= p[i]], {j, Length[s]}], {i, w}]; s];
%t A381802 {0}~Join~Table[n - Length@ f[n], {n, 2, 120}]
%Y A381802 Cf. A000010, A381800, A381801.
%K A381802 nonn
%O A381802 1,5
%A A381802 _Michael De Vlieger_, Mar 14 2025