The "one billion minus 999,994,000" digits prime number

[a1call]

Please see the attached screenshot along with the command documentation.
It takes less than 2 seconds.

You can try the command yourself with a free account.

[chalsall]

Originally Posted by a1call

Please see the attached screenshot along with the command documentation.

What you are forgetting is empirical time is different than computational time.

[a1call]

Which means it actually takes a fraction of a second on the server, right or am I missing something.

[chalsall]

Originally Posted by a1call

Which means it actually takes a fraction of a second on the server, right or am I missing something.

It means you are missing a lot!

Sure, in our modern age, we just "throw hardware at the problem". And that might make some sense. Machines and energy are cheap(ish). Programmers are expensive.

BUT... Some actually want to optimize the equations.

That also makes sense....

[science_man_88]

Originally Posted by a1call

Which means it actually takes a fraction of a second on the server, right or am I missing something.

I think what is being pointed out is that:

this code takes 4 milliseconds for this single computation isn't necessarily useful ( though I do that a lot myself) because without knowing how the time scales people won't be sure if it's worth putting in the time it would take for other inputs for example two inputs a and b=2*a;

if for input of b we double the time then the algorithm may be linear time complexity, if it quadruples the time it may be exponential, if b=a^2 and time doubles then maybe the algorithm may be logarithmic. same with number of operations if you say this algorithm takes 4 operations okay is that 4 additions, 4 multiplications, 4 divisions ( divisions are typically slow for computations unless they use a way of dividing that doesn't use much if any actual dividing). that and that it takes time to display an answer.

[danaj]

The point is that you're comparing two completely different operations.

PrimeQ is similar to Pari/GP's ispseudoprime, Perl/ntheory's is_prime, or mpz_prp's mpz_bpsw_prp (used by Python's gmpy 2.0). It runs very fast. It is a probable prime test. Nobody really knows what the Wolfram / Mathematica implementation really is (Pinch noted their "Lucas test" was not what the rest of the world calls a Lucas test and was strictly weaker than what BPSW should use, but that was 22 years ago). BPSW is great test, but I'm not sure how it applies here. It's meaningless in the EFF challenges. I have an old web page that does similar tests, though not factoring. It runs on the slow web host server rather than the browser, so the proof size is pretty limited.

The test you're running with alpertron is a proof. APR-CL I believe (but could be wrong). That would be similar to Pari/GP's isprime, mpz_aprcl's mpz_aprcle, or FLINT's new APRCL code (not in master yet). Comparable to the ECPP methods of Primo or Perl/ntheory's is_provable_prime. They take massively longer to run than the probable prime test. A certificate (ECPP, Pratt, etc.) would work for EFF, but you can't just give a general form number of 1M digits to Primo and expect it to ever produce something. Hence the idea of building up the certificate, which at least isn't loony with today's resources (I was going to say practical, but that's stretching it).

[a1call]

There is nothing in the documentation about the command being a probable prime test.
For the record none of these has anything to do with the EFF challenge. I think that can only be satisfied with mathematical proof and without calculating the the digits of the prime.

[danaj]

Originally Posted by a1call

There is nothing in the documentation about the command being a probable prime test.

Under "Implementation notes":

http://reference.wolfram.com/languag...tion.html#6849

It states that PrimeQ does trial division with small primes (typical for performance), then M-R bases 2 and 3, then a Lucas test. M-R base 2 plus a proper Lucas test makes the BPSW test. Adding base 3 is either to add more certainty over just BPSW, or (the cynical view) to mask an improper Lucas test.

It points out you need to use ProvablePrimeQ to get a proof.

[a1call]

Originally Posted by danaj

Under "Implementation notes":

http://reference.wolfram.com/languag...tion.html#6849

It states that PrimeQ does trial division with small primes (typical for performance), then M-R bases 2 and 3, then a Lucas test. M-R base 2 plus a proper Lucas test makes the BPSW test. Adding base 3 is either to add more certainty over just BPSW, or (the cynical view) to mask an improper Lucas test.

It points out you need to use ProvablePrimeQ to get a proof.

I stand corrected.
Thank you again for your insight danaj.

[a1call]

I tried the ProvablePrimeQ command it aborted after 1 minute. The online tool is still running with no end in sight.
My PARI/gp is not configured yet because of memory shortages on my desktop, but someone told me that the test took 8 minutes on a slow computer.

Can someone please let me know if the 2947digit integer that I posted is prime or not.

Thanks in advance.

[Batalov]

Originally Posted by a1call

...someone told me that the test took 8 minutes on a slow computer.

That someone also doesn't know how to do primality tests.

The 2947digit candidate can be tested with Primo in ~1 hour with 4-8 threads (surely not 8 minutes).
Get Primo and run the test.