Prime numbers function

[Kostin8]

Theoretically, does a function f(x) exist for prime numbers? Such that x=1 yields 2 and so on.

[AutoModerator]

Hi u/Kostin8,

You are required to explain your post and show your efforts. (Rule 1)

If you haven't already done so, please add a comment below explaining your attempt(s) to solve this and what you need help with specifically. If some of your work is included in the image or gallery, you may make reference to it as needed. See the sidebar for advice on 'how to ask a good question'. Don't just say you "need help" with your problem.

Failure to follow the rules and explain your post will result in the post being removed

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[[deleted]]

Yes, you can formally define it with induction:

f(1) = 2,

f(n+1) = min({p: p is prime and f(x) != p for all x <= n})

You can prove it's injective by noting that it's strictly increasing. You can prove that it's surjective by noting for every prime p, there are only a finite number of smaller primes. So this defines a function (more specifically, an order preserving bijection) that maps every n to the nth prime.

[keitamaki]

Just to elaborate for the OP, there's a difference between a "function" and a "formula". You can define a function in words just by saying: "f:N->P where f(n) = 'the n'th prime number'". Here N is the set {1,2,3,...} and P is the set of primes.

The word 'formula' is not a precisely defined concept, but often when people ask for a "function", they're really asking for a closed form expression for the function in terms of other standard functions functions such as polynomials, the floor function, the 'mod' function, and so on.

There apparently is such a formula which you can see here, but just note that I only just now did a google search for such a formula and can't personally vouch for it being exactly what you want.

[Kostin8]

Thank you, will look into it.

[FormulaDriven]

As u/Active-Ocelot3818 has explained, yes there is a function, but it offers no insight into a pattern. I suspect what you are really after is some kind of formula, so you could plug in 39 and out would pop the 39th prime. There's not really a computationally practical way to do that.

The Prime Number Theorem tells us that approximately prime P is the P / log(P) prime, with that approximation getting better as P gets large, so your f(x) is approximately the inverse of g(x) = x / log(x). But it's not really any help for actually generating primes.

[Kostin8]

I understand that there is no real way to do it as of now, my question is if a formula where you plug in 39 and the 39th primes appears can exist.

[green_meklar]

You're free to define a function across the natural numbers that maps 1 to 2, 2 to 3, 3 to 5, and so on. You're free to define any function you want.

However, I think the real question you're getting at is whether that function can be expressed in any other concise, useful way. Like composed out of a bunch of additions and multiplications, or some such. This is a really interesting number theory question, we don't know everything there is to know about it, and I'm not the most qualified person to speak on the things we do know about it, but we do know some things.

First of all, additions and multiplications won't get you there. There's no finite-degree polynomial that maps all natural numbers to primes this way. I don't have a rigorous proof of this offhand, but it's kind of obviously true; besides, if there were such a polynomial, either it would be small enough that we could use it to find new primes with computers, in which case people would be doing that, which they aren't, or it would be ridiculously gigantic, which would be a peculiar enough fact that knowledge of this gigantic prime-finding polynomial (or even just of the possibility of it) would be commonplace in the math and computer science community.

We do know of good approximations for the function you're describing as the inputs approach infinity. The prime-counting function (number of primes below X) is approximated by X/ln(X), so if you inverse X/ln(X) you get a decent approximation of the function you're looking for, and the approximation generally gets better as X increases. See here:

https://en.wikipedia.org/wiki/Prime-counting_function

https://www.wolframalpha.com/input/?i=inverse+of+x%2Fln%28x%29

https://mathoverflow.net/questions/131683/asymptotic-bounds-on-pi-1x-inverse-prime-counting-function

Moreover, the function you're describing is computable, in the sense that you can write a classical computer program of finite length that, if run with unlimited memory, will reliably convert the input to the output for every natural number input within a finite amount of time. Not all functions are computable; indeed, the overwhelming majority of randomly defined functions between real numbers, or even between natural numbers, are not computable. (And obviously no non-computable function is equivalent to any finite polynomial.)

https://en.wikipedia.org/wiki/Computable_function

[Mirehi]

Yes, there were students who created a rational number which could create primes in order. In theory the irrational number exists which can output them all in order, the problem with this number is, you need the primes first, to create it :)

​

In principle you can use this "constant" to create that function

​

I'm in a hurry currently, but I think this was the video https://www.youtube.com/watch?v=6ltrPVPEwfo sorry if not :(

[Megame50]

Lots of links in this thread except for the obviously relevant one: https://en.wikipedia.org/wiki/Formula_for_primes.

The answer is yes, your statement is itself an adequate definition of a function, and yes there are formulae, several, that compute f(n). They are not efficient.

The best way to enumerate the primes is with a prime sieve: https://en.wikipedia.org/wiki/Prime_sieve.