 # Nth Prime

34 posts / 0 new Nth Prime

What would be the value or implication (scientific, mathematical, or otherwise) of having a formula which gave us the nth prime?

## Subscription Note:

Email notifications will be sent out daily by default unless specified otherwise on your account which you can edit by going to your userpage here and clicking on the subscriptions tab. Might be useful for quickly generating a large prime, but it won't be a polynomial function, might be pretty nasty. So, it wouldn’t necessarily overturn the cryptographic world upside down?

Would it win me a Nobel prize in Science? At least? I could use the money. They don't give Nobel prizes for math, but there are other prizes it might win you. The problem is there technically already functions that can do this. The problem with them are is they are very, very complicated. Essentially they are just the normal method for finding primes (brute force), expressed in function form. When people talk about a function to tell you the nth prime, they typically mean a relatively simple (aka useful) function that can do it. That function is currently unknown (and I don't know if it can even exist, something to look into). To put it another way (I know that was a little complicated), I can write you a function to find the nth prime. And if you put it into a computer and ask it for the 5th prime, it will take lets say 1 unit of time. Then if you try for the 50th prime (10 times bigger), instead of taking 10 times longer, it might take 100 or a 1000 times longer. Basically the complexity (think difficulty) scales extremely quickly, so quickly it will be essentially useless for any large number; taking longer then your lifetime to answer the question.

When someone says they want a function to give them the primes; they probably mean they want one that doesn't scale like that. They probably mean one that could realistically be used on large numbers. This is an area I have some knowledge in.

Yes encryption does have connections with large prime numbers, but the "nth prime" is not needed nor useful for encryption. Significantly large prime numbers is just fine. The "overhead" of encrypting with really large prime numbers can actually make the entire encryption process too unwieldy to be relevant.

Especially as Moore's law collapses, well not even really moore's law, but more hitting the limit on how small transistors can get (which greatly effects Moore's law.) Since everything is stalled around 7 nm or larger for silicon based chips, it starts becoming a matter of money not tech. How much equipment, cooling and most notably electricity are you willing to throw at it? Finding prime numbers is actually not really hard compared to working backwards to find the two primes used to create the public key. But checking if a multiplication of two large prime numbers to be a "public key" you can only do via prime factorization, which is extremely computationally intensive, as there is no shortcut to do this. This is literally why public keys are often rely on this method. Because it takes a very long time to compute. You would have to check every possible number one at a time. Make numbers that are trillions times trillions large, and even supercomputers (more data centers) that can perform exoflops of number crunching a second could take a billion years to find the answer.

In other words, I could in a few minutes write a program with a large enough number, that prime factorization of it, would take up every single computing device in the world today, running at full speed for the rest of natural lives and it wont even be close to finishing it.

On the other hand, 128 bit encryption can be cracked in real time renting computation resources from say: amazon web services for maybe ~10 bucks a minute. And 128 bit allows for numbers well past trillions. (3.4 times 10^38.)

And to think the device you are writing this on can easily find the prime factorization of a number within a few minutes, (or seconds) that would take a life time of doing by hand.

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

I am an atheist that always likes a good debate
Please include @LogicFTW for responses to me
Tips on forum use. ▮ A.R. Member since 2016.
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ +1 for a like in your post.

I’m also interested in the cryptographic nature of the nth prime. I see exactly what you mean by what you say. Thank you. Finding a closed-form function f(n) that would give you the nth prime without computing all the previous primes first (as is done with the Sieve of Eratosthenes and related algorithms), would probably win you the Fields Medal in a heartbeat. The reason? Finding that function rapidly involves you in the intricacies of the Riemann zeta function, which is the function that describes the distribution of the primes. Worse still, finding the above fabled f(n), would almost certainly require you to prove the Riemann Hypothesis, a mathematical puzzle that has been taxing the minds of world class mathematicians for over a century. There's a \$1 million prize waiting for you at the Clay Mathematical Institute if you succeed in that endeavour.

So, if you want to have a crack at this, you can now spend the next five years learning all about the intricacies of the complex number field, including all the fun results such as those derived by Cauchy and Riemann in the 19th century (the infinite differentiability of complex functions being one of the big surprises lurking there for you), then another five years learning all about the Riemann zeta function and its features. After all that, if you think you've found a proof of the Riemann Hypothesis, you'll have the fun of persuading the Clay Mathematical Institute that you're right. Pass that hurdle, and you can kiss goodbye to anonymity here, as you'll be world famous.

Even after all of this, however, there's still the matter of making the leap from your proof of the Riemann Hypothesis, to that magic function f(n). Find a closed form for f(n) that doesn't involve some seriously nasty computational complexity, and you can write your own salary cheque from that point on. I’ve got a geometric representation of the nth prime. It’s sequential right triangles which map to a spiral function. And it involves Euler’s formula as well as the summation series of the nth prime.

And that’s where I’m stuck. I can’t navigate around the Euler function. Nor can I deal with complex equations.

Anyway. Maybe one day I’ll dig up the drawing. It’s interesting. The spiral pattern repeats itself every eight iterations.

All I need to do is an inductive step. But I’m no good at that either. Anyhow. If I dig it up and it works and someone solves it; please share the prize money with me ;) I wrote a simple example. I just went ahead and wrote it in python to make it easier to use. Here it is. Change line 11 (the line that says n = 25) to set the nth prime you want; n=25 means you want the 25th prime. I fooled around with different values of n, it and when I asked codepad to tell me the 5000th prime it cried and gave up.

If you can't figure out how it works; I gave it a list of known primes (just the number 2), and it then checks to see if 3 is evenly divisible by any of the known primes; it isn't so it adds 3 to the list of known primes, then tries 4. Rinse repeat until the list of known primes has n entries (the last entry being the nth prime). If you remember what Calilasseia told us:

Calilasseia - Finding a closed-form function f(n) that would give you the nth prime without computing all the previous primes first...would probably win you the Fields Medal in a heartbeat.

You'll notice my function does exactly what Calilasseia counseled you not to do; I'm calculating ALL of the previous primes, and I'm doing it in an inefficient way.

In fact, I'm sure even some forum members who aren't versed in this kind of thing can already think of a better way. We could just have it check 3, 5, 7, .... In other words, there are no even primes larger than 2, so there is no need to check every number, we can just check the odd numbers. Fixing that might make it run up to twice as fast, which is nice. However that isn't enough speed up to deal with how quickly this function will bog down with big numbers.

There are also many other glaring inefficiencies that can be fixed, but none of those will make this function into what we want. If we have to calculate the previous primes we are screwed. We a need to start over from scratch with a better (unknown) method. Way over my pay grade. But this is the approach I took.

First, I wanted to see if I could use geometry and induction to find the nth summation of any real number. And I successfully did this using triangles.

So, I moved on to the nth prime. And what’s interesting (and possibly trivial) is that the summation for the nth prime is divisible by a whole number and the prime number (just an outcome of the summation for any n - I suppose).

But this was the impetus. So, I have a series of eight right triangles with symbolic representations for the sides. For eg. One side is the prime - the hypotenuse may be e^i(theta)f(n) - and the other side is the summation of the prime.

So I’m looking for a pattern between the coefficients in the successive summation series of sequential primes. And then this is equal to an e^i(theta) type of function of n. The Pythagorean formula comes into play as well.

That function would spit out the prime as a function of n. But, like I said, it’s a spiral function - and it’s eight iterations long - and I’m no good with complex numbers or Euler’s formula.

Anyhow. Thanks for entertaining the thought.

Cheers. rat spit - First, I wanted to see if I could use geometry and induction to find the nth summation of any real number. And I successfully did this using triangles.

Just so I understand what you mean: what is the 4th summation of e? 1e + 2e + 3e + 4e = 10e? I simply mean the arithmetic summation of any number

https://wikimedia.org/api/rest_v1/media/math/render/svg/956e6e212a3c2b7a...

## Attach Image/Video?:

No  rat spit - And what’s interesting (and possibly trivial) is that the summation for the nth prime is divisible by a whole number and the prime number...

Yes, those two properties (C and D below) are true. Here is a quick and dirty handwaving proof:

1. n * (n + 1); will always been even (lets restrict n to natural numbers greater than 2). Because one of the factors will always be even, and the other factor will always be odd. The product of an even and odd is always even.
2. [n * (n + 1)] / 2 will always be a natural number. Because an even number will always be evenly divisible by 2.
3. [n * (n + 1)] / 2 a natural number, will always be evenly divisible by at least one whole number other than n (the number 1 always works).
4. [n * (n + 1)] / 2 will always be evenly divisible by n. This one is a little harder to see, but just imagine putting n into the denominator. Then cancel the n in the numerator and denominator, leaving (n + 1)/2. Since all primes are odd (except 2), n + 1 is always even, so we have an even number divided by 2 and that is sure to be a natural number (see part B). Right. So I’m asserting that there is a pattern among the multiple of the arithmetic summation of the prime which includes the prime but is not the prime “j”. It is defined by a spiral function [e^i(theta)]) where there is a repeating pattern of j1 to j8; j9 to j17; etcetera.

And if I had a picture of the geometry of the right triangles handy I would gladly post it.

But the main problem for me anyway, is using the Euler formula to arrive at the answer.

The e^i(theta)f(n) function runs along the hypotenuse of the right triangle. It is always equal to the non-prime multiple which is a multiple of the arithmetic summation of the prime value.

Damn. Those damn pictures are at my mom’s gathering dust. I hate going to my mom’s. I can’t be bothered. And the only way to explain it is with the picture.

But it’s like this a little bit.

e^i(theta)f(n)= cos theta + i sin theta

Is equivalent to

(Non-prime multiple of summation)^2 = prime^2 + summation^2 And the pattern repeats eight times before it resets.

And an inductive step is needed to flesh out the formula. This part is non-sensical:

(Non-prime multiple of summation)^2 = prime^2 + summation^2

Because the summation of the prime is always going to be larger than any of its multiples. In other words, Pythagorus doesn’t work here.

Which is why I’ve been trying to work with this identity:

e^i(theta)f(n)= cos theta + i sin theta

Or some combination of the two. rat spit - Which is why I’ve been trying to work with this identity:

e^i(theta)f(n)= cos theta + i sin theta

To be honest, I'm a little confused as to what you are doing beyond that hand-wavy proof part above, but this equation certainly got my attention. First off the notion is a little quacked, should that read:

1. e^(i * θ) * f(n) = cos(θ) + i * sin(θ)
2. or perhaps: e^[i * θ * f(n)] = cos(θ) + i * sin(θ)

Both versions of the equation make my skeptical alarm tingle, and here is why:

Clearly this is somehow based on Euler's famous equation: e^(i * θ) = cos(θ) + i * sin(θ)
But it seems you have just multiplied the left hand side of an Euler's famous equality by f(n); at least in option A above. And I'm assuming by f(n) you mean a function that when you give it a number (like say 4) it returns the 4th prime number (in this case 7). Meaning you just multiplied the left side of an equality by a natural number greater than 1, but you made no change to right hand side. As this seems to violate the rules of algebra, I am skeptical they are still equal. Yes. The rendering is sloppy. The f(n) belongs to the exponential. In fact there could be a g(n) in front of the e.

This e^i(theta) function is a repeating loop in the imaginary plane (as I’m sure you know). By adding additional functions I’m allowing for perturbations in the loop. Perturbations which I can’t presently define.

It’s quitting time for me. Thanks for the chat. Will be back at it tomorrow.

Cheers. rat spit - Which is why I’ve been trying to work with this identity:

e^[i * θ * f(n)] = cos(θ) + i * sin(θ) (***more explicit version substituted by Nyar***)

Again, I'm skeptical of this "identity". There are values of θ and certain prime numbers for which this "identity" doesn't seem to be true:

--------------------------------------------

• e^[i * θ * f(n)] = cos(θ) + i * sin(θ) | θ = π/2
• e^[i * π/2 * f(n)] = cos(π/2) + i * sin(π/2)
• e^[i * π/2 * f(n)] = 0 + i * 1
• e^[i * π/2 * f(n)] = i; I'll stop here because this smells bad.

--------------------------------------------

Some prime numbers substituted for f(n) make this equation false when θ = π/2.

f(3) = 5; works because:

• e^(i * π/2 * 5) =
• e^(i * 5π/2) =
• e^(i * [4π/2 + π/2]) =
• e^(i * [2π + π/2]) =
• e^(i * 2π)e^(i * π/2) =
• e^(i * π/2) = i

f(4) = 7 does NOT work because:

• e^(i * π/2 * 7) =
• e^(i * 7π/2) =
• e^(i * [4π/2 + 3π/2]) =
• e^(i * 2π)e^(i *3π/2]) =
• e^(i * 3π/2) = - i

Maybe there is something you're doing but have not explained (or was not understood by me) that protects you from the combinations of angles and primes where it doesn't work; but I recommend double-checking this "identity". Nope. Nothing missed. You’ve seemed to accomplish more with the whole endeavour than I have for the five years that this geometric representation has been staring back at me. rat spit - You’ve seemed to accomplish more with the whole endeavour than I have for the five years that this geometric representation has been staring back at me.

Trying to do stuff geometrically often takes a cleverness that most of us just don't have (I certainly don't have it). I mean what options do we have when we aren't clever enough? How exactly are we going to get more clever? Not really something you can just take a class on. If I could teach you to be more cleaver, I wouldn't; I'd teach myself first! Well, thank you? Assuming the geometry is a reflection of something real; I will take this as a compliment.

As a youngster, I spent many hours drawing. As I got older, I studied anatomy and became rather proficient at drawing the human form.

I was always entranced by M.C. Escher and I emulated his precision in my own drawings. Nothing that I did came close to his brilliancy, but I did acquire an artistic taste for geometry and symmetry.

With math, I was just good at it in high school and as an undergrad.

These doodles of these imaginary triangles are just one of a bunch of inspired “math” drawings.

But I digress. Maybe one day I’ll visit mom and search for a copy of it. I wouldn’t be able to duplicate it now. It’s a remnant of an inspired past time.

Cheers. (I think your clever. At least you can navigate your way around Euler’s formula! That’s top notch stuff!). Gave me a chance to dust off some cobwebs. Excellent! No “Fields Medal” in the near future for your efforts, I’m afraid. ;) From Breezy’s thread: A continuation of the search for the nth prime.

rat spit:

Let’s not fight. Okay? Let’s solve this nth prime.
Okay. A new approach.

e^(theta) is the hypotenuse - where (theta)= the summation series of prime “x” divided by prime x.

The opposite side of the triangle is the summation series of prime x.

The adjacent side of the triangle is prime x.

Now, this makes for some pretty steep looking right triangles as x approaches even 12, but maybe some adjustments to prime x will be found in the calculations.

So we have:

e^(theta)*2 = (prime x)^2 + (the summation of prime x)^2

Ie. the Pythagorean theorem. Inspired by:

e^(theta)i = cos theta + i sin theta;

For right triangles

rat spit - ...the summation series of prime “x”...

Nyar:

What do you mean by that exactly? For example, if we were discussing the 4th prime (x = 4); would the sum mentioned in the quote be the sum of the first 4 primes? (2 + 3 + 5 + 7 = 17)?

I hope not, because that would be a very bad thing to be in a formula for the nth prime.

rat spit:

No. No. Of course, that would be a blunder. I mean the arithmetic series summation for any given prime.

Eg. Prime x = 5, then series summation equals (1+2+3+4+5) = 15 and therefore (theta) equals 15/5 = 3

e^3*2 = [(some factor)*5]^2+ 15^2 I guess I'll move my post here too:
----------------------------------------------------------------------------------------------------------

rat spit: e^(theta)*2 = (prime x)^2 + (the summation of prime x)^2

I could clean that up considerably for you (by removing the summations and combining terms), but there is no point because I can already see some fatal problems:

1. The left hand side is an irrational number, while the right hand side is a rational number. Can an irrational number equal a rational number? Of course not. Your equation is false.
2. Presumably we start already knowing the value of x (if we want to know the 4th prime, we know x = 4). That leaves us with nothing to solve for. So there would be no way to extract the answer, even if the equation was true. That’s cool. I think it has potential though.

It relates The arithmetic summation of the prime, to the common divisor raised as a power to “e”.

I’ll start looking into it my self. Start exploring what that “factor” might be.

There’s also avenues for trigonometry here. Specifically sine - as the hypotenuse will always be larger than the opposite side.

But that might prove fatal too. The exponential will grow much too quickly compared to the arithmetic summation series.

Anyway. Thanks for the interest. Take care

- rat spit The first attempt was better as it basically quantized the distance between the primes; which would let you calculate the nth prime in a simple way. Unfortunately the primes are not quantized; so it didn't work. That is certainly the rational conclusion (no pun intended).

At 13, the end product starts running away pretty fast.

But I’ll slow it down.

And, despite your rational conclusion, I’m not willing to throw the baby out with the bath water just yet. I’ve got a trick up my sleeve that will slow that exponential down IN ITS TRACKS!

How about an irrational approximation of the nth prime?

Besides; if you don’t have useless hobbies, what are you going to do with your time? Smoke crack?

Hmm. I’ve never tried crack. https://youtu.be/uq0Z3pbmsr4

(Forgive the poor video quality).

## Pages

Donating = Loving Bringing you atheist articles and building active godless communities takes hundreds of hours and resources each month. If you find any joy or stimulation at Atheist Republic, please consider becoming a Supporting Member with a recurring monthly donation of your choosing, between a cup of tea and a good dinner. 