Prime Formula

Fair enough; I'll show you the proof in a bit. Keep the thread from dying some way. For now I'll just give the hint "Wilson's theorem"...

>[eqn]p_n = \sum_{m=1}^{2^n} [\cdots][/eqn]

lol

>there are formulas for the n'th prime (and I guess OP posted on) but they don't give algorithms that are nore efficient that brude forcing some sieve (roughly, just eliminating the numbers going down from the square root of m for not being prime

Those don't count because if you have to use a Sieve then what you have is not an expression, but an algorithm.

Finding an expression of any kind that produces all prime numbers would be a big break through. Just imagine how further that shit would push analytic number theory.
> It's easy to see that for n=1 doesn't even give an integer.

That is impossible. OP is using the floor function around everything, so everything must be an integer there.

>What is the floor function?

I liek primes.
I have been having some thoughts (though I am sure they are not original)
>1) all numbers are actually composed of some pi product of primes.
>The distinction between even and odd is the inclusion of the prime factor 2 (which is a shitty prime number).
>we can define the "auxiliary numbers" as those numbers that do not contain a prime factor of 2.
>all integer are then generated by the group operations {do nothing, times by 2} on the axillary numbers.

>prime structure relates deeply to the core of number theory

further rather than see oddness or eveness. we have found a more general category:

set of auxhillary's wrt x in the set of primes.

So one could define "3-odd" which is the prime numbers that do not have 3 as a prime factor, and p-odd in general.

Trivial

as an edit the operations are in fact: {times by 1, times by 2} (the first two"""prime numbers""")

duh. but its the trivial things which are the most fundamental mein d00den.

>tfw too intelligent to read 500 page books on how to add in different ways

give us the latex code

wolframalpha.com/input/?i=((m*((m-1)!+1) / m ))/((m-1)!+1)

I've just checked with Mathematica for n up to 10 and it indeed works

Rocco?

Both of those nasty fractions with factorial reduce to 1. Why not just write that

Some bored person without enough to do having 'fun' with Word equation generator. Both sets of square brackets reduce to 1 for all 'm' and 'k'.

>wolframalpha.com/input/?i=((m*((m-1)!+1) / m ))/((m-1)!+1)
pay closer attention to the use of floors. That fraction will either be 0 or 1. It is 1 if and only if m divides (m-1)!+1

mathworld.wolfram.com/PrimeFormulas.html
I think they already beat you to it op lol

>Trips confirm the legitimacy of this formula.

gib proofs

or can you not even do strong induction?

DO NOT post your proof! I repeat, DO NOT post your proof here. Publish that shit and get it peer reviewed first. Chances are, It'll get stolen and published by someone here if you post it here.

Nah but seriously post your proof here.

You can trust us. We are all bros here on Veeky Forums

t. Number Theory grad student, already 10 years behind on his dissertation

Ok I'm gonna test it with 1399, the 222nd prime number.

If it doesn't work

fuck you.

not the poster btw

good luck bruh

Right. I'm wasting valuable time talking to a bunch of gais about a dubious formula rather than working on conjectures and shit

What's 2^222?

>want to calculate 1000th prime number
>ok cool what's 2^1000?

Easy. It's 1 followed by 1000 zeroes in base two.

Is OPee onto something?
I can't figure out.

>2 (which is a shitty prime number)
Fuck you.

There's nothing to check unless you provide proof.

>nobel
>math

Absolutely masterful.

WILSON'S THEOREM
I
L
S
O
N
'
S

T
H
E
O
R
E
M

Use it, fags.

This

>He thinks the one most important formula in Mathematics (if it even exists) will be posted here on Veeky Forums before it's published.

tb.h it wouldn't suprise me

Well, I'd need some kind of more efficient way to evaluate that sum. As it is, it takes fucking ages to evaluate for n > 10. So nobody else has to type this piece of shit in:

p[n_] := Sum[m Floor[m Floor[(Factorial[m - 1] + 1)/m]/(Factorial[m - 1] + 1)] Floor[1 / (1 + Abs[n + 1 - Sum[Floor[k Floor[(Factorial[k - 1] + 1)/k]/(Factorial[k - 1] + 1)], {k, 1, m}]])], {m, 1, 2^n}]

It definitely works for n < 12:

p(1) = 2
p(2) = 3
p(3) = 5
p(4) = 7
p(5) = 11
p(6) = 13
p(7) = 17
p(8) = 19
p(9) = 23
p(10) = 29
p(11) = 31
p(12) = Lost patience

Really interested in where this formula comes from.

Why is everyone acting like there doesn't already exist a formula that generates primes? (few seconds on google)

There's one as an example in wolfram alpha that uses the same idea that OP was talking about. But they say that these formulas are inefficient aka useless, but everyone here is acting like it's something worthy of a fields medal.

Here you can check for yourself it even mentions Wilson's theorem. And as you can see it looks similar to what op posted in certain aspects.

mathworld.wolfram.com/PrimeFormulas.html

>Floor[m Floor[(Factorial[m - 1] + 1)/m]/(Factorial[m - 1] + 1)]
See that shit? USE FUCKING WILSON'S THEOREM and observe that it is equal to 1 iff m is prime or m=1, otherwise it's zero.
Now look at that sum over k. Look's familiar, doesn't it? Well, that's because it's nothing else than pi(m)+1, where pi(x) is the prime counting function. Now, 1 over n+1-(pi(m)+1) is less than 1 except when n=pi(m), and that is the case for p_n

me too

Calm your tits, for fuck's sake.

well user?

times by m, divide by m, for every m up to bla

>There exist a variety of formulas for either producing the nth prime as a function of n or taking on only prime values. However, all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge of the primes ahead of time in order to use the formula (Dudley 1969; Ribenboim 1996, p. 186). There also exist simple prime-generating polynomials that generate only primes for the first (possibly large) number of integer values.
From your link. OP's formula is an explicit one, which would be new.

It should be relatively easy to do a small mathlab script the function and see weather or not it works.

An user already gave a Mathematica code for it, but it's really slow. It took me ~9 minutes to calculate p(12) = 37, though admittedly my CPU is not very fast.

also from the link

>Explicit formulas exist for the nth prime both as a function of n and in terms of the primes 2, ..., p_(n-1) (Hardy and Wright 1979, pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41), a number of which are given below. However, it should again be emphasized that these formulas are extremely inefficient, and in many (if not all) cases, simply performing an efficient sieving would yield the primes much more quickly and efficiently.

OPs formula IS basically a sieving algorithm for primes. It's just very inefficient and you happen to be able to write it down as a closed form function. When calculating a value of that function, you internally basically sieve, just very inefficiently because you use very large factorials to determine whether or not a number is prime.

Yeah, it would seem like user's formula is just counting up to 2^n and adding one if a number is prime, but some fancy symbols, as said by

isPrime(n):
for i = 2 to n - 1:
if n mod i == 0
return false
next i
end for
return true

fields medal please

I'm just wondering what makes that formula special as opposed to the one that they show as an example.

[math]p_n=1+\sum_1^{2^n} \lfloor \lfloor\frac{n}{\sum_j^{m}\lfloor cos^2[ \pi \frac{(j-1)!+1}{j}]\rfloor}\rfloor^{1/n}\rfloor[/math]

or even
[math]\pi(n)=-1+\sum_{j=3}^n[(j-2)!-j\lfloor\frac{(j-2)!}{j}\rfloor][/math]

[math]\pi(n)=-1+\sum_{j=3}^n[(j-2)!-j\lfloor\frac{(j-2)!}{j}\rfloor][/math]

Reminds me of this guy, he leaked elite australian spy secrets to /pol/ or /b/ or something and all he got was
>fake and gay
>saged

ibtimes.co.uk/spy-agency-whistle-blower-posted-top-secret-report-Veeky Forums-users-called-it-fake-gay-1514330

>to sqrt(n)
ftfy

But you only check if n is prime, you don't generate the n'th prime. This can be done in polynomial time
en.wikipedia.org/wiki/Primality_test

Here's the lazy infinite list in Haskell containing all primes:

ps = 2 : [i | i 0 | p p^2

I figured it out guys

[eqn]p_n = \sum_{i=1}^\infty i \cdot \mathbb{1}_{\mbox{i is the nth prime}}[/eqn]

screenshot this for my noble prize in number theory

I can see it happening. Never underestimate the autism.

Hey, I actually used a formula just like this to generate all the primes (there is still a lot more you can do to make it more compact and efficient though). It's true that formulae such as these are known to exist, it's actually quite trivial to piece together 'something' which works... The difficulty is in making this formulae efficient. That said a starting point is something worth having.

Here are some things to ponder/use:

Instead of taking the sum to 2^n you can use ceiling(n(ln(n)+ln(ln(n))), which is smaller than 2^n and hence you'll get less 'zeros' to add near the end of your sum (not sure that makes it more efficient).

Also, the reason I needed the formula was to find simpler expressions for the Reiman Zeta function (as Euler defined it: product of (1/(1-1/(p(n)^s))) over all n). Where p(n) is the nth prime. Maybe you could actually put your formula to use to find a simpler formula (one which does not involve an infinite product nor sum) for the Reiman Zeta function. That would be neat.

That said I think it's a fun and even useful exercise to come up with formula like these (hence why I also spent my time using Wilson's theorem to come up with similar formula).

I'll also suggest you incorporate this if you think you could do something with it, especially if you know complex analysis well enough.

I guess I should add that to use ceiling(n(ln(n)+ln(ln(n)))) you need n>=4. Or something like this...

>closed form function
neither dependent-range summations nor the floor function would have been included in the definition of closed forms when I went to university. how times change.

What about higher values?

> But you only check if n is prime, you don't generate the n'th prime.

Well then if you want the nth prime, start with the ith prime, for i < n, and then keep running the algorithm on incrementally larger integers until you find enough primes to get to the nth prime. Duh.

Yep. This is spot on for me.

Though I still think it's very useful finding the simplest version of this basic idea. Maybe one could find a means of transforming the sum into a nice, tidy formula. Or a means of using some such sum in finding a similar version of Euler's product formula for the Reimann zeta function which doesn't involve an infinite sum or product.

>dat false equivalency

>2^n
TOP KEK
That shit must be 1000000x slower than bruteforcing it

no doubt, the complexity of this function is immense
i've been sitting and waiting a good 10 minutes for the 20th prime now

What software are you using?

My CUDA implementation is able to generate it in seconds. After the 86th prime, my GPU is running out of memory.

>this
>O-notoation

[math] \pi(n)=-1+ \sum_{j=3}^n[(j-2)!-j \lfloor \frac{(j-2)!}{j} \rfloor][/math]

holy shit i did it
[math]p(N)=curl www.di-mgt.com.au/primes1000.txt -s | sed 'Nq;d'
[/math]

that was bait... right?