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

%I

%S 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 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 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 Number of nonsquare divisors of n^2.

%C 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 Outline of a proof for this observation, _R. J. Mathar_, May 05 2013: (Start)

%C 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 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 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 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 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 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 (End)

%H T. D. Noe, <a href="/A055205/b055205.txt">Table of n, a(n) for n = 1..1000</a>

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

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

%F a(n) = A048691(n) - A000005(n). [_Reinhard Zumkeller_, Dec 08 2009]

%e n = 8, d(64) = 7 and from the 7 divisors {1,4,16,64} are square and the remaining 3 = a(8).

%e 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 a(60) = (number of terms of finite A171425) = 33. [_Reinhard Zumkeller_, Dec 08 2009]

%t Table[Count[Divisors[n^2], d_ /; ! IntegerQ[Sqrt[d]]], {n, 1, 95}] (* _Jean-Fran├žois Alcover_, Mar 22 2011 *)

%t Table[DivisorSigma[0,n^2]-DivisorSigma[0,n],{n,100}] (* _Harvey P. Dale_, Sep 02 2017 *)

%o (Haskell)

%o a055205 n = length [d | d <- [1..n^2], n^2 `mod` d == 0, a010052 d == 0]

%o -- _Reinhard Zumkeller_, Aug 15 2011

%o (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 Cf. A000005, A000290, A048691, A056595.

%K nice,nonn

%O 1,4

%A _Labos Elemer_, Jun 19 2000

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 00:18 EST 2019. Contains 320411 sequences. (Running on oeis4.)