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

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, 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, 8, 5, 19, 1, 10, 1, 8, 6, 8, 4, 22, 1, 9, 1, 8, 1, 26, 4

Offset: 1

Author

Michael De Vlieger, Sep 20 2023

Keywords

• nonn

Examples

			Let r(n) = A010846(n).
a(1) = 0 since 1 | 1 but 1 = 1.
a(2) = 1 since 1 | 2 and 2 | 2 but 2 = 2.
a(p) = 1 since 1 | p but p = p for prime p.
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.
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.
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.
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).
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A007947, A008479, A010846.

Programs

Maple

rad:= proc(n) convert(numtheory:-factorset(n),`*`) end proc:
Rads:= map(rad, [$1..100]):
f:= proc(n) nops(select(k -> n mod Rads[k] = 0 and Rads[k] <> Rads[n], [$1..n-1])) end proc:
map(f, [$1..100]); # Robert Israel, Sep 20 2023

Mathematica

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}]

PARI

rad(n) = factorback(factorint(n)[, 1]); \\ A007947
a(n) = my(r=rad(n), rk); sum(k=1, n, rk=rad(k); (rk != r) && !(n % rk)); \\ Michel Marcus, Sep 20 2023

Formula

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

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