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

Improve this question
$\endgroup$
6
  • $\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
    Commented Jan 22, 2015 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
    Commented Jan 22, 2015 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
    Commented Jan 22, 2015 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
    Commented Jan 22, 2015 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
    Commented Jan 22, 2015 at 22:15

1 Answer 1

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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