## Other

drummers-lowrise

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

Author Message
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

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

My lucky number is 75898524288+1

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

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

Message 131180 - Posted: 17 Jul 2019 | 12:15:37 UTC - in response to Message 131179.

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

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

Message 131182 - Posted: 17 Jul 2019 | 13:14:53 UTC - in response to Message 131181.

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 | +----------+

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

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

My lucky number is 75898524288+1

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

Message 131203 - Posted: 18 Jul 2019 | 0:03:25 UTC - in response to Message 131186.

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

Message 131204 - Posted: 18 Jul 2019 | 0:38:49 UTC - in response to Message 131203.

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.

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.

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.

Message 131214 - Posted: 18 Jul 2019 | 9:27:39 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

Message 131215 - Posted: 18 Jul 2019 | 9:32:43 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

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

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