A Theoretical (vs. Proficient/Practical) Deterministic Primality Test

[danaj]

I get the idea that it can be useful to have a theorem even if it isn't computationally attractive. The arguments against can be either that it is easily seen from number theory or that it isn't computationally useful. I'm not making the first, but perhaps others are hinting at it?

On the small side, we don't have "some tabulated list of primes" that are used as known primes. The computation time required to make just all the tiny 64-bit primes is immense but feasible. The storage requirements are possible, though be prepared to spend over 100 million USD for the storage array. The time taken to say "known via BPSW test" is 1 millisecond for a 64-bit prime (I just timed it on my 2012 computer). Half that time for 32-bit primes.

To give us a better idea of how your method improves as the size increases, let's take a scenario where we want to use your method to prove a number prime that is 20,000 digits. Primo can do these but they are awfully time consuming. Assume for the sake of argument that we have some already proven primes of 20001, 20002, 20003, ... digits. Based on factordb, assume we have 1 or 2 of each. Can you describe the steps? It looks like we take the factorial of the square root, so our first step is taking a factorial of a 10,000 digit number. Does this seem practical?

[a1call]

Originally Posted by danaj

I get the idea that it can be useful to have a theorem even if it isn't computationally attractive. The arguments against can be either that it is easily seen from number theory or that it isn't computationally useful. I'm not making the first, but perhaps others are hinting at it?

I agree that it can be easily seen from the number theory.
Still I think the concept is perhaps novel which was my motivation behind the post to see if indeed it was. I'm still interested to see a reference to this concept elsewhere.

Originally Posted by danaj

On the small side, we don't have "some tabulated list of primes" that are used as known primes. The computation time required to make just all the tiny 64-bit primes is immense but feasible. The storage requirements are possible, though be prepared to spend over 100 million USD for the storage array. The time taken to say "known via BPSW test" is 1 millisecond for a 64-bit prime (I just timed it on my 2012 computer). Half that time for 32-bit primes.

I was aware that very small primes where easier to compute than store, but thought there was a range higher up where consecutive primes were stored.
False assumption I guess, but that was the rational behind the smallest consecutive known primes. But not having such a list doesn't really invalidates the scenario I proposed in my last post.

Originally Posted by danaj

Does this seem practical?

Not really, hence the title of this thread.

However, the impracticality is based on the inability to compute, store and operate on (very) large factorials. But for this particular application the factorials will have to be of the same order as the known large primes. If the primes don't need to be calculated to the last digit, then perhaps neither do the factorials. Think upper and lower significant digits required for establishing the constraints required and doing the subtraction (Computations involved, I know).

[axn]

Originally Posted by a1call

Would that be computationally equivalent, more, or less taxing?

Your loop is computing GCD. Might as well use built-in function.

Originally Posted by a1call

I think primorial will definitely be more taxing for ranges even with tables rather than Sterling's theorem algos.

What Sterling's theorem algo? Your program was merely doing trial division in a roundabout way.

[a1call]

Originally Posted by axn

Your loop is computing GCD. Might as well use built-in function.



What Sterling's theorem algo? Your program was merely doing trial division in a roundabout way.

Apologies for the typo, I think WDP uses Stirling's approximation at least in part to calculate the factorial. I am pretty sure it does not actually multiply all the integers to get the factorial. No such approximation can be done for the primorial. So it should take longer to calculate the equivalent primorial than the factorial.
http://mathworld.wolfram.com/Stirlin...oximation.html

The reference was not to the GCD vs. the Mod loop.
I learned about the GCD command for the first time from your post.
Thank you.

ETA but as pointed out by CRGreathouse smaller fsctorials are faster to operate on. The 2 factors will have to be weighed in.

[a1call]

Here is a 712707 decimal digits prime that is guaranteed to be prime using my suggested concept and proved by my infamous Theorem 1.

150209! - (119878*5^1019645-1)

https://primes.utm.edu/primes/page.php?id=114317

WDP code:

n=150209;

p0=119878*5^1019645-1                                        ;
p1=n     !-p0;
Print["p1<n^2 is ", p1<n^2 ]
Print[IntegerLength[p1]]

Published page for the code:

https://www.wolframcloud.com/objects...1-a8e1e58be5b3

[axn]

Originally Posted by a1call

I think WDP uses Stirling's approximation at least in part to calculate the factorial. I am pretty sure it does not actually multiply all the integers to get the factorial. No such approximation can be done for the primorial. So it should take longer to calculate the equivalent primorial than the factorial.
http://mathworld.wolfram.com/Stirlin...oximation.html

Stirling's approximation is just that -- an approximation. And approximate value is not useful for calculating the exact value. So, no, Stirling's approximation is not relevant.

There are more efficient algorithms for calculating a factorial than naively multiplying 1,2,3,..,n one after the other. However, a primorial can be done even faster, in all cases.

You should time both factorial calculation and primorial calculation and compare which is faster (instead of guessing).

[LaurV]

Originally Posted by a1call

Here is a 712707 decimal digits prime that is guaranteed to be prime using my suggested concept and proved by my infamous Theorem 1.

150209! - (119878*5^1019645-1)

https://primes.utm.edu/primes/page.php?id=114317

WDP code:

n=150209;

p0=119878*5^1019645-1                                        ;
p1=n     !-p0;
Print["p1<n^2 is ", p1<n^2 ]
Print[IntegerLength[p1]]

Published page for the code:

https://www.wolframcloud.com/objects...1-a8e1e58be5b3

Huh?? WTF did you smoke? If n is a 6 digit number, its square is 12 digits number. How a zillion digit number can be smaller than n^2?
With that n, and theorem 1, you can mostly prove that a number smaller than 22,562,743,681 is prime. Not larger.

[a1call]

Originally Posted by LaurV

Huh?? WTF did you smoke? If n is a 6 digit number, its square is 12 digits number. How a zillion digit number can be smaller than n^2?
With that n, and theorem 1, you can mostly prove that a number smaller than 22,562,743,681 is prime. Not larger.

You are right,
false alarm
I can't figure out why the code gives true for the condition though.
Do you?

[a1call]

Negative value, forgot to put the absolute value function.
My apologies.

[danaj]

Re factorial complexity, I recommend looking at the various implementations and data from Peter Luschny. It's a bit unorganized but there's a lot of info there. GMP uses his Swing method for mpz_fac_ui since version 5.1, No idea what WDP uses, but there are so many other variables that it probably doesn't matter.

Primorials can be sped up a lot (e.g. 10x or more) using product trees. GMP added this optimization in 5.2 to mpz_primorial_ui. I wrote my own simple version that just uses the standard mpz API.

axn is definitely right that benchmarking is a good idea, especially as you're using unusual software (WDP). With GMP, primorials are faster (e.g. 4.4s vs. 40.2s for 10^8# vs. 10^8!). It's nice for testing the hypothesis that we think one *ought* to be faster than the other (and especially when we have opposite hypotheses as we do here).

[CRGreathouse]

Originally Posted by a1call

I was aware that very small primes where easier to compute than store, but thought there was a range higher up where consecutive primes were stored.
False assumption I guess

It's pretty easy to see that this could not be the case if you look at the storage requirements.

Originally Posted by a1call

However, the impracticality is based on the inability to compute, store and operate on (very) large factorials. But for this particular application the factorials will have to be of the same order as the known large primes. If the primes don't need to be calculated to the last digit, then perhaps neither do the factorials. Think upper and lower significant digits required for establishing the constraints required and doing the subtraction

This definitely doesn't work. You'll need to know every digit to tell if the number is prime.