Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
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 Goetz Volunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 0
                           
|
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 75898524288+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 | |
|
|
|
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: 13513
ID: 53948
Credit: 236,922,854
RAC: 0
|
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 75898524288+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: 916
ID: 107307
Credit: 974,494,092
RAC: 0
         
|
|
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 |
+----------+ | |
|
|
|
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 | |
|
Michael GoetzVolunteer moderator
Project administrator
Send message
Joined: 21 Jan 10
Posts: 13513
ID: 53948
Credit: 236,922,854
RAC: 0
|
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.
____________
My lucky number is 75898524288+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: 916
ID: 107307
Credit: 974,494,092
RAC: 0
|
-- 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 FernandoProject administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 144
ID: 1108183
Credit: 8,505,009
RAC: 0
             
|
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. | |
|
JimBHonorary cruncher
Send message
Joined: 4 Aug 11
Posts: 916
ID: 107307
Credit: 974,494,092
RAC: 0
|
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: 144
ID: 1108183
Credit: 8,505,009
RAC: 0
|
|
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 "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 | |
|
|
|
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 |
