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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.