Contribution came from Emmanuel Vantieghem.
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)
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):
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.
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,
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 :
741605304176531779, 741605304176531783, 741605304176531789,
741605304176531791, 741605304176531797, 741605304176531801,
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 !).