login
Number of nonsquare divisors of n.
21

%I #25 Aug 18 2024 09:15:29

%S 0,1,1,1,1,3,1,2,1,3,1,4,1,3,3,2,1,4,1,4,3,3,1,6,1,3,2,4,1,7,1,3,3,3,

%T 3,5,1,3,3,6,1,7,1,4,4,3,1,7,1,4,3,4,1,6,3,6,3,3,1,10,1,3,4,3,3,7,1,4,

%U 3,7,1,8,1,3,4,4,3,7,1,7,2,3,1,10,3,3,3,6,1,10,3,4,3,3,3,9,1,4,4,5,1,7,1

%N Number of nonsquare divisors of n.

%C a(A000430(n))=1; a(A030078(n))=2; a(A030514(n))=2; a(A006881(n))=3; a(A050997(n))=3; a(A030516(n))=3; a(A054753(n))=4; a(A000290(n))=A055205(n). - _Reinhard Zumkeller_, Aug 15 2011

%H Reinhard Zumkeller, <a href="/A056595/b056595.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = A000005(n) - A046951(n) = tau(n) - tau(A000188(n)).

%F Sum_{k=1..n} a(k) ~ n*log(n) + (2*gamma - zeta(2) - 1)*n, where gamma is Euler's constant (A001620). - _Amiram Eldar_, Dec 01 2023

%e a(36)=5 because the set of divisors of 36 has tau(36)=nine elements, {1, 2, 3, 4, 6, 9, 12, 18, 36}, five of which, that is {2, 3, 6, 12, 18}, are not perfect squares.

%p A056595 := proc(n)

%p local a,d ;

%p a := 0 ;

%p for d in numtheory[divisors](n) do

%p if not issqr(d) then

%p a := a+1 ;

%p end if;

%p end do:

%p a;

%p end proc:

%p seq(A056595(n),n=1..40) ; # _R. J. Mathar_, Aug 18 2024

%t Table[Count[Divisors[n],_?(#!=Floor[Sqrt[#]]^2&)],{n,110}] (* _Harvey P. Dale_, Jul 10 2013 *)

%t a[1] = 0; a[n_] := Times @@ (1 + (e = Last /@ FactorInteger[n])) - Times @@ (1 + Floor[e/2]); Array[a, 100] (* _Amiram Eldar_, Jul 22 2019 *)

%o (Haskell)

%o a056595 n = length [d | d <- [1..n], mod n d == 0, a010052 d == 0]

%o -- _Reinhard Zumkeller_, Aug 15 2011

%o (PARI) a(n)=sumdiv(n,d,!issquare(d)) \\ _Charles R Greathouse IV_, Aug 28 2016

%Y Cf. A000005, A000188, A046951.

%Y See A194095 and A194096 for record values and where they occur.

%Y Cf. A001620, A013661.

%K nonn

%O 1,6

%A _Labos Elemer_, Jul 21 2000