Tag Archives: python

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 – IV

Standard

While discussing this problem with Dr. Shailesh Shirali, he commented that there has to be a way to phrase the problem in terms of a ray of light being reflected off the walls of the rectangle, bouncing around, proceeding from one corner to some other corner.

The problem in re-stating my problem in “light reflection” form was that reflections must be from center of squares and this is not the way light “actually” reflects from surfaces. But, I clubbed that idea with “graph theory” (directed graphs), which actually answers the first question I asked in my previous post:

Why no filled square has more than 2 crosses?

As per my “Cross diagonal cover algorithm” we can’t retrace a path and each square has just two diagonals. Hence, if we replace all the squares by their centers then each center is of degree two (i.e. can allow intersection of at most two distinct paths). Hence proving that no filled square can have more than 2 crosses. For example:

New Doc 22_1

Now moving to the bigger question of counting the total number of filled squares, there hasn’t been much progress yet (even on arriving at a concrete conjecture). But, Prof. Amritanshu Prasad wrote a SageMath  program for my algorithm which enables us to find number of the filled squares for individual cases without actually drawing them! For Example: for m=101 , n=102 grid, there will be 5151 = (101 * 102 )/ 2 filled squares. Pretty cool 🙂

SageMath is is an open source implementation of mathematics and scientific software based on Python 2.  Unfortunately, since the SageMath program is essentially a Python script I am not allowed to embed  it in my WordPress.com blog. But, motivated by my discussions with Ms. Marina Ibrishimova, I tweaked Prof. Prasad’s original source-code and added comments (initialized by #) to make it self explanatory.

Here is the SageMath (or Python) code to count the number of filled squares for 2 \leq m\leq n\leq 10

#-----START OF PYTHON FUNCTION FOR CROSS DIAGONAL COVER ALGORITHM-----

def cover(m,n):
#a function to count the number of squares covered in a grid with m rows
#and n columns
    xinc = 1
#we will use this variable to increment (or decrement) the value of
#x-coordinate (row position) by 1 unit after each step
    yinc = 1
#we will use this variable to increment (or decrement) the value of
#y-coordinate (column position) by 1 unit after each step
    pos = [1, 1]
#we are assuming our grid to have at least 2 rows and 2 columns
#and will initialize counting from (1,1) position.
    visited = [[0, 0], [1, 1]]
#since we start from (1,1) position, we implicitly assume to have
#counted (0,0) position.
    while pos != [m-1, 0] and pos != [0, n-1] and pos != [m - 1, n - 1]:
#whenever we reach any corner the algorithm terminates, so need to include
#position of other three corners apart from starting corner in condition.
          if pos[0] in [0, m-1]:
#evaluates to true if x-coordinate of current position is a
#member of the collection [0,m-1]
             xinc = - xinc
#if x-coordinate is either 0 or m-1 then we will switch diagonal
#by switching the sign of xinc
          if pos[1] in [0, n-1]:
#evaluates to true if y-coordinate of current position is a member
#of the collection [0,n-1]
             yinc = -yinc
#if y-coordinate is either 0 or n-1 then we will switch diagonal
#by switching the sign of yinc
          pos[0] += xinc
#update the x-coordinate of new position as x(new) = x(old) + xinc,
# where xinc = 1 or -1.
          pos[1] += yinc
#update the y-coordinate of new position as y(new) = y(old) + yinc,
# where yinc = 1 or -1.
          if not (pos in visited):
#if this new state is not there in visited positions list
             visited.append([pos[0], pos[1]])
#then add this new position to the list of visited positions.
    return visited 

#---------------END OF FUNCTION---------------

#we will write a small code to be able to use above function to find number of
#filled squares for all grids where m,n lie between 1 and 11 (both excluded).

for i in range (2, 11):
#The range() function provides an easy way to construct a list of integers.
#The range() function only does numbers from the first to the last,
#not including the last.
    for j in range(i, 11):
        print i, j, len(cover(i, j))
# len(indata) counts the bytes of data in indata here it
#counts the number of elements is visited list.

To run the above code, please copy-paste it in SageMathCell and click evaluate button. You will get the list displaying m, n and the number of filled squares in each of the grid (with 1<m,n<11).

In case you want to understand above Python function, here is an illustration when m=3 and n=4:

New Doc 23_1

Note that though (1,1) position is encountered twice but it is added to “visited squares” list only once.

So far I haven’t been able to derive a useful interpretation even after getting access to lot of data. I hope to formulate a conjecture soon…