4
$\begingroup$

Let $p_n\# = \prod_{k=1}^n p_k$ be the $n$-th primorial.

Q1. Given $n$ (in binary) is there an efficient way (polynomial time) to calculate the exact number of digits of the binary representation of $p_n\#$; in other words calculate $m$ such that $2^m \leq p_n\# < 2^{m+1}$

Edit: The problem seems harder than I thought, so also the following could help:

Q2. Does the problem become easier if we "drop" a fixed number of low primes, i.e. we want to calculate the exact number of digits of the binary representation of $p_n\#^* = \prod_{k=a}^n p_k$ for some fixed $a$ ? And if we further relax it to $a = \log n$ ?

$\endgroup$
  • $\begingroup$ $n^n$ is a good upper bound to the nth primorial. Looking at estimates involving Chebyshev functions should easily get you to within a few bits. You might also consider estimations using ratios of factorials or perhaps binomial coefficients. Gerhard "Ask Me About Estimating Primes" Paseman, 2015.01.22 $\endgroup$ – Gerhard Paseman Jan 22 '15 at 20:12
  • $\begingroup$ @GerhardPaseman: I was wondering if there is an efficient way to calculate the exact number of bits. (I'm not an expert of number theory, but the result could help me to refine a problem in computational complexity) $\endgroup$ – Marzio De Biasi Jan 22 '15 at 20:13
  • $\begingroup$ Of course. I don't know the error in $\log (n^n/p\#_n)$, but I imagine it is small enough to be of use. You might consider the complexity of computing (the binary length of) $n^n$ to get a rough idea of what to hope for an answer to your question. Gerhard "Ask Me About System Design" Paseman, 2015.01.22 $\endgroup$ – Gerhard Paseman Jan 22 '15 at 20:16
  • $\begingroup$ It seems $n^n$ is a good upper bound only for some small $n \gt 3$. I will look at this more. Gerhard "Still A Few Bits Off" Paseman, 2015.01.22 $\endgroup$ – Gerhard Paseman Jan 22 '15 at 21:09
  • $\begingroup$ $p_n=n\log n+n\log\log n+O(n)$, hence $\log(p_n\#)=\theta(p_n)=n\log n+n\log\log n+O(n)$, so the $\log(n^n)$ estimate is only good to a handful of leading bits. $\endgroup$ – Emil Jeřábek Jan 22 '15 at 22:15
1
$\begingroup$

I believe no polynomial in $\log_2 n$ algorithm is known, since this is related to open problems.

Call your function $f(n)$. It is closely related to Chebyshev theta function

$$ \vartheta(x)=\sum_{p\le x} \log p $$

If you know $f(n)$ by base change of the logarithm you get very good approximation to $\vartheta(p_n)$ the error being small constant.

As far as I know, no such good approximations are known.

It is an open problem when $\vartheta(x) > li(x)$ see here.

Efficient computation of theta can be used for verification of Riemann hypothesis because of conditional bounds.

If it is of partial interest, there are bounds for theta (and $f(n)$) both unconditional and better conditional.

$\endgroup$

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.