Prime Numbers formula

  • A
  • Thread starter a1call
  • Start date
  • #51
34,976
11,164
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 1013 multiplications of 12-digit numbers, 5*1012 multiplications of 24-digit numbers, ... so memory usage is only ld(1013)*1013*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.
 
  • #52
85
5
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.
 
  • #53
34,976
11,164
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.
 
  • #54
85
5
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, [Broken] 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.
 
Last edited by a moderator:
  • #55
34,976
11,164
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.
 
  • #56
85
5
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?
 
Last edited:
  • #58
34,976
11,164
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.
 
  • #59
85
5
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.
 
  • #60
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,703
8,894
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.
 
  • #61
85
5
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.
 
  • #62
34,976
11,164
What were the base numbers you used, which two numbers did you use to come to this difference?

The number is prime.
 
  • #63
85
5
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.
 
  • #64
22,089
3,291
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.
 
  • #65
85
5
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
 
  • #67
85
5
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?
 
  • #68
22,089
3,291
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...
 
  • #69
Ryan_m_b
Staff Emeritus
Science Advisor
5,844
712
Closed pending moderation
 
  • #70
34,976
11,164
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.
 
Last edited:

Related Threads on Prime Numbers formula

  • Last Post
Replies
6
Views
15K
  • Last Post
Replies
4
Views
838
Replies
7
Views
582
Replies
10
Views
18K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
5
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
15
Views
7K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
1
Views
642
Top