A problem from 600 CE and some curiosities of Āryabhaṭa’s kuṭṭaka algorithm

Around 600 CE in the examinations of one of the Hindu schools of mathematics and astronomy one might have encountered a problem such as below (given by Bhāskara-I in his commentary on Āryabhaṭa’s Āryabhaṭīya):

dvayādyaiḥ ṣaṭ-paryantair ekāgraḥ yo ‘vaśiṣyate rāśiḥ |
saptabhir eva sa śuddho vada śīghraṃ ko bhaved gaṇaka ||

Quickly say, O mathematician, which number when divided by the numbers starting with 2 and ending in 6 (i.e 2:6) leaves 1 as the remainder, and is exactly divisible by 7?

This problem was given to illustrate the use of the kuṭṭaka algorithm first provided by Āryabhaṭa. Before we actually solve the above problem we will briefly examine the kuṭṭaka. The kuṭṭaka is a general algorithm deployed to obtain integer solutions for the indeterminate linear equations of the form , where are positive integers. Thus, it is essentially the problem of finding the coordinates of the the integer lattice point through which the line passes. Of the three constants in the equation, and are given; is not given but we have to find the smallest for which the equation can be solved in integers. From that we can build other valid For computational simplicity (with no loss of generality) we take to be the bigger number and to be the smaller number. The below presentation of it follows the matrix representation of Āryabhaṭa’s operation given by the mathematician Avinash Sathye:

Let us consider as an example the following equation . From and we can generate the below matrix which is the result of the kuṭṭaka procedure. We have written a function ‘kuṭṭaka’ in the R language that computes this matrix and few other details given .

The process is initiated with column . Write and . Kuṭṭaka in Sanskrit means ‘to powder’, common translated as ‘pulverizer’. We start ‘pulverizing’ with , which means finding the . Then . We iterate this procedure until we get ; that completes the column . We call as the number of iterations for convergence. Thus, the matrix will have rows and 4 columns. The quotient of the division of is written as , that of as , so on till convergence. Thus, the cells and will always be empty (NA in the R language).

Then we fill in and . There after we compute the remaining elements of this column working upwards from with the formula:

We then fill in and and complete the column starting upwards with the formula:

With that we have our kuṭṭaka matrix and all the needfull stuff to solve the said indeterminate equation:
1) The greatest common divisor . This is also the smallest positive for which our indeterminate equation has integer solutions.
2) The least common multiple
3) The integer lattice points through which the line passes are obtained from by assigning the appropriate signs. Thus, for the above equation we have the solution . Thus, will pass through the integer lattice at the point
4) If we enforce the need for positive solutions then we can use to obtain the minimal integer solution: . Thus, will pass through the integer lattice at the point in the first quadrant.
5) We can write the following relationship, which helps us to more generally get the lattice points through which the line passes even if the values of and are interchanged or for other than the minimal :

Thus, if we set , we get as further lattice points through which the line passes.

Now we can tackle the original problem: Since it says that 7 divides the number perfectly it can be written as where will the y-coordinate of the lattice point. The numbers 2, 3, 4, 5, 6 leave a remainder of 1. Of them 4 is divisible by 2, and 6 by both 2 and 3. So all we need to consider are the numbers 4, 5, 6. Using the above kuṭṭaka or any other means we can show that and . Thus, we can write , where will the coordinate of the integer lattice. Using kuṭṭaka on the equation we get the matrix:

From this we can compose . Thus, our number is , which is divisible by 7 but leaves a remainder of 1 for all integers from 2:6. More generally, if we say that then we can use to compose the negative solutions or . Such triplets of solutions correspond to symmetric lattice points along the line.

In the final part of this note we shall consider the following operation: Take a number and perform the kuṭṭaka operation with it (i.e. ) and all integers lesser than or equal to it (i.e. ). Then we count the number of iterations it takes with each of these integers to reach convergence. From above it is clear that the minimum number of iterations for convergence will always be 3. We term the result the kuṭṭaka spectrum of a number and plot this spectrum for the numbers 120, 123, 127 and 128.

Figure 1

The kuṭṭaka spectrum displays several notable features:
1) It is pseudo-symmetric about the mid-point, i.e. either side of is an approximate mirror image of the other side but they differ in “height” by one iteration.

2) The number of times the kuṭṭaka spectrum hits a minimum (i.e. converges in 3 iterations) is equal to the number of divisors of , . Thus, for a highly composite number, as defined by Ramanujan, we get the record number of minima in the kuṭṭaka spectrum for any number less than it. Thus, in our example the highly composite number has 16 minima with the first six integers 1:6 giving a run of 6 successive minima. A minimally composite number like in our figure we get 4 minima, namely 1 and the number itself and its two prime factors. The prime number in our figure, , as expected has only 2 minima.

3) The more composite a number the lower its mean value of iterations (red line in Figure 1) than other integers in its immediate neighborhood. Thus, the highly composite number 120 has the lowest mean value in our set. In contrast, the primes have higher mean values than the integers in their immediate neighborhood. This is can be seen with in Figure 1.

4) A curious feature of the spectrum are the maxima, i.e. the value of for which the maximum number of iterations are required for pulverizing to convergence. For example the spectrum of shows 2 maxima: pulverizes it via the pathway: 128, 79, 49, 30, 19, 11, 8, 3, 2, 1, 0. The other one via 128, 81, 47, 34, 13, 8, 5, 3, 2, 1, 0. One immediately notices that the convergence in each of these two cases enters the Golden ratio convergent sequence. This feature can be investigated further by examining the distribution of the values of for those which result in maxima in the kuṭṭaka spectrum for a given . In order to have have clear discrimination of these fractional values of corresponding to the spectral maxima we chose a set of relatively large , namely all integers from 500 to 1000. We then determined the kuṭṭaka spectrum for each of those numbers and extracted the maxima for each and plotted a distribution of the values (Figure 2).

Figure 2.

First, the maxima always occur in second half of the spectrum (Figure 2), i.e. . This makes sense because smaller would reach close to in the first division itself and could pulverize it to a relative small number. However, would fit only once in and could leave a relatively large remainder that could need more steps for pulverizing. Second, strikingly, the dominant peak in this distribution is the Golden ratio (Figure 2), suggesting the maxima tend to occur where . Indeed in our above example . This can be intuitively understood as the which generates a maximum may be seen as a Golden cut of : if is too big then the remainder generated will be small and might be pulverized quickly. If is too small then it will leave a big remainder relative to which might be quickly pulverized in the next step. Thus, the could give you the cut that is just right. The next dominant peak is at . This is similar to in its operation. These two are marked by a red dashed line in Figure 2.

There are further peaks in the distribution corresponding to other fractions on either side of following a certain pattern of declining heights. Further they show the same symmetry as and , with each peak having a counterpart . We have thus far not been able to determine a more
general expression describing all these peaks or prove why they should be peaks but we were able to account for a subset of them as corresponding to other quadratic irrational numbers (marked by grey dashed lines in Figure 2). These include:

Of these the pair , especially the former is not the best fit to the peak but given the breadth of that peak it is possible that more than one attractor fraction is merged in that peak. It would be a good mathematical quest to discover the general expression for the peaks, their dominance and prove why they tend to be peaks. There might be a subtle fractal structure to them that might become apparent at large values of .