Study of Some Sequences of Prime Numbers Defined by Iteration

Idir Sadani

Turkish Journal of Analysis and Number Theory

Study of Some Sequences of Prime Numbers Defined by Iteration

Idir Sadani

Department of Mathematics, University of Mouloud Mammeri, Tizi-Ouzou. Algeria


We study the properties of prime number sequences obtained using a well-defined equivalence relation . It will be seen that the elements of each class of are all prime numbers which constitute the fundamental object of our study. The number of prime numbers of each class less than or equal to a given quantity , the number of the different equivalence classes and some other results will be deduced.

Cite this article:

  • Idir Sadani. Study of Some Sequences of Prime Numbers Defined by Iteration. Turkish Journal of Analysis and Number Theory. Vol. 3, No. 4, 2015, pp 97-103.
  • Sadani, Idir. "Study of Some Sequences of Prime Numbers Defined by Iteration." Turkish Journal of Analysis and Number Theory 3.4 (2015): 97-103.
  • Sadani, I. (2015). Study of Some Sequences of Prime Numbers Defined by Iteration. Turkish Journal of Analysis and Number Theory, 3(4), 97-103.
  • Sadani, Idir. "Study of Some Sequences of Prime Numbers Defined by Iteration." Turkish Journal of Analysis and Number Theory 3, no. 4 (2015): 97-103.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

Let be the set of prime numbers, and for all , let denote the number of prime numbers less than or equal to . The prime number theorem which was shown independently by de la Vallée Poussin [1], and Hadamard [2] in 1896, states that:



where is the logarithmic integral of defined by:

We can give an equivalent statement for this theorem as, for example, let denote the n'th prime number. Then


One of our objectives here is to use a restriction of the function to to study intrinsic properties of some sequences of primes defined by iterations. The point of departure for this study is the construction of an equivalence relation that we denote by . The purpose of this equivalence relation is to show first, that there is a recurrence relation between prime numbers which can be arranged in an infinity of well-defined classes dependent on the initial value. Second, the use of its properties with the famous prime number theorem is one way to find and prove other results for the possible applications in number theory. Part of our motivation came from the prime number theorem and the Riemann hypothesis. Also, it was an attempt to establish the relationship between these prime numbers classes and several as-yet unproved conjectures, such as Goldbach's Conjecture and Twin Prime Conjecture.

The structure of this paper is as follows. In section 2, we begin with the definition of our equivalence relation and its equivalence classes where is a prime number, which constitute the fundamental object of study, and we propose some preliminary results. In section 3, we exhibit the main results of this work by introducing and studying the functions and . The methods used here are part of elementary number theory and we have attempted to present the ideas in as elementary a way as possible. Finally, in section 4, we give some open questions related this subject.


1) We set

this function count the number of primes less than .

2) We define the following functions:

where is the composition operator.

3) In many situations, we search to estimate , where . Then, we use the following formula:


2. Preliminary results

2.1. The Classes and Its Elements

We start with the following lemma:

Lemma 2.1. Let be the restriction of to . Then, is a bijection and its inverse function is .

Notation. Throughout this paper, we simply use the notation to designate the restriction of to the set instead of using .

The proof of the following theorem is obvious.

Theorem 2.1. We define the relation on the set of prime numbers defined by: if and are two prime numbers, if and only if:

1) for any prime number ,

2) there exists such that .

Then, is an equivalence relation.

Notation. The elements of the equivalence class are defined by:

The smallest element of , which we denote by , is called the origin of the class . Then, in this case, we note that the sets and have the same elements.

Example 1.

Notation. We denote by the set of all origins . The set is given explicitly by:

and we denote by the set of all origins less than or equal to .

Theorem 2.2. Let be a prime number. Then, is not a prime number implies that, for all , there is no an integer such that .

Proof. Let . By the prime number theorem, represents the -th prime number which we denote by .

Next, , implies that , which is the -th prime number, so we obtain the formula:


Now, we use the equation (4) which composed by gives

that is the -th prime number. We can write

Inductively, we obtain the following general formula:


To each number , we associate the set :

Now, suppose that is not a prime number, we must prove that for all , there is no such that . To show this, suppose that there exists a positive integer such that , i.e., and we show that is a prime number. Hence, we have, if and only if , which implies that .

But, for all is prime, which proves what we wanted.

Remark. The cardinality of the set is infinite.

Theorem 2.3. There exists a partition of the set of prime numbers defined by

such that , where and is not prime number.

Proof. On the one hand, according to the prime number theorem, the number of prime numbers belonging to is equal to . On the other hand, by the Theorem 2.2, there are prime numbers which do not belong to . We denote these numbers by , where . So, we obtain of sets which are defined by:

such that and . Finally, it is not difficult to see that the sets constitute a partition of the set of prime numbers less than or equal to . So, since is arbitrary in , letting tend to we obtain an infinity of sets which then form a partition of the set .

Theorem 2.4. Let be a finite set of prime numbers defined by

such that are consecutive. Then, there exists at least one set where , such that .

Before giving the proof of this result, we give an illustrative example.

Example 2. Let be a set which defined by

• The class of the integer 5 is and its cardinality is greater than 1.

• We notice that , therefore the integer 7 constitutes the origin of a new class which is and its cardinality is greater than 1. It only remains to see that the prime number 13 does not belong to the two classes and . Thus the prime number 13 constitutes the origin of a new class and clearly its cardinality is 1.

Proof of theorem 2.4. We suppose that each class containing at least two elements i.e., the cardinality of is equal or greater than 2, and we suppose that is prime. According to the theorem of prime numbers, the interval contains prime numbers. This leads to the two following cases:

If , i.e., there exists only one prime number in , namely . Therefore, we obtain and is not a prime number since and are consecutive. Then contains only one element in which is the prime number .

If , i.e., there exist at least two prime numbers in , namely . We suppose that where , is a prime number. Then is not prime and since , then, the unique element of is .

Finally, in both cases, there exist at least one class where , such that is a unique element of this class in , i.e., . The proof now is completed.

We have the following definition:

Definition 1. Let be the set defined as in the Theorem 2.4 and is a prime number belonging to . We say that is an outside class of , if

if in , we say that this class is an inside class of .

Remark. According to the Definition 1, the number is the smallest element of the class in , therefore, it is the origin of this class i.e., .

2.2. Study of

The function , , is a contraction. Therefore, the sequence defined by:

admits a fixed point. Since decreasing and is bounded below by , then it converges to the single fixed point .

Notation. , where is the function composition operator.

Theorem 2.5. Let be an initial value. Then


Proof. We set and we have

And combining all these, we obtain


Which is equivalent to


Then, passing to the limit, we obtain




and since

the formula (10) is obviously equivalent to

Which is the desired result.

Lemma 2.2. Let be the sequence which is decreasing and bounded below by , and let be a real number. Then, the number of iterations, which denote by , is depend on and the initial value , and given by :


where is a bounded value, and , i.e., depend on .

Proof. We have

where is the derivative of the function

where, . Inductively, we obtain

Next, there exists a real number , such that

Or in an equivalent way, since, and ,

We can extract the value of from the above equality:

and replacing by its value, we get

Now, according to the definition of , the sequences and are bounded, then it holds for the difference which we denote it by . Then, we have, by setting and :


Finally, we have the following limits:


3. Principal Results

3.1. Definition and Estimate of the Functions and

We set the following definition:

Definition 2. Let . We define

Then counts the number of prime numbers less than or equal to belonging to the class .

Lemma 3.1. We have

Proof. According to the definition of , there exists such that . Next, from the prime number theorem, we have

Moreover, supposing that with not a prime number, it follows that



Definition 3. Let . We define the functions and as follows:

Theorem 3.1. We have

Proof. In view of the proof of Lemma 3.1, we have,

which is equivalent to

Finally, for all fixed and tend to infinity, we have , then

i.e., .

Theorem 3.2. We have,


1) For the proof of the first formula, we have, on the one hand

Then we obtain

On the other hand, for all with , we have


Now, according to Lemma 3.1, , and then for sufficiently large (depending on ), , and thus

Now, for all , we can choose more near to 1. For this , so that , and for sufficiently large, we have

2) According to Theorem 3.1, we have

3) Concerning the third equality, we have

Evaluate now the difference


However, for



By using , since

we obtain

Then, .

3.2. Definition and Estimate of and
3.2.1. Definition and Estimate of

Definition 4.

1. Let be a positive real number. We denote by the number of different classes such that . Precisely,

2. We denote by the function defined by

Example 3. In [2,11], the value 2 represents the origin of the class but the values 3,5,11 do not, since they belong to the same class . The value 7 represent the origin of the class . Thus in this case, we have .

We have the following result:

Theorem 3.3. We have,

Proof. Suppose that the number of different classes is finite as . We know that


Next, let , where is finite by hypothesis. We obtain

Therefore, we have , and since the second sum has a finite number of terms, we deduce

which contradicts formula (13).

Theorem 3.4. Let . Then


Proof. To find the value of means that we estimate the number of origins . Clearly, the prime number is an origin that means is not a prime number. Then, let be between 2 and , and let be the greatest prime number in , therefore is not a prime number and for all integer , . So, we only have to search the numbers which are not primes and less than . Thus, we have

1° The number of the even numbers less than or equal to equal to .

2° The number of the odd numbers less than or equal to equal to such that is the number of the prime numbers less than or equal to .

Next, we add the two quantities, we obtain, since , the quantity which is equal to

3.2.2. Estimate of

For all initial value , we define the following sequence:


It is not difficult to see that, this sequence is stationary for and increasing divergent to infinite for and as . It is clear that, inductively, , then we have the following consequence:

Lemma 3.2. We have,

where represents the origin of the classes .

Proof.. Since for all , we have , then

In the expression:

the value of obviously depends on and if we denote by , then, we have

i.e., the number of elements of the form must be equal to number of prime numbers .

According to the formula (3), we have

therefore, the inequality is obtained directly by substitution.

Proposition 3.1. We have,



1. We have

Moreover, since

And recalling that

We obtain

The second inequality is obtained in the same way,

2. It is enough to tend to in the inequality (16).

4. Conclusion and Future Work

There is a lot of results on properties of prime numbers. There are innumerable ideas in this field regarding the randomness of prime numbers. However, it turns out that prime numbers do not appear absolutely randomly, meaning, it is not entirely true that there is no way whatsoever to see some relations and find some functions to generate a lenght of few prime numbers. Patterns do emerge in the distribution of primes over varied ranges of number sets. In this paper we have investigated sequences of primes obtained by the equivalence relation , from which we have associated various arithmetic functions. As we have seen in the sections above, many classical results stated in elementary number theory can be restated with our sequences. Also, there are many other asymptotic formulas can be deduced, we have just presented several of them as examples.

As far as motivation, the concern relates to the developing of new ideas for solving great unsolved problems and conjectures encountered in this field.

A highly intriguing area in primes is the concept of twin primes. These are prime numbers which differ by the number 2 for example: 3 and 5, 5 and 7, 11 and 13, etc. There is an attempt being made to prove that there are infinitely many twin primes that exist in the natural number system. These are the concepts that come to mind. Others are pretty much minor results.

Yitang Zhang, in his paper [3], attacked the problem by proving that the number of primes that are less than 70 million units apart is infinite. While 70 million is a long, long way away from 2, Zhang's work marked the first time anyone was able to assign any specific proven number to the gaps between primes.

In November 2013, James Maynard, in [4] , introduced a new refinement of the GPY sieve, allowing him to reduce the bound to 600 and show that for any there exists a bounded interval containing prime numbers.

At the present time, let me explain and share some general ideas and questions about my future work. Firstly, the questions raised are very broad in scope and cannot be addressed directly. This means that, it is preferable to resort to a methodology (plan in stages) to tackle the great problems in a structured manner. Secondly, for that reason, we have proposed and developed the results of this paper (see the problem 1 and 2).

Finally, here are just a few questions and conjectures a little more direct, I think are important.

Problem 1 The twin prime conjecture is equivalent to conjecturing the translates of the (the values of the pair ) are simultaneously prime values infinitely often. The question is: show that if the are simultaneously prime values infinitely often then the are simultaneously twin primes infinitely often, and then the twin prime conjecture is true. We have posed this question from the perspective of finding recurrence relation between primes.

Problem 2 Let and be twin primes. Show that

Problem 3

1. Does the set contain an infinity of twin primes?

2. Let fixed. Are there an infinity of primes of the form such that is prime?

3. Study of

There is continuing research to prove these conjectures and questions rigorously, using the results of this paper and advanced techniques in number theory in the next work.


We sincerely thank the editor and the referees for their valuable comments and suggestions.


[1]  C. J. de la Vallée Poussin, “Recherche analytique sur la théorie des nombres”, Ann. Soc. Sci. Bruxelle, 20. 183-256. 1896.
In article      
[2]  J. Hadamard, “Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques”, Bull. SOC. Math. France, 24. 199-220. 1896.
In article      
[3]  Y. Zhang, Bounded gaps between primes”, Ann. of Math, 179, 1121-1174. 2014.
In article      View Article
[4]  J. Maynard, “Small gaps between primes”, Ann. of Math, 181. 383-414. 2015.
In article      View Article
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn