OEIS - A057732 : 2^n + 3

[ATH]

Using C and GMP the test for S0=14 matches the OEIS A057732 from n=4 (1 and 2 are trivial, n=3 fails) up to 11k so far, no false positive.

Using S0=(N-5)/2 the test matches OEIS from n=3 (1 trivial and n=2 fails) to 11k so far, no false positive.

Testing n: 17187, 17220, 17934, 20724, 22732, 25927, 31854, 33028, 35754, 38244, 39796, 40347, 55456, 58312 directly with both seeds gives a positive.

[T.Rex]

Originally Posted by Xyzzy

It sure has been a long time since you visited! We were worried about you!

Hi !
Life is various and weird. Some maths. Photography. Children living at 1000km and 10,000km from me. Girl-friend. Visiting daughter's country (Singapour and around, and soon Australia). Some weird but at the end not serious issue with my brain. Hiking. Mother having Alzeihmer. Death of mother. Mother's inheritance tasks and issues. Disease of girl-friend's father, and then death. Vacations. Painful work project.
However, I'm in good health, still able to climb 1000m in about 2 hours in Grenoble's mountains !

And chance and a bad night pushed me to look at these damned 2^n+3 numbers !

[T.Rex]

Hummm Looks like I have also a LLT-like algorithm for 2^n+5 prime numbers (with n odd).
See: https://oeis.org/A059242 .
It works fine for: 3, 5, 11, 47, 53, 141, 143, 191, 273, 341 . There is a gap till 16541, that should be reached by tomorrow.
Will give details later, probably in another thread.

[T.Rex]

And I'll have a look at (2^n+5)/3 with n even, too. If I have time.

[Batalov]

Tony, you can easily sieve for these forms, and if you do (for 2 minutes) then searching up to 16541 would take less than 1 minute...?

[paulunderwood]

Originally Posted by danaj

It takes ~7 minutes on my computer to get to 17934 using GMP and the simple method of running an ES BPSW test on each value.

perl -Mntheory=:all -MMath::GMPz -E 'for (1..1e9) { say if is_prob_prime(Math::GMPz->new(2)**$_+3) }'

Pari/GP simple method, using a relatively similar test (slightly less stringent), takes 20 minutes.

for(n=1,1e9,if(ispseudoprime(2^n+3),print1(n", ")))

It'd be interesting to compare the new test.

Also note that after 3k or so digits, gwnum starts being faster than GMP, and at 50k+ digits it is a lot faster. So OpenPFGW will probably be faster at the very large sizes regardless.

My hand-rolled GMP program of Tony's LLT with a "special mod reduction" took over 27 minutes to get to 17934, on 4770k at 3.25GHz.

[ATH]

The test is positive for all number in https://oeis.org/A057732 for both S0 values, and there is no counter example up to 23k for both S0 values.

[T.Rex]

OK. My PARI/gp code reached 20724, 22732, and 25927, with no false positive, which also are in A057732.
It is not useful to let PARI/gp continue searching, since a much faster implementation of LLT must be used in order to find a n greater than 685578 such that N=2^n+3 is a biggest PRP .

About comments dealing with performance about proving that a number is pseudo-prime and saying that other methods are more useful, I do not agree. I think that LLT-like algorithms are the fastest math ways for proving that a specific number N is Prime, when such an algorithm has been proven (like for Mersenne or Fermat numbers) - and when a specific LLT-code has be written for number N. And I think that LLT-like algorithms for PRPs may be proven true in the future, once Math people have develop new proof technics for proving LLT-like algorithms based on cycles instead of the tree.
Remember that 99,99% of Number Theory people ignore that the Pépin test used for proving that a Fermat number is prime is equivalent to a LLT test, and that at least 3 math proofs (including one by myself) have been provided for this. There is much more in LLT method than you think. Reread Édouard Lucas work and Hugh C. Williams book about Lucas' work.
See: http://www.ejpam.com/index.php/ejpam...iewArticle/245
See: http://arxiv.org/PS_cache/arxiv/pdf/...705.3664v1.pdf

[paulunderwood]

Originally Posted by paulunderwood

My hand-rolled GMP program of Tony's LLT with a "special mod reduction" took over 27 minutes to get to 17934, on 4770k at 3.25GHz.

Maybe if somebody could implement this with a simple GWNUM command line program and post the source, it might be useful and instructive to the community

[R.D. Silverman]

Originally Posted by paulunderwood

Maybe if somebody could implement this with a simple GWNUM command line program and post the source, it might be useful and instructive to the community

I doubt it.

This entire thread has been devoted to mindless numerology. I see no mathematical discussion at
all.

[danaj]

Originally Posted by paulunderwood

Maybe if somebody could implement this with a simple GWNUM command line program and post the source, it might be useful and instructive to the community

That sounds very useful. Heck, I want that so I can play around with other tests. Edit referencing RDS comment: useful to people implementing these things for running on computers. It would offer little in terms of math other than speed up simple checks.

From a performance testing standpoint, it's important to note that the tests I ran (is_prob_prime and ispseudoprime) have compositeness tests at the front, so of course they will be faster. If one really wanted to compare, either the L-L type test needs similar tests prepended or we need to run something like is_bpsw_prime that does nothing but the primality test. I did a very brief experiment with the former and got relatively similar times (I just did a simple mod with N in the loop, with no special optimizations). This of course ignores the certainty of the test -- the L-L type tests are (1) different, and (2) could someday be proven results.