A055205 Number of nonsquare divisors of n^2.

0, 1, 1, 2, 1, 5, 1, 3, 2, 5, 1, 9, 1, 5, 5, 4, 1, 9, 1, 9, 5, 5, 1, 13, 2, 5, 3, 9, 1, 19, 1, 5, 5, 5, 5, 16, 1, 5, 5, 13, 1, 19, 1, 9, 9, 5, 1, 17, 2, 9, 5, 9, 1, 13, 5, 13, 5, 5, 1, 33, 1, 5, 9, 6, 5, 19, 1, 9, 5, 19, 1, 23, 1, 5, 9, 9, 5, 19, 1, 17, 4, 5, 1, 33, 5, 5, 5, 13, 1, 33, 5, 9, 5, 5, 5

Offset: 1

Author

Labos Elemer, Jun 19 2000

Keywords

• nice
• nonn

Comments

Seems to be equal to the number of unordered pairs of coprime divisors of n. (Checked up to 2*10^14.) - Charles R Greathouse IV, May 03 2013

Outline of a proof for this observation, R. J. Mathar, May 05 2013: (Start)

i) To construct the divisors of n, write n=product_i p_i^e_i as the standard prime power decomposition, take any subset of the primes p_i (including the empty set representing the 1) and run with the associated list exponents from 0 up to their individual e_i.

To construct the *nonsquare* divisors of n, ensure that one or more of the associated exponents is/are odd. (The empty set is interpreted as 1^0 with even exponent.) To construct the nonsquare divisors of n^2, the principle remains the same, although the exponents may individually range from 0 up to 2*e_i.

The nonsquare divisor is therefore a nonempty product of prime powers (at least one) with odd exponents times a (potentially empty) product of prime powers (of different primes) with even exponents.

The nonsquare divisors of n^2 have exponents from 0 up to 2*e_i, but the subset of exponents in the "even/square" factor has e_i candidates (range 2, 4, .., 2*e_i) and in the "odd/nonsquare" factor also only e_i candidates (range 1,3,5,2*e_i-1).

ii) To construct the pairs of coprime divisors of n, take any two non-intersecting subsets of the set of p_i (possibly the empty subset which represents the factor 1), and let the exponents run from 1 up to their individual e_i in each of the two products.

iii) The bijection between the sets constructed in i) and ii) is given by mapping the two non-intersection prime sets onto each other, and observing that the numbers of compositions of exponents have the same orders in both cases.

(End)

Examples

			n = 8, d(64) = 7 and from the 7 divisors {1,4,16,64} are square and the remaining 3 = a(8).
n = 12, d(144) = 15, from which 6 divisors are squares {1,4,9,16,36,144} so a(12) = d(144)-d(12) = 9
a(60) = (number of terms of finite A171425) = 33. [_Reinhard Zumkeller_, Dec 08 2009]
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)

Crossrefs

Cf. A000005, A000290, A048691, A056595.

Cf. A001620, A013661, A082633, A201994, A306016.

Programs

Haskell

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

Mathematica

Table[Count[Divisors[n^2], d_ /;  ! IntegerQ[Sqrt[d]]], {n, 1, 95}] (* Jean-François Alcover, Mar 22 2011 *)
Table[DivisorSigma[0,n^2]-DivisorSigma[0,n],{n,100}] (* Harvey P. Dale, Sep 02 2017 *)

PARI

a(n)=my(f=factor(n)[,2]);prod(i=1,#f,2*f[i]+1)-prod(i=1,#f,f[i]+1) \\ Charles R Greathouse IV, May 02 2013

Formula

a(n) = A000005(n^2)-A000005(n) because the number of square divisors of n^2 equals the number of divisors of n.

a(n) = A056595(A000290(n)).

a(n) = A048691(n) - A000005(n). - Reinhard Zumkeller, Dec 08 2009

Sum_{k=1..n} a(k) ~ (n/zeta(2)) * (log(n)^2/2 + c_1 * log(n) + c_2), where c_1 = 3*gamma - 2*zeta'(2)/zeta(2) - zeta(2) - 1 = 0.226634..., c_2 = 3*gamma^2 - (2*gamma - 1)*zeta(2) - 3*gamma_1 + (1 - 3*gamma)*(2*zeta'(2)/zeta(2) + 1) + (2*zeta'(2)/zeta(2))^2 - 2*zeta''(2)/zeta(2) = -0.0529271..., gamma is Euler's constant (A001620), and gamma_1 is the first Stieltjes constant (A082633). - Amiram Eldar, Dec 01 2023