Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

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

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  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 13046 ID: 53948 Credit: 202,912,378 RAC: 88,420

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 75898^{524288}+1  


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  

mackerelVolunteer tester
Send message
Joined: 2 Oct 08 Posts: 2247 ID: 29980 Credit: 351,961,193 RAC: 358,010

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  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 13046 ID: 53948 Credit: 202,912,378 RAC: 88,420

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 75898^{524288}+1  


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  

JimBVolunteer moderator Project administrator Project developer Send message
Joined: 4 Aug 11 Posts: 892 ID: 107307 Credit: 869,756,415 RAC: 778,110

PPS3M (n=2M2.999999M) was sieved to p=100P.
SELECT COUNT(*) FROM llr WHERE project="PPS" and k=343 and n mod 3 = 0;
++
 count(*) 
++
 0 
++  


PPS3M (n=22.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", "PPSMega" )  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  

Michael GoetzVolunteer moderator Project administrator Project scientist
Send message
Joined: 21 Jan 10 Posts: 13046 ID: 53948 Credit: 202,912,378 RAC: 88,420

PPS3M (n=22.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", "PPSMega" )  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 75898^{524288}+1  


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  

JimBVolunteer moderator Project administrator Project developer Send message
Joined: 4 Aug 11 Posts: 892 ID: 107307 Credit: 869,756,415 RAC: 778,110

 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 012M.
Algebraic factors were also applied for k=625. I don't remember why this works, but for example I have that:
25*2^55000695*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 FernandoProject administrator Project scientist Send message
Joined: 21 Mar 19 Posts: 44 ID: 1108183 Credit: 4,133,139 RAC: 8,336

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^55000695*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.  

JimBVolunteer moderator Project administrator Project developer Send message
Joined: 4 Aug 11 Posts: 892 ID: 107307 Credit: 869,756,415 RAC: 778,110

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 FernandoProject administrator Project scientist Send message
Joined: 21 Mar 19 Posts: 44 ID: 1108183 Credit: 4,133,139 RAC: 8,336

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


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  


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 "highschool" 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  


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 