cp's OEIS Frontend

A055205 Number of nonsquare divisors of n^2.

%I A055205 #48 Dec 01 2023 05:21:46
%S A055205 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,
%T A055205 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,
%U A055205 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
%N A055205 Number of nonsquare divisors of n^2.
%C A055205 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
%C A055205 Outline of a proof for this observation, _R. J. Mathar_, May 05 2013: (Start)
%C A055205 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.
%C A055205 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.
%C A055205 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.
%C A055205 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).
%C A055205 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.
%C A055205 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.
%C A055205 (End)
%H A055205 Alois P. Heinz, <a href="/A055205/b055205.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%F A055205 a(n) = A000005(n^2)-A000005(n) because the number of square divisors of n^2 equals the number of divisors of n.
%F A055205 a(n) = A056595(A000290(n)).
%F A055205 a(n) = A048691(n) - A000005(n). - _Reinhard Zumkeller_, Dec 08 2009
%F A055205 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
%e A055205 n = 8, d(64) = 7 and from the 7 divisors {1,4,16,64} are square and the remaining 3 = a(8).
%e A055205 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
%e A055205 a(60) = (number of terms of finite A171425) = 33. [_Reinhard Zumkeller_, Dec 08 2009]
%t A055205 Table[Count[Divisors[n^2], d_ /;  ! IntegerQ[Sqrt[d]]], {n, 1, 95}] (* _Jean-François Alcover_, Mar 22 2011 *)
%t A055205 Table[DivisorSigma[0,n^2]-DivisorSigma[0,n],{n,100}] (* _Harvey P. Dale_, Sep 02 2017 *)
%o A055205 (Haskell)
%o A055205 a055205 n = length [d | d <- [1..n^2], n^2 `mod` d == 0, a010052 d == 0]
%o A055205 -- _Reinhard Zumkeller_, Aug 15 2011
%o A055205 (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
%Y A055205 Cf. A000005, A000290, A048691, A056595.
%Y A055205 Cf. A001620, A013661, A082633, A201994, A306016.
%K A055205 nice,nonn
%O A055205 1,4
%A A055205 _Labos Elemer_, Jun 19 2000