A363924 - OEIS

%I #36 Aug 16 2024 06:05:40

%S 1,2,2,2,5,2,6,2,2,6,5,2,2,5,7,2,7,2,18,2,6,8,5,2,8,6,2,19,2,8,2,6,2,

%T 5,6,8,2,2,8,5,22,2,6,20,2,2,9,5,23,2,9,2,5,9,7,2,5,7,9,5,2,2,25,2,16,

%U 9,2,2,21,7,2,26,5,9,5,9,7,2,7,23,2,5,10,2

%N a(n) = number of k <= m such that rad(k) | m, where m = A005117(n) and rad(n) = A007947(n).

%C Let S_m be the sequence { k : rad(k) | rad(m) }. This sequence gives the number of k <= rad(m), which is the same as k <= m, since m is squarefree. Seen another way, this sequence gives the position of m in S_m.

%C Number of k <= p^e, e >= 0, such that rad(k) | p is (e+1). This is given by {A025477} + 1.

%C Number of k <= m for numbers k neither squarefree nor prime powers (k in A126706) is given by A365790(n) = A010846(A126706(n)).

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

%F a(n) = A010846(A005117(n)).

%F Let b(n) = A005117(n).

%F For prime b(n) = p, a(n) = 2 since terms k in S_p such that k <= p are {1, p}.

%F For composite b(n) = m, a(n) > 2, since p | m appear in S_p, and p < m.

%e Let b(n) = A005117(n).

%e a(1) = 1 since 1 is the only number k <= b(1) such that rad(k) | 1.

%e a(2) = 2 since k in {1, 2} are such that rad(k) | 2.

%e a(5) = 5 since b(5) = 6, k in {1, 2, 3, 4, 6} are such that rad(k) | 6. That is, 6 appears in the 5th position in S_6 = A003586.

%e a(7) = 6 since b(7) = 10, Card({ k : k <= 10, rad(k) | 10 }) = Card({1, 2, 4, 5, 8, 10}) = 6. That is, 10 appears in the 6th position in S_10 = A003592, etc.

%t rad[x_] := Times @@ FactorInteger[x][[All, 1]]; Map[Function[{m, r}, Count[Range[m], _?(Divisible[r, rad[#] ] &)]] @@ {#, rad[#]} &, Select[Range[2^10], SquareFreeQ]]

%o (Python)

%o from math import gcd, isqrt

%o from sympy import mobius

%o def A363924(n):

%o     def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))

%o     m, k = n, f(n)

%o     while m != k:

%o         m, k = k, f(k)

%o     return int(sum(mobius(k)*(m//k) for k in range(1,m+1) if gcd(m,k)==1)) # _Chai Wah Wu_, Aug 15 2024

%Y Cf. A003586, A003592, A005117, A007947, A010846, A025477, A126706, A365790.

%K nonn

%O 1,2

%A _Michael De Vlieger_, Oct 24 2023