login
a(n) = number of k <= n such that rad(k) | n but rad(k) != rad(n).
1

%I #13 Sep 21 2023 13:21:31

%S 0,1,1,1,1,4,1,1,1,5,1,6,1,5,4,1,1,7,1,6,4,6,1,7,1,6,1,6,1,17,1,1,5,7,

%T 4,9,1,7,5,8,1,18,1,7,6,7,1,9,1,8,5,7,1,9,4,8,5,7,1,24,1,7,6,1,4,21,1,

%U 8,5,19,1,10,1,8,6,8,4,22,1,9,1,8,1,26,4

%N a(n) = number of k <= n such that rad(k) | n but rad(k) != rad(n).

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

%F a(n) = card({k : 0 < k < n, rad(k) | n, rad(k) != rad(n)}).

%F a(n) = A010846(n) - A008479(n).

%e Let r(n) = A010846(n).

%e a(1) = 0 since 1 | 1 but 1 = 1.

%e a(2) = 1 since 1 | 2 and 2 | 2 but 2 = 2.

%e a(p) = 1 since 1 | p but p = p for prime p.

%e a(p^m) = 1 since 1 | p^m, m > 0, but rad(p^k) = p and p^k | p^m for k = 1..m, and it is clear that the only divisor d | p^m such that rad(d) != p is d = 1.

%e For squarefree m, a(m) = r(m)-1 since all k < m are such that rad(k) != rad(m), but rad(m) = m, thus m = m. Hence r(m)-1.

%e a(12) = 6 since both k=6 and k=12 are such that rad(k)=rad(12)=6; the number k in S = {1, 2, 3, 4, 8, 9} is such that rad(k) | 12 but rad(k) != rad(12) = 6, hence we have |S| = 6.

%e Generally, for numbers n neither squarefree nor prime powers, 1 < a(n) < r(n)-1, since rad(n) = k, k < n, and both k and n are such that rad(k) = rad(n).

%p rad:= proc(n) convert(numtheory:-factorset(n),`*`) end proc:

%p Rads:= map(rad, [$1..100]):

%p f:= proc(n) nops(select(k -> n mod Rads[k] = 0 and Rads[k] <> Rads[n], [$1..n-1])) end proc:

%p map(f, [$1..100]); # _Robert Israel_, Sep 20 2023

%t r[x_] := r[x] = Times @@ FactorInteger[x][[All, 1]]; Table[Function[s, Length[s] - LengthWhile[r[n]*s, # <= n &]]@ Select[Range[n], Divisible[r[n], r[#]] &], {n, 120}]

%o (PARI) rad(n) = factorback(factorint(n)[, 1]); \\ A007947

%o a(n) = my(r=rad(n), rk); sum(k=1, n, rk=rad(k); (rk != r) && !(n % rk)); \\ _Michel Marcus_, Sep 20 2023

%Y Cf. A000005, A007947, A008479, A010846.

%K nonn

%O 1,6

%A _Michael De Vlieger_, Sep 20 2023