# Upper bound for OEIS A076689 “Smallest k such that k*p#+1 is prime”?

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

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).
• The $q$ in the linked answers is larger than $\exp(n)$. – joro Sep 10 '15 at 7:08
• @joro it's $n^n,$ thus the $\epsilon.$ – Igor Rivin Sep 10 '15 at 7:13
• How is it $n^n$? $\log{n\#}=\theta(p_n)\sim p_n$. Chebyshev theta. – joro Sep 10 '15 at 7:18