Hofstadter and Nārāyaṇa: connections across space and time

The scientist-philosopher Douglas Hofstadter presents an interesting single-seeded sequence H in his book ‘Gödel, Escher, Bach: An Eternal Golden Braid’. It is generated by the recurrence relation,

where …(1)

Working it out one can see that it takes the form: 0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, 14, 15, 16, 17, 17…

If we connect in (1) then we get a tree structure which simulates a specific pattern of succession and duplication (Figure 1).

Figure 1

As we mentioned before, we only got to read Hofstadter’s book briefly when we first came across it. Hence, we did not have the chance to take in all that was discussed in it. However, it seeded our own explorations along the lines he has proposed in the book. Thus, in that period we discovered for ourselves a two-seeded sequence generated by the recurrence relation,

, where …(2)

This, while similar in from to the above recurrence relation, produces a different sequence: 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 14, 14, 14, 15, 16, 17, 18, 18, 18…

Our sequence (2) is related to Hofstadter’s H sequence in that adjacent duplications in his H are replaced by one singleton and a triplication in ours.

As we have described before, a convenient method for visualizing sequences such as this is to ‘rectify’ them: They increase linearly with a constant slope . Hence, we find that slope and use to render the sequence along the x-axis. For many common sequences works. However, during our experimentation with the sequence (2) (illustrated in Figure 11 in the previous article) it was obvious that . Hence, we took the arithmetic mean of for large and obtained , which served as the required rectification factor. Notably, the same value of applied for the H-sequence and we could accordingly rectify it (Figure 2)

Figure 2

Similarly, during our explorations of two other two-seeded sequences (See previous article) we discovered that their rectification factor , where is the Golden Ratio:

, where …(3)
, where …(4)

Since, (3) in particular resembles H and our above sequence (2) we wondered if we could similarly get a precise expression for their shared . We noted that in the case of the doubly nested recurrence relation (3) its rectification factor was the first root of the quadratic . For the triply nested recurrence relation (4) we noted that its rectification factor was the root of the cubic . Thus, we realized that a connection exists between the rectification factors and algebraic numbers. Armed with this knowledge searched the roots of cubic polynomials to get the rectification factors for H and our sequence (2). The real root of , yielded their required rectification factor. In the case of (3) and (4) the rectification factor is the reciprocal of the Golden Ratio, which is the convergent of the famous Meru sequence (known in the west as Fibonacci),

Thus, the rectification factors of the linearly growing two-seeded sequences (3) and (4) were reciprocals of the convergent of a non-linear sequence M. Notably the terms of M appear at each level of the tree of these linear sequences (3) and (4); see Figures 2 and 14 in the previous article. So question arose as to what is the corresponding non-linear sequence to which the rectification factor of H and (2) is similarly reciprocally related? The answer to this remarkably leads us to the original cow sequence of the great medieval Hindu mathematician Nārāyaṇa, son of Narasiṃha.

In his Gaṇita-kaumudi, Nārāyaṇa presents one of the earliest studies to identify a discrete formula for the ideal population dynamics of an organism which continually reproduces upon reaching a certain age. He poses the following problem:
prativarṣaṃ gauḥ sūte varṣa-tritayena tarṇakī tasyāḥ |
vidvan viṃśati-varṣaiḥ gor ekasyāś ca santatiṃ kathaya ||
Every year a cow gives birth, from its 3rd year, [and so also] her calves.
O scholar, tell, in 20 years [of reproduction] what will be the clan size from one cow?

He then provides the answer as the following sum of a series:
abdās tarṇy abd[a+ū]onāḥ pṛthak pṛthak yāvad alpatāṃ yānti |
tāni kramaś c[a+e]aikādika-vārāṇāṃ padāni syuḥ ||
Subtract the number of years (when a calf begins giving birth) successively and separately from the number of years till the remainder becomes less than the subtractive. Those are numbers for repeated addition once etc in order. The sum of the summations along with 1 added to the number of years [is the desired number]. Translation as per Ramasubramanian and Sriram’s interpretation.

Let the sequence dh[n], for dhenu (cow), represent the number of cows in the nth year. While Nārāyaṇa gives the direct formula for the nth term, it can be expressed in modern terms rather simply by the below recurrence relation for a triply seeded sequence,

, where … (5)

This sequence goes as, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641… Thus, the answer for Nārāyaṇa’s problem with 20 reproductive years is .

We note that, just a for the Meru sequence, this sequence too has a convergent which we will call Nārāyaṇa’s convergent ,

Investigating this value, we found it to be the only real root of the cubic equation , i.e. . This result yields the relationship between the rectification factor for the Hofstadter H sequence and our sequence (2) on one hand and the cow sequence of Nārāyaṇa on the other: . Thus, the same reciprocal relationship, which we saw between the Golden ratio, the convergent of the nonlinear Meru sequence, and the rectification factors of the linear sequences (3) and (4), is obtained for , the convergent of the dhenu sequence (5), and the linear sequences H and (2).

Since the Hofstadter H sequence includes all Natural Numbers we ask if there is any pattern to the occurrence of the dhenu numbers in it. This relation turns out to be,

The same relation also holds for our sequence (2) except that alternately the values are either or . A further interesting observation emerges as we examine these sequences more closely. The sequence (3) with rectification factor has a fixed bandwidth oscillation (see figure 5 in previous article). The H sequence and sequence (2) have a similar type of fixed bandwidth oscillation. Consistent with this, their recurrence relation and that of sequence (3) resemble each other with one of the terms being directly itself. In contrast, sequence (4), which also has the rectification factor , shows increasingly larger loops of the size of the Meru numbers and a fractal structure. Hence, we asked if there is a similar fractal sequence with same as H and sequence (2). Given that in the recurrence relation (4) the two terms recursively call the sequence with one having a subtraction, , we looked for similar sequences and found that the sequence discovered by Mallows has a comparable structure,

, where …(6)

Duly, we found that serves as a rectification factor for it (Figure 3) consistent with what we had experimentally determined for the sequence.

Figure 3

and , unlike , are not constructible by standard compass and straight-edge construction. Rather, they need a construction of the type used for the Delian altar of Apollo, i.e. doubling the cube. It goes thus (Figure 4):

1) Draw a parabola with focus at and directrix as . This parabola has equation .
2) Draw a rectangular hyperbola with the x- and y-axes as its asymptotes and and as its vertices. This hyperbola has the equation .
3) The point of intersection of the two conics, X, gives our desired constants: .
4) Using this and the two conics we can construct a rectangle comparable to the Golden rectangle.
5) Dissecting it using the square of side 1 allows us to construct two further rectangles: . Together these furnish the various powers of as shown in Figure 4.

Figure 4

This finally leads to the question of whether this observation regarding the algebraic number emerging as a convergent of a Nārāyaṇa-type series and it reciprocal as the rectification factor of a Hofstadter-like sequence is a more general one. In course of our explorations of Hofstadter-like sequences we discovered a fractal sequence that we termed the seahorse sequence (Figure 12 in the previous article). This is given by the recurrence relation,

…(7)

For this sequence we experimentally established a rectification factor . Using the above-described principle we then identified its proper form as the real root of the cubic equation . Thus, . Then we asked if there was a corresponding Nārāyaṇa-like sequence whose convergent is the reciprocal of . Our search yielded the following triply seeded Nārāyaṇa-like sequence provided by the recurrence relation:

, where …(8)

It goes as 1, 1, 1, 3, 7, 15, 33, 73, 161, 355, 783, 1727, 3809, 8401, 18529, 40867, 90135, 198799, 438465, 967065, 2132929, 4704323… We found its convergent,

This allowed us to establish it as the real root of , thus . Here again for sequence (7) we get . In addition to these examples there is the trivial case of sequences shown in the previous article where the rectification factor is . Its reciprocal corresponds to the trivial duplication sequence: 1, 2, 4, 8, 16, 32… Together these four show us that the form of the polynomial equations for the convergent and its reciprocal are also notable in their parity:

This leads to a conjecture: The reciprocal of an algebraic number which is the convergent of a non-linear Nārāyaṇa (Meru/dhenu)-like sequence serves as a rectification factor for a Hofstadter-like sequence. We have not attempted to prove this formally but the mathematically minded might be interested in doing so.

As we saw above, for and their reciprocals are the rectification factors for two types of Hofstadter-like sequences, namely one with a fixed bandwidth oscillation and another with fractal loops of increasing size. In the case of its reciprocal rectifies the seahorse sequence (7) which is a fractal sequence. We have not thus far found a fixed bandwidth sequence rectified by . If such a sequence exists then more generally we might speculate that for each rectification factor there are both fixed bandwidth and fractal sequences.

In conclusion, we find a remarkable link (to us) between the medieval mathematics of Nārāyaṇa and the modern mathematics of Douglas Hofstadter. This yields some interesting results some of which to our knowledge remains unexplored and unproven in terms of formal proofs. Notably, unlike the Golden ratio which appears in many places in mathematics and even in nature, we have not found equivalent occurrences for and their reciprocals. It almost appears as if nature has a predilection for things constructible by compass and straight-edge. However, we may note in passing that while writing this article we saw a recent paper proving a theorem that a number which is related to our , precisely , appears in the convergents of the random Fibonacci series of Divakar Viswanath.