# Length of the binary representation of a primorial

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$ ?

• $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 – Gerhard Paseman Jan 22 '15 at 20:12
• @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) – Marzio De Biasi Jan 22 '15 at 20:13
• 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 – Gerhard Paseman Jan 22 '15 at 20:16
• 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 – Gerhard Paseman Jan 22 '15 at 21:09
• $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. – Emil Jeřábek Jan 22 '15 at 22:15

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.