3

OEIS A076689

Is defined as smallest integer $a(n)=k$ such that $k n\#+1$ is prime, where $n\#$ is primorial, the product of the first $n$ primes.

Lower bound appears $1$, the primorial primes.

What is upper bound for $a(n)$, possibly using plausible conjectures?

By examining the B-file, it might as low as $Cn$.

Upper bound polynomial in $n$ might give fast deterministic algorithm for finding large primes: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

joro
  • 24,174

1 Answers1

2

The answers to this question seem to indicate that there is an upper bound of the form $O(n^{2+\epsilon})$ for any $\epsilon$ (using the unpublished result of Oesterle). I am sure experts might say more (and this does not use the primoriality in any way).

Community
  • 1
Igor Rivin
  • 95,560
  • Thanks. I suspect primorial is the best choice for low bound. – joro Sep 09 '15 at 10:31
  • I edited with possible application of upper polynomial bound. – joro Sep 09 '15 at 10:58
  • The $q$ in the linked answers is larger than $\exp(n)$. – joro Sep 10 '15 at 07:08
  • @joro it's $n^n,$ thus the $\epsilon.$ – Igor Rivin Sep 10 '15 at 07:13
  • How is it $n^n$? $\log{n#}=\theta(p_n)\sim p_n$. Chebyshev theta. – joro Sep 10 '15 at 07:18
  • Do you mean this result: $p \leq 70 q (\log q)^2$ under GRH? This indeed appears to give something close to your claim :) – joro Sep 10 '15 at 07:55
  • Hm, the linked question require $q$ to be prime AFAICT. – joro Sep 10 '15 at 08:01
  • @joro yes, $\log n \sim p_n \sim n \log n.$ As for $q$ being prime, I am not sure what the assumptions of Oesterle's alleged results are, but I don't see where the primality would matter... – Igor Rivin Sep 10 '15 at 09:09
  • I suspect the same too. Btw, you appear to have typo in your comment, likely missing/not escaping "#". – joro Sep 10 '15 at 09:21
  • Citable reference even for $q$ prime might solve this: https://mathoverflow.net/questions/217919/what-is-wrong-with-this-deterministic-algorithm-efficiently-generating-large-pri – joro Sep 10 '15 at 10:50
  • You appear to cite quite controversial result -- check the comments in the answer you link to. Some claim this is not proved... And the second best bound doesn't appear good for me. – joro Sep 10 '15 at 14:10