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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .