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

[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.

 

[a1call]

The following 183 digit prime was found using formulation using the Theorem 1, without scripting and programming.
Is that of any significance considering the method?
Are there any other formulas which can give comparable results without programming?

The number of digits is about a dozen less than the maximum of what the free version of Wolfram Alpha accepts.

268247424057311445389468276509855422892624146761442207989329055956776521156436821116123624436462260510842892838582894073662704750945426649505938377042214898386145890456554863200575291

http://www.wolframalpha.com/input/?...77042214898386145890456554863200575291+prime?Credits to Wolfram Alpha for doing the arithmetic.

Thank you for your time and replies.

 

[mfb]

What were the base numbers you used, which two numbers did you use to come to this difference?

The number is prime.

 

[a1call]

What were the base numbers you used, which two numbers did you use to come to this difference?

The number is prime.

I used a probable prime concept using Theorem 1 rather than a proven prime.
I will PM the exact expression shortly.

 

[micromass]

The following 183 digit prime was found using formulation using the Theorem 1, without scripting and programming.
Is that of any significance considering the method?
Are there any other formulas which can give comparable results without programming?

The number of digits is about a dozen less than the maximum of what the free version of Wolfram Alpha accepts.

268247424057311445389468276509855422892624146761442207989329055956776521156436821116123624436462260510842892838582894073662704750945426649505938377042214898386145890456554863200575291

http://www.wolframalpha.com/input/?i=268247424057311445389468276509855422892624146761442207989329055956776521156436821116123624436462260510842892838582894073662704750945426649505938377042214898386145890456554863200575291+prime?Credits to Wolfram Alpha for doing the arithmetic.

Thank you for your time and replies.

Please tell us in detail how you found this number, or tell us how to replicate this result.

 

[a1call]

Please tell us in detail how you found this number, or tell us how to replicate this result.

As I mentioned before this is based on prime candidacy and not proof so the sum does not converge to less than square of the largest prime or integer in factorial.

A few notes:

* This was an exercise to see the capabilities of the free version of Wolfram Alpha
* The free version of Wolfram Alpha can actually calculate much (much) larger prime candidates but the problem is you can't feed it back for the tool to see if it is a prime. The Pro version can input much larger numbers. So if anyone has the Pro account and comes up with larger primes using the Teorem 1, please feel free to post it here.
* I would have used multifactorials (which does not require knowing all the lower primes used) rather than primorials, but "off the shelf" Wolfram alpha does not support multifactorials higher than double factorials.
* Number of prime numbers below a number can be calculated, though I haven't bothered doing:

https://en.wikipedia.org/wiki/Prime_number#Number_of_prime_numbers

The point of posting the prime is to suggest that Theorem 1 might perhaps be of some value since it can come up with primes with relatively few trials for large numbers even without converging to less than the square of the largest prime. It is certainly more probable than Mersenne primes which in fact are quite rare. As pointed out on the other board there are other formulas that can give large prime candidates. But I would argue The Theorem 1 approaches will give much more probable primes than those.

* For the record I am still of the opinion that there is enough information in this thread for someone with better math skills than myself to come up with a mathematical expression evaluating to more than a billion digits and the proof that it is a prime and can probably fit all that in a single standard sheet of paper, I have not seen any arguments on the two boards or the PMs on them to convince me otherwise.

* To replicate or come up with other primes please adjust the 2 primorials in the example below to optimize for the closest sum to the square of the largest prime factor and largest number of digits. it took me more trials to come of with the free version input limitation than with the 1st prime.** here is the exact mathematical expression:

http://www.wolframalpha.com/input/?i=((+primorial+150))/(primorial+85)-(1*primorial+85)&f=1

 

[micromass]

http://www.wolframalpha.com/input/?i=((+primorial+150))/(primorial+85)-(1*primorial+85)&f=1

And you actually think you will find a billion digit prime number with this?

 

[a1call]

And you actually think you will find a billion digit prime number with this?

You asked me a question and I answered it. If you chose to ignore what I said, then there is no point in replying is there?

 

[micromass]

You asked me a question and I answered it. If you chose to ignore what I said, then there is no point in replying is there?

Well, I don't see the point of this thread anyway...

 

[Ryan_m_b]

Closed pending moderation

 

[mfb]

To check numbers with more digits, you can use tools like this. It can identify primes that size within less than a minute.

Anyway, it's not a method to find billion-digit primes.

Edit: Sorry, didn't see the previous post, the thread was still displayed as open.