Is there a formula for generating prime numbers and proving their primality?

[zinq]

"The original poster seems to be talking about something that sounds like proof that there are infinitely many primes.
If 2*3*5*7*...*p(n) is the product of the first n primes, then either there is a prime between [2*3*5*7*...*p(n-1)] and [2*3*5*7*...p(n)] or else [2*3*5*7*...*p(n)]+1 is a prime."

Actually, there is always a prime p satisfying

N < p ≤ 2N​

for any positive integer N. (This fact is called Bertrand's postulate, and its proof is trickier than one might guess. See https://en.wikipedia.org/wiki/Proof_of_Bertrand's_postulate.)

So, the first alternative in the quoted either-or statement always holds.

 

[zinq]

This thread has included several mentions of an "algebraic" formula for primes (or the nonexistence of such a formula).

I think it would be a good idea to be very precise about just what type of formula is being referred to, whether it's one that generates primes or one that cannot do so.

Obviously we can generate an infinite sequence of distinct primes with the evident formula P(n) for all n ≥ 1 as follows:

P(1) = 2;​

P(n+1) = the smallest prime factor of P(1) P(2) ... P(n) + 1.
​

But surely it is a more interesting formula that we're concerned with here.

 

[pbuk]

Hi,

The following is the routine that I have forwarded to the 2 people who have offered to assist me.

* Take any set S of consecutive positive primes starting from 2 and ending at some Pn.
* Write a code routine to try either random combinations, or ordered trial combinations of all of the above primes and generate a sum of the form z = a - b where a and b have no common prime factors
* a and b each, are multiplications of positive integer powers of any distinct and non empty subsets of A and B such that A + B = S
** Any sum z < Pn2 that your routine comes up with id's guaranteed to be a prime.

Here is a small integer example for clarification:
z = 13 x 112 - 72 x 5 x 3 x 2 = 103
Here S is the set of first consecutive primes from 2 to Pn = 13
A = {11,13}
B = {2,3,5,7}
Note: sets A and B do not need to be made of consecutive elements.

Against my better judgement, here's a counter-example:
S = {2, 3, 5, 7, 11, 13, 17, 19}
A = {2}, B = {3, 5, 7, 11, 13, 17, 19}
a = 2, b = 4,849,845
b - a = 4,849,843 = 43 x 167 x 450473

 

[a1call]

z < Pn²
The pasting dropped the superscript tags. In your example the sum should be less than 361.
There can not be any counter examples for z less than square of Pn.

 

[pbuk]

z < Pn²

That's quite a limitation - if I have consecutive primes up to Pn then testing ANY integer less than P(n)² for primality is trivial - or indeed generating every prime less than P(n)².

 

[a1call]

It is limiting it is true. However generating all consecutive primes is not a necessity. The theorem can be used for applications that does not require this. For example you can code your routine to use double factorial of a composite odd integer which can be evaluated formulaic. And then factor out many (not necessarily all) known primes to be added to the other side. If you do clever programming you sold be able to generate primes up to some range beyond which the sum would converge rarely. That's why this is not what I had/have in mind for very large primes.

 

[pbuk]

You would still need to do arithmetic O(P(n)!) in order to generate a prime O(P(n)²) so I think you would need to come up with a bit more than an assertion that you can overcome this by "doing clever programming" to demonstrate that there is anything interesting in your method.

 

[a1call]

Here is an example that can be proven is prime using the theorem that I posted. The only primes you need to generate it are 2 and 3

http://www.wolframalpha.com/input/?i=15!/(3*9!)-2^3*3^4

 

[mfb]

The statement is true, but it is as useful as Mills' formula: not at all.
The product of the first 46 prime numbers (all up to 200) has 82 decimal digits. Therefore, your numbers b and c would need at least 40 digits, and you have two find two numbers that are within 40000 (5 digits) of each other. That is an extremely inefficient calculation. And it would give primes smaller than 40000, which are useless.

To find a prime with 1 billion digits, you would need all primes up to 500 million digits. There are about 25 million of them, the product of all has several quadrillion digits (~10¹⁶) so b and c have a few quadrillion digits at least. Good luck handling those digits (they need several thousand TB to store them). For random products, the chance that the difference between two of them just has a billion digits is about 1 in 10^{several quadrillions}.

 

[a1call]

All that is true but I pointed that out already. Two points though.
First, the method has one thing going for it that the sum needs to be calculated to very (relatively) few significant digits. Long enough to establish relativity to the largest integer factor squared. For nearly 100% of the sums this would be 2 significant digits. The rare instances where the sum and square match in number of digits and more than 2 significant digits you can go a few digits more. This makes for a very efficient primality test.

Second, there is a way to make the sum converge with a much higher probability. What that way is though it's the $150k question. Which is the whole point of my staring these threads. At this point though I'm just posting to clarify any misconceptions of what I have posted before.
I don't expect any credible computing party to take me up with my offer.

 

[willem2]

To find a prime with 1 billion digits, you would need all primes up to 500 million digits. There are about 25 million of them

There are 25 million primes smaller than 500 million. There are about 10^500 / ln (10^500) ~ 8.6 * 10^496 primes with up to 500 million digits.
I don't think multiplying them all will ever be possible.

 

[mfb]

There are 25 million primes smaller than 500 million. There are about 10^500 / ln (10^500) ~ 8.6 * 10^496 primes with up to 500 million digits.
I don't think multiplying them all will ever be possible.

Oops, good point. The number of primes to multiply exceeds the number of particles in the universe by about 400 orders of magnitude.

First, the method has one thing going for it that the sum needs to be calculated to very (relatively) few significant digits.

Even a single digit is bad if you have to do it 10³⁵ times (for finding primes below 40000). That is not efficient.

Second, there is a way to make the sum converge with a much higher probability. What that way is though it's the $150k question.

Probably even more, it looks like several number theory questions would be related to that.
Differences between powers, for example.

Anyway, as willem's comment shows, not even a single multiplication is possible within the computing limits of the observable universe.

 

[mathwonk]

this is an interesting discussion and example of the varying uses of language. some people call a "formula" an expression with unknown coefficients that are merely proved to exist, even though no one knows what their values are. so the words "exhibit" and "prove to exist" are rather different. others think a formula must be a polynomial. anyway we all seem to enjoy piling onto someone who believes he/she has solved a problem we are sure is unsolved.

 

[aikismos]

Hi,
Since someone let the cat out of the bag (with good intentions no doubt) I might as well let it out properly and 1st hand.

Let the cat out of the bag? Nahhhh. More like whacked the bag against the refrigerator so everyone would know there's a cat inside (and from my perspective, I think the consensus is that it's questionable whether its a cat; maybe a small, toothless mouse?) That being said you might want to consider the scope of your project which is essentially to be the first to reach a prime of a size which is almost 100 times larger than the currently largest known prime.

* You haven't shared until now (as far as I can tell) for any form of peer review.
* You haven't really done a thorough analysis in terms of computational complexity.
* Your ambition is to try to build a non-distributed application to overtake an accomplished distributed effort with much vaster resources.
* Your recruiting methods consist of posting brief snippets with questionable assertions and gargantuan ambitions on the Internet.

I'm not saying your not going to be first to the billion-digit line, but if you do get there, it won't possibly be without ample help. Like science, we are are increasingly living in era of big-math! :D

 

[a1call]

There are 25 million primes smaller than 500 million. There are about 10^500 / ln (10^500) ~ 8.6 * 10^496 primes with up to 500 million digits.
I don't think multiplying them all will ever be possible.

A factorial (and by extension multifactorial) can be evaluated within a range formulaic using Sterling's formula. You don't need tho multiply all primes. The calculated ranges can be used to proof if a sum is prime.

 

[Vanadium 50]

not even a single multiplication is possible within the computing limits of the observable universe.

This is why I said he can't find a 25-digit prime, A 25 digit prime means P(n) = around 10^13, and we're dealing with 12 digit numbers. That means the products will take up about a terabyte, which means ~1000 seconds just to get them in and out of memory. That means the whole process will take 10^16 seconds, or of order a billion years. That's without the combinatorics problem with finding useful d's.

It's clear now that I was too generous - a 19 digit prime looks to be beyond this method. Primes that size can be found by guessing in less than a second.

 

[Vanadium 50]

Primes that size can be found by guessing in less than a second

1000000000000000003 is prime. (As is 1000000000000000009)

 

[willem2]

A factorial (and by extension multifactorial) can be evaluated within a range formulaic using Sterling's formula. You don't need tho multiply all primes. The calculated ranges can be used to proof if a sum is prime.

You still need to subtract two of those numbers to get your desired prime number. The maximum error to get that right is 0.5. Even if you use Sterlings formula, there's no room in the universe to store the result

 

[a1call]

You still need to subtract two of those numbers to get your desired prime number. The maximum error to get that right is 0.5. Even if you use Sterlings formula, there's no room in the universe to store the result

You do not need to evaluate the sum, factorial or the square to the last digit. Only to the significant digits to establish primality. Theoretically this can be done on a hand held calculator.

 

[Vanadium 50]

Theoretically this can be done on a hand held calculator.

Then why not do it?

You claim you have something revolutionary. Show us. Give us a tiny, tiny prime - say 50 or 100 digits - if you expect us to believe that you can find a billion digit prime.

 

[mfb]

A factorial (and by extension multifactorial) can be evaluated within a range formulaic using Sterling's formula. You don't need tho multiply all primes. The calculated ranges can be used to proof if a sum is prime.

It can be approximated, but you need an extremely precise result. Also, the formula doesn't work for the product of the first n primes, or subsets of it.

That means the products will take up about a terabyte, which means ~1000 seconds just to get them in and out of memory. That means the whole process will take 10^16 seconds, or of order a billion years.

Well, you can speed that up significantly. Make 10¹³ multiplications of 12-digit numbers, 5*10¹² multiplications of 24-digit numbers, ... so memory usage is only ld(10¹³)*10¹³*6 bytes or ~1000 TB.
The last multiplication step is the most elaborate one, but it can be done in O(n log n log log n). You don't need a supercomputer to do that in a year.

 

[a1call]

It can be approximated, but you need an extremely precise result. Also, the formula doesn't work for the product of the first n primes, or subsets of it.

* Doesn't 15!/7^2 Contain (is divisible by) all the positive prime numbers less than 15 excluding 7?
* Doesn't Sterling's formula evaluate an upper and lower bound for a factorial which is precise?
* Doesn't n^2 > precise-upper-bound-of-z conclude that n^2 > z ?

Thank you in advance.

 

[mfb]

Doesn't 15!/7^2 Contain (is divisible by) all the positive prime numbers less than 15 excluding 7?

Sure.

Doesn't Sterling's formula evaluate an upper and lower bound for a factorial which is precise?

It does, how does it help?

Doesn't n^2 > precise-upper-bound-of-z conclude that n^2 > z ?

Ýou are not interested in the rough number of the huge products, you need a tiny difference with reasonable precision. To see that the difference between two 1-million digits is a 20-digit number, you need a precision of at least 999980 digits.
The stirling formula has a relative error of about 1/(12n), so only the first 7 digits are correct. You can add a correction term to the formula to get 14 correct digits, and another correction term to this correction term to get about 20 correct digits. You'll need of the order of 1 million higher orders to get a result precise enough.

 

[a1call]

Thank you for the reply and thank you for complimenting my short comings.
The math is what it is. The question would be is that more efficient than multiplying 500 million integers?
Just noticed your number of posts is a very nice prime.
19001
ETA
"
If the exact values of large factorials are needed, they can be computed using arbitrary-precision arithmetic. Instead of doing the sequential multiplications [PLAIN]https://upload.wikimedia.org/math/4/e/9/4e950c2fb098b47dd67e63e9e671abb0.png, a program can partition the sequence into two parts, whose products are roughly the same size, and multiply them using a divide-and-conquer method. This is often more efficient.[8]

The asymptotically best efficiency is obtained by computing n! from its prime factorization. As documented by Peter Borwein, prime factorization allows n! to be computed in time O(n(log n log log n)2), provided that a fast multiplication algorithm is used (for example, the Schönhage–Strassen algorithm).[9] Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve.[10]
"

https://en.m.wikipedia.org/wiki/Factorial#Computation
Would any of these yield an exact but truncated value for factorial of around (10^500000000)!

Again the way I see it the sum needs to be calculated only to just number of significant digits to perform a size comparison to a truncated square value.
Am I missing something?
Thank you for your insights.

 

[mfb]

Would any of these yield an exact but truncated value for factorial of around (10^500000000)!

No, the number of digits you would have to compare exceeds the number of atoms in the universe by far.
You can get the first and last 20 digits of that number with a reasonable effort, but not the digit at place 10^(10^9). For the difference of two huge numbers to be small, all apart from the last few digits have to agree.

 

[a1call]

I see what you mean and cache see that you are right.
Thinking out loud here for a solution:
Say you need your sum to be less than 100.
Say yours sum elements (what is the equivalent termfor factors in a sum? ) are 4 digits long then you need at least 3 significant digits to establish primality
4
504$ - 503$ = 1$ < 100

So the only solution I can think of would be make the sum elements smaller.
So how about the practicality of summing billion digit integers truncated.
For the above example that it be something like:
8$- 6$ = 2$ < 100

ETA This is hypothetical and not based on my posted theorem and assumes hypothetically that there is a theorem that can prove a sum is prime for much smaller values than the sum of factorials. Such a thereon would state that the sum function is a prime if smaller than 10^10^10

Then the truncated summation of two, ten billion digit numbers that sum up to a truncated one billion digit integer would be practical and sufficient proof.
Wouldn't it?

 

[a1call]

Can't update my last post on a mobile's
Guess the term would be addend.
Wonder if it would be correct even if the element ous negative?

http://www.factmonster.com/ipka/A0881931.html

 

[mfb]

Summands.

Then the truncated summation of two, ten billion digit numbers that sum up to a truncated one billion digit integer would be practical and sufficient proof.
Wouldn't it?

Yes, but that is basically saying "suppose we have an algorithm that gives prime numbers with little effort, can we use this to generate prime numbers?"

As you can freely swap B and C, the sign doesn't matter, as you already indicated by taking the magnitude of the difference.

 

[a1call]

Thank you very much for putting up with my questions mfb.
just trying to grasp the problems with coming up with on billion+ prime.
At least in theory this is one possible way of representing and proving primality of such a number. As un-probable/worthless/dumb as it may seem, there seems to be no other suggested way of satisfying the EFF challenge.

 

[Vanadium 50]

As un-probable/worthless/dumb as it may seem, there seems to be no other suggested way of satisfying the EFF challenge.

You're right. It is, as you say, unprovable, worthless, and dumb. That you have failed does not mean every one else is destined to fail as well, and it does not mean your technique has more merit than other approaches - approaches that have gotten closer.