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
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

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.
____________
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: 2584 ID: 29980 Credit: 550,654,016 RAC: 13,199

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
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

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.
____________
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  

JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 918 ID: 107307 Credit: 977,945,376 RAC: 61

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
Send message
Joined: 21 Jan 10 Posts: 13804 ID: 53948 Credit: 345,369,032 RAC: 6,456

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.
____________
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  

JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 918 ID: 107307 Credit: 977,945,376 RAC: 61

 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 Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 206 ID: 1108183 Credit: 11,958,242 RAC: 5,116

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.  

JimBHonorary cruncher Send message
Joined: 4 Aug 11 Posts: 918 ID: 107307 Credit: 977,945,376 RAC: 61

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 Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 206 ID: 1108183 Credit: 11,958,242 RAC: 5,116

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  

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