mersenneforum.org OEIS - A057732 : 2^n + 3
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2015-08-27, 10:47 #1 T.Rex     Feb 2004 France 16378 Posts OEIS - A057732 : 2^n + 3 Hi, I think that I have a LLT-like method for finding OEIS A057732 PRPs. Now, up to 31th number (8739), I have the same results that OEIS shows. (A057732 numbers are primes and PRPs numbers of the form: 2^n + 3. See: https://oeis.org/A057732) I'd like to know which method has been used for finding the big A057732 numbers, like the top ones: 479844 (prime) and 685578 (PRP). Thx
 2015-08-27, 10:58 #2 paulunderwood     Sep 2002 Database er0rr 5·829 Posts I don't think you should have said "479844 (prime)" Here are the known gigantic PRPs, some well within the reach of ECPP in a reasonable amount of time. My guess is that these PRPs were found with NewPGen+PFGW. Last fiddled with by paulunderwood on 2015-08-27 at 11:15
 2015-08-27, 12:15 #3 T.Rex     Feb 2004 France 32×103 Posts Yes. reading again the OEIS A057732 page, it seems clear now that the biggest exponents give PRPs. However, the name of this OEIS is bad: "Numbers n such that 2^n + 3 is prime." I should have had a look at OEISA057733 which shows that biggest n giving a prime for 2^n+3 is 228. Since my method finds all 2^n+3 primes in A057733 plus n = 390, 784, 1110, 1704, 2008, 2139, 2191, 2367, 2370, 4002, 4060, 4062, 4552, 5547, 8739 , with no false positive and no false negative, I think that my method is interesting. NewPGen+PFGW ? OK. I no more know how to use them. Last fiddled with by T.Rex on 2015-08-27 at 12:48
 2015-08-27, 12:45 #4 T.Rex     Feb 2004 France 11100111112 Posts LLT-like method based on Cycles My method is based on the LLT (Lucas-Lehmer Test), as usual. It makes use of cycles, since the DiGraph x^2-2 modulo (2^n+3) primes does no generate a tree, but only cycles with small trees attached to the cycles. And it makes uses of 2 possible seeds S0. The general formula is: N=2^n+3 ; s(0)=S0 ; s(i+1)=s(i)^2-2 modulo N. If s(j) == S0 then N is prime. In our case, I've found 2 different seeds S0: 14 and (N-5)/2, but with a different number of steps j for each and depending if n is even or odd. In short, in the PARI/gp language, there are 2 sets of 2 formulae, which both (seem to) give all prime N=2^n+3 : 1) Seed S0 = 14 - n odd: n-1 steps for(i=1,100000,n=2*i+1;N=2^n+3;x=14;for(j=1,n-1,x=Mod(x^2-2,N));if(x==14,print(n," Prime"))) - n even: n-2 steps for(i=1,100000,n=2*i ;N=2^n+3;x=14;for(j=1,n-2,x=Mod(x^2-2,N));if(x==14,print(n," Prime"))) 2) Seed S0 = (N-5)/2 - n odd: n-1 steps for(i=1,100000,n=2*i+1;N=2^n+3;S=(N-5)/2;x=S;for(j=1,n-1,x=Mod(x^2-2,N));if(x==S,print(n," Prime"))) - n even: n-1 steps for(i=1,100000,n=2*i ;N=2^n+3;S=(N-5)/2;x=S;for(j=1,n-1,x=Mod(x^2-2,N));if(x==S,print(n," Prime"))) Probably that second case is simpler, since the number of steps is the same for both n odd and n even, and thus there is only 1 case. If you copy and paste the formulae into gp, you'll have the PRPs. And, since we have now a new method for finding PRPs for 2^n+3, these PRPs are more close to be prime ! ;) We just lack a proof ! Anyway, if Jean Pené could have a look and see if he can implement this PRP test easily, that would generate interesting BIG PRPs. Last fiddled with by T.Rex on 2015-08-27 at 12:54
 2015-08-27, 12:58 #5 T.Rex     Feb 2004 France 92710 Posts ..., 17187, 17220, 17934 My testing is still running, and my PARI/gp code has just found: 17187, 17220, and 17934. Still no missing n such that 2^n+3 is PRP and still no false positive. (still done with first set of formulae) Sure that PARI/gp is too slow. Maybe someone can implement the algorithm is some C-coded LLT program. Last fiddled with by T.Rex on 2015-08-27 at 12:59
 2015-08-27, 13:00 #6 paulunderwood     Sep 2002 Database er0rr 10000001100012 Posts GMP might be quicker -- it depends on programming C Last fiddled with by paulunderwood on 2015-08-27 at 13:02
 2015-08-27, 13:28 #7 T.Rex     Feb 2004 France 32×103 Posts OK. Wait and see if someone is interested in coding this. Probably that someone would like to find new big PRPs ! ;)
 2015-08-27, 13:40 #8 paulunderwood     Sep 2002 Database er0rr 414510 Posts As for finding new big PRPs, NewPGen+PFGW/LLR is the way to go as it will use George's libraries. Your LLT offers little speed gain over a base 3 Fermat PRP test. When I get a spare hour I will hack some GMP to get your LLT running
 2015-08-27, 13:51 #9 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 16158 Posts 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. Code: 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. Code: 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.
2015-08-27, 13:58   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by T.Rex Sure that PARI/gp is too slow. Maybe someone can implement the algorithm is some C-coded LLT program.
that may be true but there's a lot of possible small improvements in theory that I've been told about over the years instead of 2*i replace it with i<<1, instead of 2^n replace with 1<<n, instead of x^2 use sqr(x) or maybe even use the sqr function outside the Mod and subtract two after that ( or Mod your original value and then do the math in a way that carries it through without having to use Mod again. instead of using things like 1,n-1 use 2,n and since it's iterative other than a number you want to print you can do things in reverse with a step of -1 in a forstep. edit: the outer loop can potentially broken down with PARI/gp's new parallel parfor and grouping by number of threads in theory ( though I suck at that part). edit2: of course you can also delay printing by concatenating into a vector and printing ( or returning) only once.

Last fiddled with by science_man_88 on 2015-08-27 at 14:53

2015-08-27, 14:00   #11
Xyzzy

Aug 2002

2·4,229 Posts

Quote:
 Originally Posted by T.Rex Hi, I think that I have a LLT-like method for finding OEIS A057732 PRPs.
It sure has been a long time since you visited! We were worried about you!

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post lidocorc Information & Answers 1 2016-12-11 07:26 T.Rex Miscellaneous Math 38 2015-09-05 16:14 T.Rex Miscellaneous Math 7 2015-08-28 18:04 science_man_88 Miscellaneous Math 11 2011-05-18 15:04

All times are UTC. The time now is 05:01.

Thu May 26 05:01:23 UTC 2022 up 42 days, 3:02, 1 user, load averages: 1.20, 1.23, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔