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 : Proth Prime Search : Algebraically factorizable Proth prime candidates

Author Message
Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131173 - Posted: 17 Jul 2019 | 11:05:03 UTC

As an example, is there currently a PPS workunit for 343*2^2799186 + 1 loaded?

Not sure if such candidates are removed by the sieve, or removed "manually".

/JeppeSN

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 13046
ID: 53948
Credit: 202,912,378
RAC: 88,420
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (9,112,157)PSP LLR Turquoise: Earned 5,000,000 credits (5,065,592)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,014,138)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,552,316)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (66,792,810)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 131176 - Posted: 17 Jul 2019 | 11:31:33 UTC - in response to Message 131173.

As an example, is there currently a PPS workunit for 343*2^2799186 + 1 loaded?

Not sure if such candidates are removed by the sieve, or removed "manually".

/JeppeSN


There is not. PPS is currently loaded to n=2.8M and that candidate is not in there.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131177 - Posted: 17 Jul 2019 | 11:52:09 UTC - in response to Message 131176.


There is not. PPS is currently loaded to n=2.8M and that candidate is not in there.

That is good. I tried to come up with an example where there seems to be no small factor (which a sieve would certainly find). Not sure what the sieving level is?

The reason why 343*2^2799186 + 1 is composite, is that:

X^3 + 1 = (X + 1)*(X^2 - X + 1)

and k=343 is a cube (=7^3) and n=2799186 is a multiple of three (=933062*3), so therefore

343*2^2799186 + 1 = 7^3*2^(933062*3) + 1 = (7*2^933062)^3 + 1

so it is covered by the factorization of X^3 + 1 that I mentioned (substitute X=7*2^933062).

Now I see that the smallest factor of my example is 141,554,883,787. Do we sieve so deeply?

/JeppeSN

mackerelProject donor
Volunteer tester
Avatar
Send message
Joined: 2 Oct 08
Posts: 2247
ID: 29980
Credit: 351,961,193
RAC: 358,010
Discovered 2 mega primesEliminated 1 conjecture "k"Found 3 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 5 primes in the 2019 Tour de Primes321 LLR Turquoise: Earned 5,000,000 credits (8,774,878)Cullen LLR Turquoise: Earned 5,000,000 credits (5,149,818)ESP LLR Turquoise: Earned 5,000,000 credits (6,454,573)Generalized Cullen/Woodall LLR Turquoise: Earned 5,000,000 credits (5,122,074)PPS LLR Emerald: Earned 50,000,000 credits (58,493,179)PSP LLR Jade: Earned 10,000,000 credits (14,997,908)SoB LLR Jade: Earned 10,000,000 credits (17,319,914)SR5 LLR Jade: Earned 10,000,000 credits (18,479,395)SGS LLR Turquoise: Earned 5,000,000 credits (6,702,766)TPS LLR (retired) Bronze: Earned 10,000 credits (34,130)TRP LLR Jade: Earned 10,000,000 credits (15,154,737)Woodall LLR Turquoise: Earned 5,000,000 credits (5,715,464)321 Sieve Turquoise: Earned 5,000,000 credits (8,483,125)Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,383,853)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,626,419)PPS Sieve Emerald: Earned 50,000,000 credits (74,140,875)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,293,882)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,012,757)AP 26/27 Sapphire: Earned 20,000,000 credits (21,918,894)GFN Sapphire: Earned 20,000,000 credits (48,764,647)PSA Ruby: Earned 2,000,000 credits (2,939,755)
Message 131179 - Posted: 17 Jul 2019 | 12:11:08 UTC - in response to Message 131177.

Now I see that the smallest factor of my example is 141,554,883,787. Do we sieve so deeply?

If I'm reading the link below right, we're way, way past that.
http://www.primegrid.com/stats_pps_sieve.php

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 13046
ID: 53948
Credit: 202,912,378
RAC: 88,420
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (9,112,157)PSP LLR Turquoise: Earned 5,000,000 credits (5,065,592)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,014,138)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,552,316)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (66,792,810)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 131180 - Posted: 17 Jul 2019 | 12:15:37 UTC - in response to Message 131179.
Last modified: 17 Jul 2019 | 12:16:57 UTC

Now I see that the smallest factor of my example is 141,554,883,787. Do we sieve so deeply?

If I'm reading the link below right, we're way, way past that.
http://www.primegrid.com/stats_pps_sieve.php


Yes, over a million times deeper than that. Your factor is in the G's and the sieving was done in the P's.

EXCEPT...

The sieving you're looking at is for a higher N range than these candidates. I'm not sure what these were sieved to, but it was probably lower. But still, much higher than your factor.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131181 - Posted: 17 Jul 2019 | 12:27:22 UTC - in response to Message 131180.

Now I see that the smallest factor of my example is 141,554,883,787. Do we sieve so deeply?

If I'm reading the link below right, we're way, way past that.
http://www.primegrid.com/stats_pps_sieve.php


Yes, over a million times deeper than that. Your factor is in the G's and the sieving was done in the P's.

EXCEPT...

The sieving you're looking at is for a higher N range than these candidates. I'm not sure what these were sieved to, but it was probably lower. But still, much higher than your factor.


You are right! My example was not interesting, then.

I could also ask more broadly, do we have any candidates with k=343 where n is divisible by three? Maybe n=2798940, or something else.

My primitive loops will take (too) long to exclude the possibility that { k=343, n=2798940 } has a small factor (in the G's, T's or P's) as well.

/JeppeSN

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 892
ID: 107307
Credit: 869,756,415
RAC: 778,110
Discovered 1 mega prime321 LLR Ruby: Earned 2,000,000 credits (2,671,514)Cullen LLR Turquoise: Earned 5,000,000 credits (5,031,868)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,995,446)PPS LLR Ruby: Earned 2,000,000 credits (3,246,903)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (42,470,293)SR5 LLR Jade: Earned 10,000,000 credits (10,987,079)SGS LLR Ruby: Earned 2,000,000 credits (2,069,865)TRP LLR Ruby: Earned 2,000,000 credits (2,150,717)Woodall LLR Ruby: Earned 2,000,000 credits (3,444,961)321 Sieve Turquoise: Earned 5,000,000 credits (6,009,197)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (51,712,607)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Sapphire: Earned 20,000,000 credits (31,496,305)PSA Double Gold: Earned 500,000,000 credits (654,228,826)
Message 131182 - Posted: 17 Jul 2019 | 13:14:53 UTC - in response to Message 131181.
Last modified: 18 Jul 2019 | 5:11:42 UTC

PPS3M (n=2M-2.999999M) was sieved to p=100P.

SELECT COUNT(*) FROM llr WHERE project="PPS" and k=343 and n mod 3 = 0; +----------+ | count(*) | +----------+ | 0 | +----------+

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131186 - Posted: 17 Jul 2019 | 16:22:42 UTC - in response to Message 131182.

PPS3M (n=2-2.999999) was sieved to p=100P.

SELECT COUNT(*) FROM llr WHERE project="PPS" and k=343 and n mod 3 = 0; +----------+ | count(*) | +----------+ | 0 | +----------+


That convinces me there must be "something" ensuring these candidates are removed before LLR is run on them.

If you want, you can generalize your query to:
SELECT * FROM llr WHERE project IN ( "PPS", "PPSE", "PPS-Mega" ) -- do correct the project names if needed AND ( -- cubes k IN ( 27, 125, 343, 729, 1331, 2197, 3375, 4913, 6859, 9261 ) AND n MOD 3 = 0 OR -- fifth powers k IN ( 243, 3125 ) AND n MOD 5 = 0 OR -- seventh powers k IN ( 2187 ) AND n MOD 7 = 0 )
to be absolutely sure.

/JeppeSN

Profile Michael GoetzProject donor
Volunteer moderator
Project administrator
Project scientist
Avatar
Send message
Joined: 21 Jan 10
Posts: 13046
ID: 53948
Credit: 202,912,378
RAC: 88,420
The "Shut up already!" badge:  This loud mouth has mansplained on the forums over 10 thousand times!  Sheesh!!!Discovered the World's First GFN-19 prime!!!Discovered 1 mega primeFound 1 prime in the 2018 Tour de PrimesFound 1 prime in the 2019 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,822,730)Cullen LLR Ruby: Earned 2,000,000 credits (2,005,249)ESP LLR Turquoise: Earned 5,000,000 credits (5,009,577)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,145,754)PPS LLR Turquoise: Earned 5,000,000 credits (9,112,157)PSP LLR Turquoise: Earned 5,000,000 credits (5,065,592)SoB LLR Sapphire: Earned 20,000,000 credits (34,221,148)SR5 LLR Turquoise: Earned 5,000,000 credits (8,293,415)SGS LLR Ruby: Earned 2,000,000 credits (2,014,138)TRP LLR Ruby: Earned 2,000,000 credits (2,737,347)Woodall LLR Ruby: Earned 2,000,000 credits (2,195,123)321 Sieve Turquoise: Earned 5,000,000 credits (5,552,316)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,170,256)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,059,304)PPS Sieve Sapphire: Earned 20,000,000 credits (20,110,788)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Amethyst: Earned 1,000,000 credits (1,035,522)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,051,121)AP 26/27 Jade: Earned 10,000,000 credits (10,114,260)GFN Emerald: Earned 50,000,000 credits (66,792,810)PSA Jade: Earned 10,000,000 credits (12,404,447)
Message 131189 - Posted: 17 Jul 2019 | 17:33:27 UTC - in response to Message 131186.

PPS3M (n=2-2.999999) was sieved to p=100P.

SELECT COUNT(*) FROM llr WHERE project="PPS" and k=343 and n mod 3 = 0; +----------+ | count(*) | +----------+ | 0 | +----------+


That convinces me there must be "something" ensuring these candidates are removed before LLR is run on them.

If you want, you can generalize your query to:
SELECT * FROM llr WHERE project IN ( "PPS", "PPSE", "PPS-Mega" ) -- do correct the project names if needed AND ( -- cubes k IN ( 27, 125, 343, 729, 1331, 2197, 3375, 4913, 6859, 9261 ) AND n MOD 3 = 0 OR -- fifth powers k IN ( 243, 3125 ) AND n MOD 5 = 0 OR -- seventh powers k IN ( 2187 ) AND n MOD 7 = 0 )
to be absolutely sure.

/JeppeSN


All of those come back 0, but that table isn't the entire sieve table.
____________
Please do not PM me with support questions. Ask on the forums instead. Thank you!

My lucky number is 75898524288+1

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131195 - Posted: 17 Jul 2019 | 20:09:17 UTC - in response to Message 131189.

All of those come back 0, but that table isn't the entire sieve table.

Even when we look only at currently loaded work, or similar, there should be some cases where the k is an odd power (like y^3) and n is the relevant multiple (like z*3) and where no "small" factor (less than 100 Peta) exists. So since they are not in that database table, I am confident we do not run unnecessary LLR test on these. /JeppeSN

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 892
ID: 107307
Credit: 869,756,415
RAC: 778,110
Discovered 1 mega prime321 LLR Ruby: Earned 2,000,000 credits (2,671,514)Cullen LLR Turquoise: Earned 5,000,000 credits (5,031,868)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,995,446)PPS LLR Ruby: Earned 2,000,000 credits (3,246,903)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (42,470,293)SR5 LLR Jade: Earned 10,000,000 credits (10,987,079)SGS LLR Ruby: Earned 2,000,000 credits (2,069,865)TRP LLR Ruby: Earned 2,000,000 credits (2,150,717)Woodall LLR Ruby: Earned 2,000,000 credits (3,444,961)321 Sieve Turquoise: Earned 5,000,000 credits (6,009,197)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (51,712,607)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Sapphire: Earned 20,000,000 credits (31,496,305)PSA Double Gold: Earned 500,000,000 credits (654,228,826)
Message 131203 - Posted: 18 Jul 2019 | 0:03:25 UTC - in response to Message 131186.
Last modified: 18 Jul 2019 | 0:03:42 UTC

-- cubes
k IN ( 27, 125, 343, 729, 1331, 2197, 3375, 4913, 6859, 9261 ) AND n MOD 3 = 0
OR
-- fifth powers
k IN ( 243, 3125 ) AND n MOD 5 = 0
OR
-- seventh powers
k IN ( 2187 ) AND n MOD 7 = 0
)[/pre]to be absolutely sure.

/JeppeSN


In the earliest sieve file I have (p=10T), the k values 27, 125, 2197, 4913 and 6859 have no n mod 3 = 0 entries in them. One of the early sieving programs must have taken care of them.

Likewise k=3125 has no n mod 5 = 0 entries in it

On July 2, 2015 algebraic factors were applied for k=243, 343, 729, 1331, 2187, 3375 and 9261 on all PPS sieves 0-12M.

Algebraic factors were also applied for k=625. I don't remember why this works, but for example I have that:
25*2^5500069-5*2^2750035+1 is a factor of 625*2^11000138+1

The messages that instigated these algebraic factors being applied were probably on Lennart's PST message board server (now gone). I certainly didn't think of this myself. But that's why there aren't any candidates left that meet those conditions.

Ravi Fernando
Project administrator
Project scientist
Send message
Joined: 21 Mar 19
Posts: 44
ID: 1108183
Credit: 4,133,139
RAC: 8,336
321 LLR Silver: Earned 100,000 credits (224,754)ESP LLR Bronze: Earned 10,000 credits (16,570)PPS LLR Gold: Earned 500,000 credits (788,215)PSP LLR Bronze: Earned 10,000 credits (26,371)SoB LLR Silver: Earned 100,000 credits (183,524)SR5 LLR Bronze: Earned 10,000 credits (11,183)SGS LLR Bronze: Earned 10,000 credits (43,147)TRP LLR Bronze: Earned 10,000 credits (72,462)321 Sieve Ruby: Earned 2,000,000 credits (2,692,032)AP 26/27 Bronze: Earned 10,000 credits (72,774)
Message 131204 - Posted: 18 Jul 2019 | 0:38:49 UTC - in response to Message 131203.
Last modified: 18 Jul 2019 | 0:41:04 UTC


In the earliest sieve file I have (p=10T), the k values 27, 125, 2197, 4913 and 6859 have no n mod 3 = 0 entries in them. One of the early sieving programs must have taken care of them.

Those values of k are congruent to 6 mod 7, so k * 2^n + 1 will be divisible by 7 whenever n is divisible by 3.

Likewise k=3125 has no n mod 5 = 0 entries in it

These are divisible by either 3 (when n is even) or 11 (when n is 5 mod 10).

Algebraic factors were also applied for k=625. I don't remember why this works, but for example I have that:
25*2^5500069-5*2^2750035+1 is a factor of 625*2^11000138+1

This is an example of the aurifeuillean factorization 4x^4 + 1 = (2x^2 - 2x + 1)(2x^2 + 2x + 1), which rules out all candidates where k is a fourth power and n is 2 mod 4. So hopefully these candidates were removed for k = 81, 2401, and 6561 as well.

JimBProject donor
Volunteer moderator
Project administrator
Project developer
Send message
Joined: 4 Aug 11
Posts: 892
ID: 107307
Credit: 869,756,415
RAC: 778,110
Discovered 1 mega prime321 LLR Ruby: Earned 2,000,000 credits (2,671,514)Cullen LLR Turquoise: Earned 5,000,000 credits (5,031,868)ESP LLR Turquoise: Earned 5,000,000 credits (5,064,082)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (4,995,446)PPS LLR Ruby: Earned 2,000,000 credits (3,246,903)PSP LLR Turquoise: Earned 5,000,000 credits (5,013,650)SoB LLR Sapphire: Earned 20,000,000 credits (42,470,293)SR5 LLR Jade: Earned 10,000,000 credits (10,987,079)SGS LLR Ruby: Earned 2,000,000 credits (2,069,865)TRP LLR Ruby: Earned 2,000,000 credits (2,150,717)Woodall LLR Ruby: Earned 2,000,000 credits (3,444,961)321 Sieve Turquoise: Earned 5,000,000 credits (6,009,197)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (4,002,919)Generalized Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (20,005,451)PPS Sieve Emerald: Earned 50,000,000 credits (51,712,607)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,341,676)TRP Sieve (suspended) Ruby: Earned 2,000,000 credits (2,070,804)AP 26/27 Jade: Earned 10,000,000 credits (10,742,251)GFN Sapphire: Earned 20,000,000 credits (31,496,305)PSA Double Gold: Earned 500,000,000 credits (654,228,826)
Message 131207 - Posted: 18 Jul 2019 | 5:01:12 UTC - in response to Message 131204.

So hopefully these candidates were removed for k = 81, 2401, and 6561 as well.

While I cannot pinpoint when they were removed, I can tell you there aren't any candidates with k in (81, 2401, 6561) where n mod 4 = 2. I suspect they were sieved out for some other reason, hence my list of algebraic factors (which was produced from the current sieve at that time as it's too short to be every possible candidate) didn't need to list those.

Ravi Fernando
Project administrator
Project scientist
Send message
Joined: 21 Mar 19
Posts: 44
ID: 1108183
Credit: 4,133,139
RAC: 8,336
321 LLR Silver: Earned 100,000 credits (224,754)ESP LLR Bronze: Earned 10,000 credits (16,570)PPS LLR Gold: Earned 500,000 credits (788,215)PSP LLR Bronze: Earned 10,000 credits (26,371)SoB LLR Silver: Earned 100,000 credits (183,524)SR5 LLR Bronze: Earned 10,000 credits (11,183)SGS LLR Bronze: Earned 10,000 credits (43,147)TRP LLR Bronze: Earned 10,000 credits (72,462)321 Sieve Ruby: Earned 2,000,000 credits (2,692,032)AP 26/27 Bronze: Earned 10,000 credits (72,774)
Message 131208 - Posted: 18 Jul 2019 | 5:11:13 UTC - in response to Message 131207.

Never mind, I just realized it. Those numbers will all be divisible by 5.

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131214 - Posted: 18 Jul 2019 | 9:27:39 UTC
Last modified: 18 Jul 2019 | 9:33:42 UTC

Jim and Ravi, excellent observations.

I hadn't even mentioned the aurifeuillean factorization.

Clearly, in many cases, the n that are removed by algebraic factorizations are also already removed by a small prime (or a set of small primes), and in that cases the knowledge of the algebraic factorization does not help. But in other cases, as we have seen, you can remove a few extra candidates for free if you know your algebraic factorizations.

Summary (given a candidate k*2^n + 1):

If k is a perfect cube (y^3) and n is a multiple of three (3z), remove. Because X^3 + 1 = (X + 1)(X^2 - X + 1).

If k is a fifth power (y^5) and n is a multiple of five (5z), remove. Because X^5 + 1 = (X + 1)(X^4 - X^3 + X^2 - X + 1).

If k is a seventh power (y^7) and n is a multiple of seven (7z), remove. Because X^7 + 1 = (X + 1)(X^6 - X^5 + X^4 - X^3 + X^2 - X + 1).

If k is a eleventh power (y^11) and n is a multiple of eleven (11z), remove. Because X^11 + 1 = (X + 1)(X^10 - X^9 + X^8 - X^7 + X^6 - X^5 + X^4 - X^3 + X^2 - X + 1).

(And so on for all odd primes.)

If k is a fourth power (y^4) and n is singly even (that is n = 2 mod 4; n is of form 4z+2), remove. Because 4X^4 + 1 = (2X^2 + 2X + 1)(2X^2 - 2X + 1).

/JeppeSN

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131215 - Posted: 18 Jul 2019 | 9:32:43 UTC
Last modified: 18 Jul 2019 | 9:36:01 UTC

With the minus form k*2^n - 1 (not a Proth number), we have similarly:

If k is a perfect square (y^2) and n is even (a multiple of two, 2z), remove. Because X^2 - 1 = (X - 1)(X + 1).

If k is a perfect cube (y^3) and n is a multiple of three (3z), remove. Because X^3 - 1 = (X - 1)(X^2 + X + 1).

If k is a fifth power (y^5) and n is a multiple of five (5z), remove. Because X^5 - 1 = (X - 1)(X^4 + X^3 + X^2 + X + 1).

(And so on for all primes.)

No aurifeuillean factorization here. And the difference is, the "high-school" factorization works for 2,3,5,7,11,...; where in the plus (Proth) case it works only for the odd powers 3,5,7,11,...

/JeppeSN

Profile JeppeSNProject donor
Send message
Joined: 5 Apr 14
Posts: 972
ID: 306875
Credit: 11,517,616
RAC: 8,187
321 LLR Silver: Earned 100,000 credits (360,928)Cullen LLR Bronze: Earned 10,000 credits (98,851)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Ruby: Earned 2,000,000 credits (2,486,479)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Bronze: Earned 10,000 credits (16,010)SGS LLR Bronze: Earned 10,000 credits (32,929)TRP LLR Bronze: Earned 10,000 credits (71,060)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (101,851)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 131223 - Posted: 18 Jul 2019 | 16:11:53 UTC - in response to Message 131181.

My primitive loops will take (too) long to exclude the possibility that { k=343, n=2798940 } has a small factor (in the G's, T's or P's) as well.

343*2^2798940 + 1 wasn't an example either, had factor 1,734,415,048,423. /JeppeSN

Post to thread

Message boards : Proth Prime Search : Algebraically factorizable Proth prime candidates

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.97, 0.94, 1.01
Generated 12 Dec 2019 | 14:01:55 UTC