compute the double square...... :(

Alan Mackenzie acm at muc.de
Sun Jan 9 09:54:53 EST 2011


aregee <rahul.nbg at gmail.com> wrote:

> Double Squares
> A double-square number is an integer X which can be expressed as the
> sum of two perfect squares. For example, 10 is a double-square because
> 10 = 32 + 12. Your task in this problem is, given X, determine the
> number of ways in which it can be written as the sum of two squares.
> For example, 10 can only be written as 32 + 12 (we don't count 12 + 32
> as being different). On the other hand, 25 can be written as 52 + 02
> or as 42 + 32.

There is interesting mathematics involved in "double squares".  Such
properties are intimately bound up with the factorisation of the number.

It can be shown that:
(i) a prime number of the form 4n + 1 is a double square in exactly one
    way.  So is 2.  E.g. 73 = 64 + 9, 2 = 1 + 1.

(ii) a prime number of the form 4n + 3 is not a double square.

(iii) The product of m distinct primes, each of the form 4n + 1, is a
double square in 2^(m-1) ways.  E.g. 5*13 = 65 = 64 + 1 = 49 + 16

(iv) If k = a^2 + b^2, l = c^2 + d^2, then:
    kl = (ac + bd)^2 + (ad - bc)^2
       = (ac - bd)^2 + (ad + bc)^2.

(v) if k is a prime of the form 4n + 1, then k^m is a double square in
    (m + 2) / 2 ways.  E.g. 5^4 = 625 = 625 + 0 = 576 + 49 = 400 + 225.

(vi) .... and so on.

It's all in the factorisation!

-- 
Alan Mackenzie (Nuremberg, Germany).




More information about the Python-list mailing list