3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thanks. I suspect primorial is the best choice for low bound. $\endgroup$ – joro Sep 9 '15 at 10:31
  • $\begingroup$ I edited with possible application of upper polynomial bound. $\endgroup$ – joro Sep 9 '15 at 10:58
  • $\begingroup$ The $q$ in the linked answers is larger than $\exp(n)$. $\endgroup$ – joro Sep 10 '15 at 7:08
  • $\begingroup$ @joro it's $n^n,$ thus the $\epsilon.$ $\endgroup$ – Igor Rivin Sep 10 '15 at 7:13
  • $\begingroup$ How is it $n^n$? $\log{n\#}=\theta(p_n)\sim p_n$. Chebyshev theta. $\endgroup$ – joro Sep 10 '15 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.