Author Topic: A Simple formula to predict the number of primes  (Read 3954 times)

0 Members and 1 Guest are viewing this topic.

IJSER Content Writer

  • Sr. Member
  • ****
  • Posts: 327
  • Karma: +0/-1
    • View Profile
A Simple formula to predict the number of primes
« on: February 18, 2012, 02:24:58 am »
Author : Prithvijit Chakrabarty
International Journal of Scientific & Engineering Research Volume 3, Issue 1, January-2012
ISSN 2229-5518
Download Full Paper : PDF

Abstract— This paper describes a formula to predict the number of prime numbers between a known prime  'P' and its square, when all primes up to ‘P’ are known.
   The formula is developed by considering a continuous section of the number line between P and P2. The length of this section is repeatedly divided by primes below P to obtain the number of primes in the region. The process is similar to the Sieve of Eratosthenes. However, instead of eliminating the multiples of primes below P, it eliminates the number of multiples of these primes. This reduces it to a simplifiable algebraic expression that can easily be implemented using programs.

Index Terms— Divisibility, factors, multiples, number, prime, range, square.

1   INTRODUCTION                                                                      
ANY number can be tested to be a prime by checking divi-siblity by primes below its square root. If we consider a number P2, where is a known prime, then, division of P2 with primes numbers below must be performed to test its primality. In other words, if P2 is composite, it is guaranteed to be divisible by prime numbers below P.
   Similarly, if there are composites between the num-bers P and P2, then they must be divisible by primes below their square root. As they are less than P2, their square root will be less than P and they will be divisible by primes below P. Thus, all composite numbers from P to P2 are guaranteed to be divisble by primes below P.
your paper.

If we consider 'n' consecutive natural numbers, then, half of them them will be odd and half will be even, i.e, in this range, there will be   even and  odd numbers, or  multiples of 2. Similarly, there will be  multiples of 3 in this range. However, some of these multiples will be divisible by 2 as well. Thus, to find numbers divisible only by 3 and a number greater than 3, we must find the number
of multiples of 3 among the numbers excluding the multiples of 2. In a range of n, numbers, there will be  such numbers. Similarly, there will be  multiples of 5 that are divisible only by numbers greater than 5 and 5. In this manner, the number of multiples of any prime 'p' in a range of 'n' con secutive natural numbers can be found by subtracting the total
number of multiples of primes below 'p' from 'n' and dividing it with 'p'.

The process of finding multiples of primes mentioned above can be used to find the total number of multiples of all primes up to P in the range of P to P2. As all composite numbers in this range are multiples of these primes, we can obtain the number of composite numbers in this range.
   In this range, the number of consecutive natural numbers present is (P2-P). If this value is  , then,
   Number of multiples of 2=          (= )
   Number of multiples of 3=          (= )
From the previous step,  =    
Thus, the number of multiples of 3 can also be represented as            (1)
   Number of multiples of 5=       (= )
However, from the previous step,  is 
Thus, we may write the number of multiples of 5 as                  (2)

   Number of multiples of 7=       (= )
As  is  , the number of multiples of 7 will be              (3)
   Number of multiples of 11=       (= )
The previous step show that is  .
Hence, the number of multiples of 11 will be              (4)

      In this manner, the number of multiples of all the prime numbers less than P can be found.
Now, from the expressions (i), (ii), (iii), (iv) the general pattern the numbers follow can easily be deducted.
If we consider the series formed by these numbers, then, the ith term will be as follows:
pi-1 is the  (i-1)th  prime number,
pi is the  ith  prime number
ni-1 is the numerator of the (i-1)th term,
di-1 is the denominator of the (i-1)th term.

The total number of composite numbers that will be present between P and P2 will be:
where i varies from 0 to k such that P is the kth prime number.  The only exception to this is the number of multiples of 2(as there is no (-1)th prime.)
   As the number of composite numbers can be found, the remaining numbers in the range must be prime. Thus, the number of primes from P to P2 is:
                    (excluding the prime number P).

where ci-1 is the coefficient of   of the (i-1) th term.

   The most important property of the result (equation (v)) is that the presence of a large number of prime numbers can be detected by knowing a small number of primes. For example, there are only 7 primes below 11. If we know only these 7 primes, we can detect the presence of 25 other primes that are present between 11 and 121. Similarly, by finding out just 3 more primes, we can find the number of primes between 19 and 324. Thus, the range of the formula increases by a great extent with every prime number found.

This algorithm efficiently finds the number of primes in a given range. Though it does not predict the actual primes that will be present from P to P2, when implemented using programs, the number of primes can be predicted quickly and with great ease due to the simplicity of the formula.

Read More: Click here...