Problems & Puzzles: Puzzles

 Puzzle 816.Primes between n*k and n*(k+1) T. D. Noe sent the following nice puzzle. For any given n, what is the maximum number of primes between n*k and n*(k+1)?  If you can't give an exact number, can you give some upper limit?  See my sequence S000064. To compute the n-th term, you compute maximum number of primes between n*k and n*(k+1) for some k > 0.  So for n=2, what is the maximum number of primes between 2*k and 2*(k+1)?  This must be 1.

Contribution came from Emmanuel Vantieghem.

***

Emmanuel wrote:

There is a way to compute an upper bound as follows  :
Let  p  be the greatest prime <= n. and  P  the product of all primes <= p.
Let  G  be the  least common multiple of  n  and  P.
Thus, the range form  1  to  G  can be divided into  G/n  non-overlapping subinterval of type (1+n*k ,n*(k+1) )  (k = 0, 1, ... , G/n - 1).
In every such interval there are  t(k)  numbers  m  such that  GCD(m,P) = 1.
The maximum of these  t(k)  is then an upper bound for the number of primes in any interval of the form  ( n*k + 1 ,n*(k+1) ).  (k = 1, 2, 3 ... , infinity )
Indeed, any prime in an interval of the form   (1+n*k ,n*(k+1) )  is relatively prime to  P  and the set of numbers relatively prime to  P  has a 'periodicity'.
More precisely : the sequence  t(k)  is periodic.

Eilas, due to the size of  P, it may become extremely difficult to compute that upper bound. I arrived to compute it for  2 < n <= 22.  Here are the results (b = the upper bound):

n     b
2     1
3     1
4     2
5     2
6     2
7     2
8     3
9     3
10     4
11     4
12     4
13     4
14     4
15     4
16     5
17     5
18     6
19     6
20     6
21     5
22     7

These results confirm that the conjectured values for  n <= 22  are also the exact values.

...

I just finished the case  n = 23. This gave the upper bound 7.

***

Emmanuel wrote again on Jan 10, 2016:

I worked a bit further on this very interesting puzzle 816.

Noe's results matches my upperbound for  n  up to 30.

For bigger  n  my program was too slow or consumed too much memory.  Thus, I made a kind of guess for the upperbound for  n = 31 up to 40  as follows :
I looked for the number  t  of 'totatives' of  P  in intervals of the form  (1+ k*n, (k+1)*n)  for  k = 1, 2 ...
After a while, for some  k0 (< 15000), I found a value  t0  that seemed not to be surpassed when  k  increased up to 1000000.

Of course, it is possible that the maximum value occurs for some  k > 1000000  but I don't believe this happens in the region  n <= 40.

Once I found my maximum  t0 , I searched for the primes in intervals of the form  (m*G+1+ k*n, m*G+(k+1)*n)  where  G  is the LCM  of  P  and  n.
If there was no interval with  t0  primes within reasonable bounds for  m, I took the next interval of the form  (1+ k*n, (k+1)*n)  with  t0  totatives,
and continued in the same way.

Example.  When  n = 32, the (supposed) maximum of  9  totatives appeared for  k = 2153.  The intervals  (m*G+1+ k*n, m*G+(k+1)*n)  for  m < 10^6  all contained less than (<)  9  primes.  So, I looked for the next  k  that gave  9  totatives.
This was  5931  but again, there were not enough primes.  I had to go up to  k = 14858.  This delivered the following primes :
741605304176531777, 741605304176531779, 741605304176531783, 741605304176531789, 741605304176531791, 741605304176531797, 741605304176531801, 741605304176531803, 741605304176531807
These are nine primenumbers between  32*23175165755516618  and  32*23175165755516619.  So, I think Noe's value  S000064(32)  should be  9.
I think the values for  n = 34, 36 up to 40  can be augmented by one.  I'll try to find the necessary quantity of primes but this can take a bit of time (and it is possible that those primes do not exist !).

***

 Records   |  Conjectures  |  Problems  |  Puzzles