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.

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, 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, 10, 0, 3, 9, 15, 0, 2, 0, 30, 20, 14, 10, 10, 0, 3, 0, 14, 0

Offset: 1

Author

Michael De Vlieger, Mar 14 2025

Keywords

• nonn

Comments

a(n) is the number of r in row n of A381801 that are such that rad(r) does not divide n.

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.

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.

Examples

			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.
Define quality Q between natural numbers k and n to be rad(k) does not divide n.
a(10) = 1 since S(10) = {0,1,2,4,5,6,8} only contains r = 6 with quality Q.
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}.
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}.
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.
		

Crossrefs

Cf. A010846, A243623, A381800.

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 ];
rad[x_] := Times @@ FactorInteger[x][[All, 1]];
{0}~Join~Table[Length@ Complement[f[n], {0}~Join~Select[Range[n - 1], Divisible[#, rad[#]] &]], {n, 2, 120}]

Formula

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

a(n) <= A243623(n).

For prime power p^m, a(p^m) = 0.