Tag Archives: algorithm

Different representations of a number as sum of squares

Standard

A couple of weeks ago, I wrote a post on Ramanujam’s 129th birthday. In that post I couldn’t verify the fact that:

129 is the smallest number that can be written as the sum of 3 squares in 4 ways.

So I contacted Sannidhya, the only good programmer I know . He wrote a program in Python which finds all numbers less than 1000 that can be written as sum of three squares. Here is the program :  https://repl.it/EzIc

Now, we can conclude that 129 is the smallest such number and the next is 134.

Let’s try to understand, how this program works. Firstly, the sumOfSquares(n) procedure finds all a, b such that n = a^2 + b^2. Then the sumOfSquares3(n) procedure finds all a,b,c such that n = a^2 + b^2 + c^2. It works by repeatedly invoking sumOfSquares on (n-i^2) where i is incremented after each iteration from 1 to square root of n/3. Finally, we run a loop up to 1000 and find those number for which sumOfSquares3 returns 4 triplets (a,b,c). Similarly, one can also find numbers which can be expressed as sum of 3 squares in 5 different ways. The smallest one is 194, with the 5 triplets being (1, 7, 12), (3, 4, 13), (3, 8, 11), (5, 5, 12) and (7, 8, 9).
But how does the functions sumOfSquares(n) and sumOfSquares3(n) work? This is how Sannidhya explains:

 The SumOfSquares(n) finds all the unordered pairs (a, b), such that a^2 + b^2 = n. It works by subtracting a perfect square (i^2) from n, and checking if the remaining part is a perfect square as well. If so, then (i, sqrt(n-i^2)) will form a required unordered pair. Here, i loops from 1 to square root of n/2. Note: One can also loop from 1 to square root of n but after square root of n/2, further iterations will generate redundant pairs which are just permutations of the pairs already obtained. For example, consider 25, the expected output should be (3,4) only, but if the loop runs from 1 to square root of n, then the output will be (3, 4), (4, 3). As you can see we are getting redundant pairs. So, we run the loop from 1 to square root of n/2.

The SumOfSquares3 function calls SumOfSquares repeatedly with the argument n – i^2, where i is incremented from 1 to square root of n/3. Note that each element of SumOfSquares(n – i^2) is a pair. For each of these elements, the loop forms a triplet consisting of i and the pair. This triplet is then appended to the list, which is finally returned.

The repetitions of triplets can easily be controlled by using sorted function from Python in sumOfSquares3(n).

Indeed, these type of question are a bit hard computationally. For example, see:

Related discussions on MathOverflow:

– Is there a simple way to compute the number of ways to write a positive integer as the sum of three squares? : Note that this is not answer of my question since r_k(n) counts the number of representations of n by k squares, allowing zeros and distinguishing signs and order.

– Efficient computation of integer representation as sum of three squares

Related discussions on ComputerScience.SE

– Listing integers as the sum of three squares m=x^2+y^2+z^2 : Sannidhya did a clever improvement to this algorithm, but still as pointed here, Sannidhya’s algorithm is of O(n).

Related discussions on Mathematics.SE

– When is a rational number a sum of three squares?

– Why can’t this number be written as a sum of three squares of rationals?

– Sum of one, two, and three squares

Advertisements

Cross Diagonal Cover – I

Standard

While doodling in my college classes, I designed an algorithm which I called Cross Diagonal Cover Algorithm:

I have a m\times n rectangle divided into unit squares. I start by placing a x (cross) in leftmost corner. Every time I visit a square in diagonal direction I place a  x in the squares till I reach any boundary of rectangle, from where I switch to adjacent diagonal.

New Doc 17_1

Illustrating the algorithm… Follow the arrow numbers to fill the grid.

Please note that it doesn’t matter that how many x (cross) are there in each square. The number of x (cross) in each square just signify number of times I visited that square while executing the algorithm.

Then I asked myself the following question:

Can I cover whole grid with at least one x in each unit square?

The answer to my above question is NO! The proof is pretty easy.

If m=n then it’s trivial that I can’t cover the whole grid with x since I will  be tracing the main diagonal again and again.

Moreover, the key observation here is that I will be stuck in loop (which can’t cover whole grid) whenever I reach another corner of the grid since it supports only one diagonal. Since I want to cover whole grid I must visit all the corners but they are dead ends!

Quod Erat Demonstrandum.

Any references about this idea from literature would be appreciated. I am working on a better question on “Cross Diagonal Cover Algorithm”, which I will discuss in next post.