login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

T. D. Noe, Table of n, a(n) for n = 1..1000

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]

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

a(60) = (number of terms of finite A171425) = 33. [Reinhard Zumkeller, Dec 08 2009]

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]

-- Reinhard Zumkeller, Aug 15 2011

(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

Cf. A000005, A000290, A048691, A056595.

Sequence in context: A047818 A055972 A079168 * A161686 A289621 A069626

Adjacent sequences:  A055202 A055203 A055204 * A055206 A055207 A055208

KEYWORD

nice,nonn

AUTHOR

Labos Elemer, Jun 19 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 19 14:54 EST 2018. Contains 299334 sequences. (Running on oeis4.)