A056595 Number of nonsquare divisors of n.

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, 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, 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

Offset: 1

Author

Labos Elemer, Jul 21 2000

Keywords

• nonn

Comments

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

Examples

			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.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A000188, A046951.

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

Cf. A001620, A013661.

Programs

Haskell

a056595 n = length [d | d <- [1..n], mod n d == 0, a010052 d == 0]
-- Reinhard Zumkeller, Aug 15 2011

Maple

A056595 := proc(n)
    local a,d ;
    a := 0 ;
    for d in numtheory[divisors](n) do
        if not issqr(d) then
            a := a+1 ;
        end if;
    end do:
    a;
end proc:
seq(A056595(n),n=1..40) ; # R. J. Mathar, Aug 18 2024

Mathematica

Table[Count[Divisors[n],?(#!=Floor[Sqrt[#]]^2&)],{n,110}] (* _Harvey P. Dale, Jul 10 2013 *)
a[1] = 0; a[n_] := Times @@ (1 + (e = Last /@ FactorInteger[n])) - Times @@ (1 + Floor[e/2]); Array[a, 100] (* Amiram Eldar, Jul 22 2019 *)

PARI

a(n)=sumdiv(n,d,!issquare(d)) \\ Charles R Greathouse IV, Aug 28 2016

Formula

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

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