|
|
A055205
|
|
Number of nonsquare divisors of n^2.
|
|
11
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
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)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = A000005(n^2)-A000005(n) because the number of square divisors of n^2 equals the number of divisors of n.
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
|
|
EXAMPLE
|
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
|
|
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 *)
|
|
PROG
|
(Haskell)
a055205 n = length [d | d <- [1..n^2], n^2 `mod` d == 0, a010052 d == 0]
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|