mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-03-29, 14:35   #100
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

998510 Posts
Cool

Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)
Batalov is offline   Reply With Quote
Old 2018-03-29, 14:53   #101
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·1,523 Posts
Default

Quote:
Originally Posted by Batalov View Post
Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)
Congratulations!

How many candidates for a(15) were sieved out?

BTW, it's another "interesting anomaly" that

a(4) = a(3)^2 and a(14) = a(13)^2.
Dr Sardonicus is online now   Reply With Quote
Old 2018-03-29, 16:11   #102
axn
 
axn's Avatar
 
Jun 2003

34·67 Posts
Default

Quote:
Originally Posted by Batalov View Post
Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)
Hmmm... Unfortunately, we can't really rule out s/w issues with regular double check. BTW, does LLR, P95 & PFGW produce comparable residues on these type of numbers?. Perhaps a Gerbicz Error Check implementation for non base-2 PRP could be made. It will be much slower (50%?) but atleast could be used to spot check.
axn is online now   Reply With Quote
Old 2018-03-29, 19:32   #103
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

234018 Posts
Default

Here is my eval of what usually happens in all three tools.
This is a special form. In LLR there is an input ABC template ABC ($a*$b^$c$d)/$e; in P95, PRP=1,b,n,1,"2", and PFGW understands the ABC form as well as recognizes the special form at parse stage.

All three tools have adapted over time to do the following on it:
  • the main exponentiation loop is done over mod (b^n+1) (not general mod! therefore, fast!)
  • the last residue is folded mod (b^n+1)/e and compared to 1 (this is done using giants)

I am tempted to modify the source for this special case e=2, because giant mod is not needed, just compare two values (1 or (b^n+1)/2+1 -these should look just fine in limbs of b how they are likely internally stored) -- (or multiply by 2 and compare to 2). ...Thus avoiding giants.

Another test that I did in limited range: use -a1, -a2 in pfgw (or similar in other tools); this is not a little bit, but a lot slower, because the special arrangement of exactly 32K b-limbs is destroyed.

Let's see what happens. I'll tinker with this on the weekends.
Batalov is offline   Reply With Quote
Old 2018-03-29, 23:49   #104
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2668 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
To appear as A301738 (until it is approved, see History to see the proposed versions). /JeppeSN
Now approved.

I will contribute the new sequence quite soon.

Serge Batalov, good work on A275530.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2018-03-31, 02:05   #105
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·1,997 Posts
Default

Quote:
Originally Posted by Batalov View Post
Perhaps, so. I was concerned that there may be some giant_mod bug or a carry count bug similar to one a few years ago.

Anyway, found one ... at a(15) = 220221 (!!)
Found a(16), too
Batalov is offline   Reply With Quote
Old 2018-03-31, 03:03   #106
axn
 
axn's Avatar
 
Jun 2003

34×67 Posts
Default

Quote:
Originally Posted by Batalov View Post
Found a(16), too
How are you sieving these suckers?
axn is online now   Reply With Quote
Old 2018-03-31, 04:35   #107
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

234018 Posts
Default

These are too small to sieve, -- PFGW's ~45-bit pre-factoring looks fine to me.
It would be a different story for m=17, but I am taking a break for now.
Batalov is offline   Reply With Quote
Old 2018-03-31, 13:15   #108
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,523 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Congratulations!
BTW, it's another "interesting anomaly" that

a(4) = a(3)^2 and a(14) = a(13)^2.
!sdrawkcab ti tog I ,tibbangaD

I should have said, a(13) = a(14)^2 and a(3) = a(4)^2
Dr Sardonicus is online now   Reply With Quote
Old 2018-04-01, 17:07   #109
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×1,997 Posts
Default

And A275530(17) is now found!

(11559^131072+1)/2 is a 532535-digit PRP.

Now it is time to revisit the a(15) with a different FFT size throughout.
Batalov is offline   Reply With Quote
Old 2018-04-01, 17:51   #110
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10FE16 Posts
Default

Quote:
Originally Posted by Batalov View Post
And A275530(17) is now found!

(11559^131072+1)/2 is a 532535-digit PRP.

Now it is time to revisit the a(15) with a different FFT size throughout.
Congrats Serge. Here is my Lucas test of it:

Code:
time ./pfgw64 -k -f0 -od -q"(11559^131072+1)/2" | ../../coding/gwnum/lucasPRP - 1 11559 131072 1
                             
Lucas testing on x^2 - 4*x + 1 ...
Is Lucas PRP!

real	20m21.514s
user	48m14.480s
sys	3m17.668s
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is there a prime of the form...... PawnProver44 Miscellaneous Math 9 2016-03-19 22:11
OEIS A071580: Smallest prime of the form k*a(n-1)*a(n-2)*...*a(1)+1 arbooker And now for something completely different 14 2015-05-22 23:18
Smallest prime with a digit sum of 911 Stargate38 Puzzles 6 2014-09-29 14:18
Smallest floor of k for cullen prime Citrix Prime Cullen Prime 12 2007-04-26 19:52
Smallest ten-million-digit prime Heck Factoring 9 2004-10-28 11:34

All times are UTC. The time now is 14:23.


Sun Nov 27 14:23:15 UTC 2022 up 101 days, 11:51, 1 user, load averages: 1.16, 1.13, 1.06

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.

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