0

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.

hanugm
  • 2,353
  • 1
  • 13
  • 34
  • 1
    Bijective from what to what? With the other conditions you've listed the function can never output $2$. – Qiaochu Yuan Nov 01 '14 at 05:22
  • @QiaochuYuan please go through it now . – hanugm Nov 01 '14 at 05:27
  • 1
    $O(1)$ seems absurd to ask for; it takes $O(\log n)$ time just to read the digits of a number of size $n$. – Qiaochu Yuan Nov 01 '14 at 05:30
  • 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$. – hanugm Nov 01 '14 at 05:34

1 Answers1

1

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

https://en.wikipedia.org/wiki/Mills'_constant

https://oeis.org/A051021

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

Zaaier
  • 203
  • Is A a rational number ? – hanugm Nov 01 '14 at 05:40
  • 1
    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. – Gerry Myerson Nov 01 '14 at 05:40
  • @hanu That is not known. – Zaaier Nov 01 '14 at 05:43
  • Is it implementable now by using A=1.3 ? I mean if i write a program using formula $\lfloor$$1.3^{3^n}$$\rfloor$ , can i get list of primes ....... – hanugm Nov 01 '14 at 05:43
  • @GerryMyerson Fair enough. (Although I'm not sure off the top of my head how one would go about splitting the digits at the correct place.) – Zaaier Nov 01 '14 at 05:43
  • Well, you could instead use the decimal that has four 1-digit primes, then 4 2-digit primes, then 4 3-digit primes, and so on. .235711131719101103107109.... Then it would be easy to work out where to split the digits. – Gerry Myerson Nov 01 '14 at 05:46
  • 1
    @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. – Zaaier Nov 01 '14 at 05:49
  • @GerryMyerson Yep. That'd work. – Zaaier Nov 01 '14 at 05:50
  • @Zaaier : Yeah , i want theorem like converse for this https://primes.utm.edu/notes/proofs/Theorem2.html – hanugm Nov 01 '14 at 05:52
  • 1
    @hanu I'm pretty sure no such thing exists. – Zaaier Nov 01 '14 at 05:54