cp's OEIS Frontend

A381804 Number of residues r mod n congruent to k such that rad(k) | n but rad(r) does not divide n, with rad = A007947.

%I A381804 #4 Mar 22 2025 19:06:02
%S A381804 0,0,0,0,0,0,0,0,0,1,0,0,0,0,3,0,0,2,0,1,4,6,0,0,0,8,0,1,0,1,0,0,3,3,
%T A381804 7,2,0,13,0,1,0,5,0,7,7,6,0,1,0,16,14,8,0,15,3,1,15,23,0,2,0,0,5,0,5,
%U A381804 10,0,3,9,15,0,2,0,30,20,14,10,10,0,3,0,14,0
%N A381804 Number of residues r mod n congruent to k such that rad(k) | n but rad(r) does not divide n, with rad = A007947.
%C A381804 a(n) is the number of r in row n of A381801 that are such that rad(r) does not divide n.
%C A381804 For prime p, a(p) = 0 since r < n are coprime to p and k such that rad(k) | p are powers of p with p^0 congruent to 1 (mod p) and p^m congruent to 0 (mod p) for m > 0.
%C A381804 For proper prime power p^m, m > 1, a(p^m) = 0 since k such that rad(k) | p are powers p^j, j > 1, such that p^j mod p^m = p^(j mod m), divisors d of p^m and thus rad(d) | p^m.
%F A381804 a(n) = A381800(n) - A010846(n).
%F A381804 a(n) <= A243623(n).
%F A381804 For prime power p^m, a(p^m) = 0.
%e A381804 Let S(n) = row n of A381801 and R(n) = row n of A162306, with n in R(n) instead written as n mod n = 0.
%e A381804 Define quality Q between natural numbers k and n to be rad(k) does not divide n.
%e A381804 a(10) = 1 since S(10) = {0,1,2,4,5,6,8} only contains r = 6 with quality Q.
%e A381804 a(15) = 3 since S(15) = {0,1,3,5,6,9,10,12} and R(15) = {0,1,3,5,9} = {6,10,12}.
%e A381804 a(18) = 2 since S(18) = {0,1,2,3,4,6,8,9,10,12,14,16} and R(18) = {1,2,3,4,6,8,9,12,16,18} = {10,14}.
%e A381804 a(20) = 1 since S(20) = {0,1,2,4,5,8,10,12,16} and R(20) = {0,1,2,4,5,8,10,16} = {12}, etc.
%t A381804 f[x_] := Block[{c, ff, m, r, p, s, w},
%t A381804   c[_] := True; ff = FactorInteger[x][[All, 1]]; w = Length[ff];
%t A381804   s = {1};
%t A381804   Do[Set[p[i], ff[[i]]], {i, w}];
%t A381804   Do[Set[s, Union@ Flatten@ Join[s, #[[-1, 1]]]] &@ Reap@
%t A381804     Do[m = s[[j]];
%t A381804       While[Sow@ Set[r, Mod[m*p[i], x]];
%t A381804         c[r],
%t A381804         c[r] = False;
%t A381804         m *= p[i]],
%t A381804        {j, Length[s]}],
%t A381804     {i, w}]; s ];
%t A381804 rad[x_] := Times @@ FactorInteger[x][[All, 1]];
%t A381804 {0}~Join~Table[Length@ Complement[f[n], {0}~Join~Select[Range[n - 1], Divisible[#, rad[#]] &]], {n, 2, 120}]
%Y A381804 Cf. A010846, A243623, A381800.
%K A381804 nonn
%O A381804 1,15
%A A381804 _Michael De Vlieger_, Mar 14 2025