Generalizations of the prime sieve and Pi

PDF version for better reading

Eratosthenes, the preeminent yavana philosopher of early Ptolemaic Egypt [footnote 1], composed a hymn to the god Hermes of which only some fragments have come down to us. This connection to Hermes is evidently related to his Egyptian locus, where the old ritual-experts saw all manner of clever inventions and ritual ordinances as being set down by their god Thoth, who was syncretized with Hermes of the yavana conquerors of Egypt. In this hymn, Eratosthenes describes Hermes as looking down on universe from the highest sphere of heaven ( Ārya parame vyoman [footnote 2]. As he did so, Hermes is mentioned as perceiving the harmony of the spheres of the planets and the world axis passing through the earth in the center. Eratosthenes represented these harmonies in the form of the lyre that was invented by the god Hermes and gifted to the god Apollo. Eratosthenes, held that while surveying the universe from the highest sphere, Hermes saw that the “harmony of the spheres” was the same as the harmony of his lyre. This equivalence of the harmonies was seen by these yavanācarya-s as illustrating the desmos (equivalent of Ārya saṃbandha: the common thread, bindings, equivalences) that runs across different branches of mathematics (noted by Friedrich Solmsen who brought to light the religious background of Eratosthenes, something that is ignored by those who wish to paint him in the image of a modern “scientist” of the Occident ). Indeed, similar “harmonies” were perceived by the yavana sage Pythagoras and before him in the form of the numerical sambandha-s of the Ārya-s of the Yajurveda — such mysterious numerical patterns and conjunctions bring together apparent disparate branches of mathematics.

Keeping with the god with whom he had a special connection, Eratosthenes was the inventive kind, who, while a Platonist (made clear by the sage Iamblichus), was somewhat unlike those of the pure geometric school — he described to king Ptolemaios a method of doubling the Delian altar of Apollo with a machine rather than the geometric constructions of Eudoxus (believed to be divinely inspired) using the curve known as the kampyle or the conics used by Plato’s associates Menaechmus and Dinostratus. Likewise, he was more like the Ārya-s in his algorithmic methods pertaining to numbers — perhaps most famously the sieve for prime numbers is attributed to him. We had the experience of such a sambandha while exploring the prime sieve and its generalizations.

The prime sieve is a simple but powerful algorithm for extracting the sequence of prime numbers that one might have learned in elementary school. While a product of the ancient world, its power is best appreciated in the modern computer age and is recommended to students as one of the first computer programs to write. In its modern form it goes thus (the ancient yavana concept of numbers was geometric and not exactly the same as we might take it be):

• Write out the sequence of integers

• Move the first integer in this sequence to sequence and kill all its multiples from the above sequence (circled):

• This yields a new sequence: Again move the first term of this sequence to sequence and kill its multiples in this sequence (circled):

• Repeat this procedure with for as many cycles as required. Thus, you get the sequence of prime numbers

Millennia after Eratosthenes, in the 1950s, Jabotinsky generalized this sieve algorithm to generate other notable sequences. The first of these goes thus:

• Write out the sequence of integers

• Move the first integer in this sequence to sequence and kill all integers by jumping by a skip of size equal to that first integer, starting from that first integer of the above sequence (circled):

• This yields a new sequence: Again move the first term of this sequence to sequence and kill all integers by jumping with a skip equal to the new first integer starting from it (circled):

• This yields a new sequence: . We illustrate the next few steps below:

• Thus, the above sieve yields the sequence

The form of the sequence originally published by Erdős and Jabotinsky is the above sequence plus 1 (Sometimes called Ludic numbers). i.e.:

This sequence can also be generated by applying a sieve just as above starting with an initial sequence and killing integers with a skip of size equal to first term of the intermediate sequence minus 1. As one can see, this version of the sequence includes certain primes and certain odd numbers which are not primes (e.g. 25, 77, 91, 115, 119, 121, 143, 161, 175 …).

We know that prime number sequence has a scaling which can be asymptotically represented by . Now we can ask how does this sequence generated by the generalized sieve scale (Figure 1)?

Figure 1. Scaling of sequence .

We see that grows more rapidly than (Figure 1, black line) though it must be asymptotic to the latter. Thus, there must be additional terms to get a better asymptotic fit than (Figure 1, gray line). Figure 1 shows at till the term 10000 lies between:

(brown dotted line) and

(brown solid line),

where is Euler’s constant.

Erdős and Jabotinsky have shown that for large the growth of sequence exceeds the above higher bound by a further correction term.

We can generate another related sequence by a similar sieve where we kill the terms by skipping over the value first term. This results in the sequence

Unlike the sequence it includes both odd and even numbers and one notices that starting from the term .

As one can see it scales at half rate of the sequence . Thus, this type of generalized sieve reveals that sequences arising from a process, where the skip is dependent on the first term of the intermediate sequence, are asymptotic with a function whose base term is of the form , where is a constant. One may say that of these the one which yields the primes is some kind of an optimal sieve that lets neither too few nor two many numbers pass through it. Thus, intuitively, the primes can be seen as an inherent optimal path through the number world.

The next type of sieve of Jabotinsky is operated thus:

• Write out the sequence of integers

• Move the first integer in this sequence to sequence and kill all integers by jumping by a skip of size 1 starting from the first integer of the above sequence (circled):

• This yields a new sequence: Now we operate on this sequence by sending the first term to sequence and starting from it killing all terms by jump with a skip of 2 (circled):

• This yields a new sequence: We repeat the above procedure, killing terms in each iteration with skips of 3, 4, 5… As a result we get the sequence:

This sequence relates to a function on positive integers ; we illustrate this function by the example of :

• We take 8 and reduce it by 1 to get 7.

• We then get the lowest multiple of 7 that is greater than 8 .

• We then reduce 7 by 1 and obtain lowest multiple of 6 that is greater than 14 .

• We continue this procedure till the successive reduction ends in 1. The corresponding sequence of their multiples is:

• Thus, we get

Remarkably, it turns out that is the sequence of .

Figure 2. Scaling of sequence

Even more remarkably, ; where is a correction term. Erdős and Jabotinsky showed that in the big notation. For relatively small we can safely write , i.e. a parabolic scaling with as the coefficient (brown line in Figure 2). Thus, the generalized sieving procedure yields a sequence that provides a mysterious “desmos” to yet again linking disparate branches of mathematics. More generally, it points that beneath these branches lie relatively simply computational processes such as the sieve, whose original form was attributed to Eratosthenes, which yields a variety of entities organically, like prime numbers or .

Finally, this parabolic scaling with as the constant also brings to mind an interesting iterative generator of and , apparently first discovered by Cloitre:

• Initiate two maps with the terms and

• Iterate the maps as and

• scales as and scales as

Figure 3. Maps generating and .

Here, while the map generates via a linear relationship it generated via a parabolic relationship.

---

Footnote 1: Sometimes he is called the new or second Plato; Archimedes addresses him as philosophías proestō̃ta

Footnote 2: This evidently derives from an old IE tradition as one can also compare it with the phrase used for the cognate deity Pūṣaṇ: saṃcakṣāṇo bhuvanā deva īyate by the Aṅgiras, Bharadvāja Bārhaspatya, in RV 6.58.2. In Greek world, there were two evolutes descending from the Proto-Indo-European cognate of Pūṣaṇ: Hermes and Pan