PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Leyland primes

Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 400
ID: 1241833
Credit: 161,195,275
RAC: 1,009,600
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (134,736,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (747,401)
Message 142468 - Posted: 15 Aug 2020 | 6:36:42 UTC
Last modified: 15 Aug 2020 | 6:37:16 UTC

I generally don't like the idea of new subprojects, but if ever someone feels the absolute need to implement one, Leyland primes have a certain appeal.

They are of the form x^y + y^x and the biggest currently know one 8656^2929 + 2929^8656 has a mere 30008 digits.

According to PRP Records there are probable Leyland primes with up to 10^6 digits, but apparently it's hard to prove they are prime.

It might not be be easy to make it work with DC, the test for each number would have to be broken down into tasks. Maybe it doesn't make sense if they cannot be run parallel. But it irks me that 99% of new large primes are of a specific form just because those are relatively easy to prove their primality.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1502
ID: 306875
Credit: 33,913,566
RAC: 18,430
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,050,530)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 142470 - Posted: 15 Aug 2020 | 7:26:50 UTC

Yes, also see the activity at https://www.mersenneforum.org/forumdisplay.php?f=110. /JeppeSN

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 400
ID: 1241833
Credit: 161,195,275
RAC: 1,009,600
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (134,736,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (747,401)
Message 142485 - Posted: 16 Aug 2020 | 5:48:15 UTC

Ok, thanks. I was wondering where the currently known ones originated from...

Profile DaveProject donor
Avatar
Send message
Joined: 13 Feb 12
Posts: 2887
ID: 130544
Credit: 1,104,351,402
RAC: 1,269,710
Found 2 primes in the 2018 Tour de PrimesFound 1 prime in the 2020 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (6,042,688)Cullen LLR Turquoise: Earned 5,000,000 credits (6,019,794)ESP LLR Turquoise: Earned 5,000,000 credits (6,001,628)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (6,008,214)PPS LLR Turquoise: Earned 5,000,000 credits (6,300,000)PSP LLR Turquoise: Earned 5,000,000 credits (6,030,578)SoB LLR Turquoise: Earned 5,000,000 credits (9,306,239)SR5 LLR Turquoise: Earned 5,000,000 credits (5,502,937)SGS LLR Turquoise: Earned 5,000,000 credits (5,111,114)TRP LLR Turquoise: Earned 5,000,000 credits (5,504,122)Woodall LLR Turquoise: Earned 5,000,000 credits (5,516,672)321 Sieve (suspended) Jade: Earned 10,000,000 credits (10,003,334)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (268,250)Generalized Cullen/Woodall Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,502)PPS Sieve Double Silver: Earned 200,000,000 credits (306,996,970)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,133)TRP Sieve (suspended) Jade: Earned 10,000,000 credits (10,000,970)AP 26/27 Double Silver: Earned 200,000,000 credits (200,128,500)WW Double Bronze: Earned 100,000,000 credits (130,256,000)GFN Double Bronze: Earned 100,000,000 credits (159,374,772)PSA Double Silver: Earned 200,000,000 credits (200,000,001)
Message 142491 - Posted: 16 Aug 2020 | 10:40:02 UTC

Thought they came from Leyland in Lancashure.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1502
ID: 306875
Credit: 33,913,566
RAC: 18,430
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Jade: Earned 10,000,000 credits (12,050,530)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)WW Turquoise: Earned 5,000,000 credits (9,640,000)GFN Amethyst: Earned 1,000,000 credits (1,707,013)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 142493 - Posted: 16 Aug 2020 | 11:28:23 UTC - in response to Message 142491.
Last modified: 16 Aug 2020 | 11:28:40 UTC

Thought they came from Leyland in Lancashure.

The surname of Paul Leyland (after whom the numbers are named) likely comes from the toponym Leyland, Lancashire, England. /JeppeSN

Profile GellyProject donor
Volunteer tester
Avatar
Send message
Joined: 13 Nov 16
Posts: 46
ID: 468732
Credit: 1,957,120,148
RAC: 4,058,719
Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de Primes321 LLR Bronze: Earned 10,000 credits (38,954)ESP LLR Gold: Earned 500,000 credits (942,185)PPS LLR Double Silver: Earned 200,000,000 credits (284,953,062)PSP LLR Silver: Earned 100,000 credits (489,641)SoB LLR Jade: Earned 10,000,000 credits (12,960,428)SR5 LLR Jade: Earned 10,000,000 credits (10,694,695)SGS LLR Gold: Earned 500,000 credits (563,819)TRP LLR Jade: Earned 10,000,000 credits (12,592,743)321 Sieve (suspended) Silver: Earned 100,000 credits (395,205)PPS Sieve Double Silver: Earned 200,000,000 credits (229,814,554)TRP Sieve (suspended) Gold: Earned 500,000 credits (669,191)AP 26/27 Sapphire: Earned 20,000,000 credits (25,547,717)WW Double Amethyst: Earned 1,000,000,000 credits (1,294,848,000)GFN Emerald: Earned 50,000,000 credits (79,577,076)PSA Ruby: Earned 2,000,000 credits (3,025,234)
Message 142565 - Posted: 17 Aug 2020 | 21:07:36 UTC - in response to Message 142468.
Last modified: 17 Aug 2020 | 21:07:58 UTC

I generally don't like the idea of new subprojects, but if ever someone feels the absolute need to implement one, Leyland primes have a certain appeal.

They are of the form x^y + y^x and the biggest currently know one 8656^2929 + 2929^8656 has a mere 30008 digits.

According to PRP Records there are probable Leyland primes with up to 10^6 digits, but apparently it's hard to prove they are prime.

It might not be be easy to make it work with DC, the test for each number would have to be broken down into tasks. Maybe it doesn't make sense if they cannot be run parallel. But it irks me that 99% of new large primes are of a specific form just because those are relatively easy to prove their primality.


It's definitely out of character for PrimeGrid to pick up a subproject that cannot prove the primes they are testing, as all of the current and past projects are either sieves or for provable primes.

The reason Leyland primes aren't helpful in terms of primality proving is that you don't tend to know a lot about the factorization of P-1 or P+1, which is used in many of the primality proofs for very large primes. You can use general primality proving techniques, such as ECPP, but those top out at about 40k digits at the moment (although there are stirrings of 50k digits in the next 5 years)

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 400
ID: 1241833
Credit: 161,195,275
RAC: 1,009,600
321 LLR Amethyst: Earned 1,000,000 credits (1,058,073)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Amethyst: Earned 1,000,000 credits (1,093,381)Generalized Cullen/Woodall LLR Amethyst: Earned 1,000,000 credits (1,148,593)PPS LLR Amethyst: Earned 1,000,000 credits (1,225,852)PSP LLR Amethyst: Earned 1,000,000 credits (1,248,861)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Amethyst: Earned 1,000,000 credits (1,060,324)SGS LLR Amethyst: Earned 1,000,000 credits (1,108,160)TRP LLR Amethyst: Earned 1,000,000 credits (1,039,866)Woodall LLR Amethyst: Earned 1,000,000 credits (1,129,385)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)WW Double Bronze: Earned 100,000,000 credits (134,736,000)GFN Turquoise: Earned 5,000,000 credits (7,149,778)PSA Gold: Earned 500,000 credits (747,401)
Message 142583 - Posted: 18 Aug 2020 | 14:31:29 UTC - in response to Message 142491.
Last modified: 18 Aug 2020 | 14:35:56 UTC

Thought they came from Leyland in Lancashure.
Thanks, apparently that's exactly where they originate from.

ou can use general primality proving techniques, such as ECPP, but those top out at about 40k digits at the moment (although there are stirrings of 50k digits in the next 5 years)
I didn't know primality proving got that hard once there are no special techniques available. I also read that Leyland primes have their use especially for being hard to test for primality.

Is there a possibility doing ECPP via distributed computing? I only found "Also ECPP has never been truly exposed to distributed computing" in this mersenneforum thread.

Profile GellyProject donor
Volunteer tester
Avatar
Send message
Joined: 13 Nov 16
Posts: 46
ID: 468732
Credit: 1,957,120,148
RAC: 4,058,719
Discovered 2 mega primesFound 1 prime in the 2018 Tour de PrimesFound 2 primes in the 2020 Tour de PrimesFound 2 primes in the 2021 Tour de Primes321 LLR Bronze: Earned 10,000 credits (38,954)ESP LLR Gold: Earned 500,000 credits (942,185)PPS LLR Double Silver: Earned 200,000,000 credits (284,953,062)PSP LLR Silver: Earned 100,000 credits (489,641)SoB LLR Jade: Earned 10,000,000 credits (12,960,428)SR5 LLR Jade: Earned 10,000,000 credits (10,694,695)SGS LLR Gold: Earned 500,000 credits (563,819)TRP LLR Jade: Earned 10,000,000 credits (12,592,743)321 Sieve (suspended) Silver: Earned 100,000 credits (395,205)PPS Sieve Double Silver: Earned 200,000,000 credits (229,814,554)TRP Sieve (suspended) Gold: Earned 500,000 credits (669,191)AP 26/27 Sapphire: Earned 20,000,000 credits (25,547,717)WW Double Amethyst: Earned 1,000,000,000 credits (1,294,848,000)GFN Emerald: Earned 50,000,000 credits (79,577,076)PSA Ruby: Earned 2,000,000 credits (3,025,234)
Message 142605 - Posted: 20 Aug 2020 | 6:19:38 UTC - in response to Message 142583.


Is there a possibility doing ECPP via distributed computing? I only found "Also ECPP has never been truly exposed to distributed computing" in this mersenneforum thread.


I'm not an expert on ECPP, but from the work I've done and what I've seen, it's definitely a possibility. In 2005, they were using multiple computers in tandem for fastECPP, although definitely a far cry from distributed computing.

The way the main stage of ECPP works is it essentially connects the large prime to a small prime through a bunch of intermediate primes with elliptic curves that have special properties. It's essentially a random walk, hoping to hit on an equation that provides a factorization that you can work with, and many times Primo will end up backtracking if it doesn't like the current prime it's working on. This stage would likely be difficult to distribute well, but with enough distribution, maybe "ok" is good enough.

The second stage is a lot easier to split up and lends itself much better to distribution, as it's just taking all the equations to connect the primes in stage one and factorizing them, AFAIK.

Again, I'm no expert on ECPP, either mathematically or programmatically, and considering the maelstrom of ECC patents and Primo being closed source, it's hard to blame me. Perhaps we could change that for the better if we got enough people booked up on elliptic curves looking into distributed computing - it may be possible to blow past the current limits of ECPP due to it being single system.

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1221
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 142624 - Posted: 20 Aug 2020 | 18:56:28 UTC

Numbers of this form are notoriously hard to sieve efficiently. I know because I wrote xyyxsieve and nobody has pointed out a better algorithm than the one I'm using. The most efficient way I know to sieve requires a large amount of memory. For example I was looking at the range 30001 <= x <= 40000, 2 <= y < 40000. It took nearly 24 GB of memory to start sieving the range. The memory requirement is reduced to less than 5 GB at p=1e5, but there are still nearly 10,000,000 terms left in the range. It will take many weeks for a single core to sieve this range to p=1e10. This is because it has to compute x^y (mod p) and y^x (mod p) for all terms. There is some efficiency gained by computing x^y (mod p) for all y (for that x) and also for y^x (mod p) for all x (for that y), but it requires a lot of memory. There might be ways to statistically choose better algorithms to compute all x^y (mod p) for a single x, but I don't expect it to be much faster. The program is more efficient for larger ranges of x and y. This is because it is faster to compute x^y (mod p) for a single x and 2 <= y < 40000 than to compute once for 2 <= y < 20000 and against for 20000 <= y < 40000.

Because of the memory requirements using the GPU is pretty much out of the question. Granted I have a slower GPU at my disposal, but this sieve was actually slower with the GPU than without it. AVX512 could help quite a bit, but I don't have an AVX512 CPU at my disposal.

As for the sieving upper bound, it is very likely to be less than 1e11 for that range and 100 cores against it could probably complete the testing of that range within a few weeks.

It would probably be better to sieve a large range (let's say x <= 100000 and y < 100000) until the number of remaining terms is small enough to merge the results.

Post to thread

Message boards : General discussion : Leyland primes

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 3.64, 3.45, 3.42
Generated 18 May 2021 | 2:10:51 UTC