aregee <rahul....@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).
--
http://mail.python.org/mailman/listinfo/python-list
