Is there any non-identity monotonically increasing one-one univariate function that takes prime number as input and generates prime number as output ?

The asymptotic complexity to calculate output must me $O(1)$ (assume exponentiation is $O(1)$ operaton).

Output prime must be greater than input prime for all input primes.

  • 1
    $\begingroup$ Bijective from what to what? With the other conditions you've listed the function can never output $2$. $\endgroup$ – Qiaochu Yuan Nov 1 '14 at 5:22
  • $\begingroup$ @QiaochuYuan please go through it now . $\endgroup$ – hanugm Nov 1 '14 at 5:27
  • 1
    $\begingroup$ $O(1)$ seems absurd to ask for; it takes $O(\log n)$ time just to read the digits of a number of size $n$. $\endgroup$ – Qiaochu Yuan Nov 1 '14 at 5:30
  • $\begingroup$ I used it to avoid algorithmic answers such as $f(p)=p_p$ where $p_p$ is p th prime . I want non-abstract functions.I have to directly calculate from the input $p$. $\endgroup$ – hanugm Nov 1 '14 at 5:34

$f(n)$ $=$ $\lfloor$$A^{3^n}$$\rfloor$, where A is OEIS A051021 (~1.3).



(Though, it sounds like you're using this for a practical application, and I'm pretty sure this isn't practical.)

  • $\begingroup$ Is A a rational number ? $\endgroup$ – hanugm Nov 1 '14 at 5:40
  • 1
    $\begingroup$ That's fine if you assume $A$ is known to infinitely many decimals, but then you might as well use the decimal .23571113171923293137... obtained by concatenating the primes. $\endgroup$ – Gerry Myerson Nov 1 '14 at 5:40
  • $\begingroup$ @hanu That is not known. $\endgroup$ – Zaaier Nov 1 '14 at 5:43
  • 1
    $\begingroup$ @hanu I'm pretty sure you'll start getting wrong answers fairly quickly if you truncate it at 1.3. Um... so... generating primes algorithmically is going to be faster than refining A, then calculating f(n). There doesn't appear to be "free lunches" when it comes to prime number generation. I suspect a non-cheating-ish answer to your question would be worth a Fields Medal. I suggest using a well-optimised prime generator written in C or something if you're writing software that needs this. $\endgroup$ – Zaaier Nov 1 '14 at 5:49
  • 1
    $\begingroup$ @hanu I'm pretty sure no such thing exists. $\endgroup$ – Zaaier Nov 1 '14 at 5:54

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.