login
Number of numbers less than n whose square does not divide n.
7

%I #25 Jun 30 2021 09:04:48

%S 0,0,1,1,3,4,5,5,6,8,9,9,11,12,13,12,15,15,17,17,19,20,21,21,22,24,24,

%T 25,27,28,29,28,31,32,33,31,35,36,37,37,39,40,41,41,42,44,45,44,46,47,

%U 49,49,51,51,53,53,55,56,57,57,59,60,60,59,63,64,65,65,67,68,69,67

%N Number of numbers less than n whose square does not divide n.

%H Felix Fröhlich, <a href="/A338233/b338233.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = n - 1 - Sum_{k=1..n-1} (1 - ceiling(n/k^2) + floor(n/k^2)).

%F For n > 1, a(n) = n - 1 - tau(sqrt(n/A007913(n)) = n - A000005(sqrt(n/A007913(n)). - _Chai Wah Wu_, Feb 01 2021

%e a(7) = 5; 1^2|7, but the squares of 2,3,4,5 and 6 do not. So a(7) = 5.

%e a(8) = 5; 1^2|8 and 2^2|8, but the squares of 3,4,5,6,and 7 do not. So a(8) = 5.

%t Table[Sum[Ceiling[n/k^2] - Floor[n/k^2], {k, n - 1}], {n, 100}]

%o (PARI) a(n) = sum(k=1, n-1, if (n % k^2, 1)); \\ _Michel Marcus_, Jan 31 2021

%o (Python)

%o def A338233(n):

%o return 0 if n <= 1 else n-1-divisor_count(integer_nthroot(n//core(n,2),2)[0]) # _Chai Wah Wu_, Feb 01 2021

%Y Cf. A338228, A338231, A338234, A338236, A338430, A338434.

%K nonn,easy

%O 1,5

%A _Wesley Ivan Hurt_, Jan 30 2021