Division-multiplication parabolas, triplications, and quadratic residues

Introduction

Many strands of our investigations on conic-generating integer sequences, word fractals and cellular automaton models for pattern formation came together in an unexpected manner while investigating a simple integer sequence. While some of these connections have have been known before, others are to our knowledge unreported. We present our investigations in this regard below.

The division-multiplication parabola sequence and other associated sequences

Consider the following sequence :

; thereafter if,

;

else, and

Following our initial investigation, a search of OEIS revealed that this sequence was reported therein by Amarnath Murthy (A076039). The first few terms of are: 1, 2, 6, 1, 5, 30, 4, 32, 3, 30, 2, 24, 1, 14… A more detailed view of for increasing values of maximum is shown in Figure 1.

Figure 1

An examination of the sequence and its plot in Figure 1 reveals the following features:

1) The action of division and multiplication by takes place alternately. Hence, the sequence alternately bounces between high and low values.

2) However, on the larger scale it becomes apparent that the sequence shows cycles, each with the same overall pattern but of increasing magnitude (Figure 1).

3) A closer examination of these cycles shows that within each cycle the high values climb to a maximum and then fall off to reach a value which is 1 more than the first low value of the next cycle. In contrast, within each cycle the low values keep linearly decreasing until reaching 1. Then they start again with a new starting value in the next cycle.

4) Each new cycle starts with a large jump in magnitude relative the previous cycle. We can define the start of each new cycle objectively as after when . We find that when takes the values: 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454… This sequence can be described by the formula:

, where

We may also recursively define it as , from onward after defining the first term . We will show below that this sequence , which appears in the context of the cycles of , also appears in several other seemingly unrelated mathematical structures with interesting properties. It is also numerologically interesting that the 7th cycle corresponds to the approximate length of the earth year in days: 365.

5) The determination of the sequence allow us to trivially prove that the length of each cycle is:

, where . Thus, the expansion of the sequence is by the powers of 3.

6) The maximum value of each cycle is reached at the midpoint of each cycle and is attained when is 1, 2, 3, 8, 21, 62, 183, 548, 1641, 4922, 14763, 44288, 132861, 398582, 1195743, 3587228… This novel sequence termed can be described by the below formula:

7) The maximum value of each cycle is given by the novel sequence : 1, 2, 6, 32, 231, 1922, 16836, 150152, 1347261, 12113042, 108980466, 980713472, 8826089091… can be obtained by the formula:

where

8) Thus, the ratio is the sequence 1, 1, 2, 4, 11, 31, 92, 274, 821, 2461, 7382… defined by the formula:

This sequence can also be generated from by the formula:

We will see below that this sequence remarkably also emerges in another area of higher arithmetic.

9) Whereas the low values of decrease linearly from their starting point in a cycle till they reach 1, the high values which they alternate with appear to be defined by successively larger parabolic arcs (Figure 2). We determined these parabolic arcs to have the general equation of the form:

Here, and each successive arc spans the high values in the range to . Hence, we term sequence the division-multiplication-parabola sequence (DMPS). Thus, in a sense our sequence is a “triessential” sequence with the number 3 being fundamentally linked to it in many ways.

Figure 2.

The idea of this type of parabola first came to us over 23 years ago in the context of trying to understand if natural selection might tend to select oligo-functional proteins over both purely mono-functional ones and those that perform a large number of distinct functions. The idea is each new function gained by a protein results in an increased cost for the other functions it performs; however, there could be a net fitness gain from the compounding of the capacity to now perform multiple functions. This would result in an optimal point after which the performance in each function will deteriorate too much to have net fitness gain despite the compounding. The result would be a parabolic arc similar to that obtained in the DMPS.

In the remainder of this article we shall discuss the connections we have found between the sequences associated with the DMPS and other mathematical objects.

The Mephisto-Waltz words

A Mephisto-Waltz word is a word in a two-symbol alphabet that is generated by a triplicative substitution system with the rules . The growth is initiated with . Thus, we get the following words:

and so on. This can be graphically represented as the triplicative growth of circular cells with differentiation (Figure 3).

Figure 3.

The Mephisto-Waltz words can also be used to generate another kind of pattern in the form of a square using Cantor’s pairing function. Cantor’s pairing function maps every ordered pair of non-negative integers to a single unique integer :

Now, if we pair every ‘letter’ in the Mephisto-Waltz word with every other ‘letter’ in it with the above Cantor function then get the square pattern shown in Figure 4. Since there are four distinct pairings possible between 0 and 1, i.e. (0,0), (0,1), (1,0) and (1,1), under the the Cantor function each cell of the ensuing square matrix can have one of four values, each shown in a different color.

Figure 4.

We can also apply a form of “epigenetic” information to the genetic encoding of a folding instruction in the two symbol Mephisto-Waltz word. It goes thus: We start out drawing a line segment in a certain direction. If we encounter a we draw a line segment of fixed length in the same direction as we are currently oriented in. If we encounter and it is in an even position (epigenetic information) then we turn by an angle of and draw a line segment of the same fixed length in the new orientation. If we encounter in an odd position in then we do the same but turning by . This results in the fractal “wave” illustrated in Figure 5.

Figure 5.

Mephisto-Waltz words show an intimate connection to sequences emerging from the DMPS: First, given that they have a triplicative growth pattern their length grows as , which is the same as the length of the cycles of the DMPS. Second, the numbers of zeros in the Mephisto-Waltz words grow as the sequence , which defines the points of transition to the next cycle of the DMPS. The numbers of 1s in these words grow as . Thus in a sense the sequence captures the ‘median’ growth of these words.

Standard order words in a 3-symbol alphabet

Consider an alphabet with 3 symbols. We can denote those 3 alphabets by the numbers 1, 2, 3. Then we write the following words in the this alphabet:

1, 12, 12123, 12123123123123, 12123123123123123123123123123123123123123 …

One observes that the process goes thus: we first write 1, then 12, which form the first two words. Then from the 3rd word onward we add letters (where ) in the form of repeats of 123. Thus, the length of these words grows as 1, 2, 5, 14, 41, 122… which is the same as the sequence defining the transitions to the next cycle in the DMPS.

Standard order means that a later symbol of the alphabet cannot appear in the word unless the symbol earlier to it has already appeared in the word. Thus, 2 cannot appear in the word unless 1 has already appeared. Likewise, 3 cannot appear in a word unless 1 and 2 have already appeared. Thus, if traverse through the above-generated 3-symbol words from the one to the next we can create -letter words with a maximum of 3-symbols in standard order:

For 1-letter words we can only have: 1
For 2-letter words we can only get: 11, 12
For 3-letter words we get: 111, 112, 121, 122, 123
For 4-letter words we get: 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233
So on (OEIS: A278985). Thus, the number of -letter standard order words we can get in a 3-symbol alphabet is the same as the sequence .

The number of quadratic residues of

Quadratic residues were extensively studied by Carl Gauss in his celebrated Disquisitiones Arithmeticae. The quadratic residues for a number are determined by considering all . Then . Further, given that , we only need to compute the residues for .

For example, if we take , then we have the residues: . Thus, for , the numbers 0, 1, 4, 7 are its quadratic residues. We observe that of the numbers from 0 to (9-1=8) the following are not represented: 2, 3, 5, 6, 8. These are the quadratic non-residues of 9.

Let us now consider the quadratic residues of the powers of 3 and count how many of them are there for each power:

So on…

We see than the number of quadratic residues for the powers of 3 specify the sequence starting from the second term. This is the ratio of the maximum value to the midpoint of the cycle of the DMPS where it is attained.

We also noted that a sequence closely related to turns up in the graph theory. While this sequence is defined as:

In graph theory a circuit is defined as graph in which by passing through adjacent vertices one can reach the same vertex. Now, if we specify that adjacent vertices should be colored using different colors, then we need a minimum of 4 colors to color all vertices of any circuit graph. The number of distinct configurations that a circuit graph with vertices can be colored with 4 colors was shown to be by Bernhart (OEIS: A006342). This sequence goes as: 0, 1, 1, 4, 10, 31, 91, 274, 820, 2461, 7381, 22144, 66430, 199291, 597871, 1793614 … One can see that it differs from by 1 at every odd , i.e. .

Thus, rather notably, a simple arithmetic procedure generates the DMPS, with associated sequences bearing connections to other seemingly unrelated mathematical objects pointing to the pervasiveness of certain combinatoric numbers.