Bases > 1030 and k's > CK

[gd_barnes]

I have Sweety blocked and just delete all of his posts now without even knowing what they say. It makes my job a lot easier.

I will leave this one since it was responded to.

Edit:

Curtis,

If you can ban Sweety from CRUS I would appreciate that.

Thanks,
Gary

[NHoodMath]

Originally Posted by NHoodMath

I already had this one (R2021) searched to 13K, going to 25K rn (BTW I did finish those 3 k's on S2020 to n=100K, no primes)

I actually quit on this in January, it reached 30K with no new primes, still 7 k's remaining (22, 32, 74, 98, 212, 254, 332), highest prime found was for k=242 at n=13212.

[LaurV]

I remember I tested both R and S sides of base 2021 at the beginning of the year (as it is customary every year, hehe) close to n=200k and there were only 5 k's left for Riesel side (74 and 332 have primes below n=100k) and 8 k's left for Sierpinski side. The both sides have the same conjectured k, which amazed me at the time, but I don't know how common it is, I didn't talk about it, and it seems somehow I forgot to post here. I will have to look for those files this weekend Sunday (because it is 1:25 AM already here, Sunday).

[NHoodMath]

Originally Posted by LaurV

...The both sides have the same conjectured k, which amazed me at the time, but I don't know how common it is,...

It is actually quite common for a base to have the same CK on both sides due to how the math behind the CK works (I'll outline the simplest case). Say for a given base b that primes p and q > 2 divide (b+1). Then in that case, find a number k where a * p +- 1 = c * q +- 1 = k (if one sign is plus then the other must be minus). That number k will be a CK on both sides (unless (k-1 for Riesel, k+ 1 for Sierp) is divisible by a factor of b - 1, in which case it will be trivially eliminated)
For base 2021:
2022 = 2 * 3 * 337
has two factors > 2
Let p = 3
q = 337
Searching for a and c finds the lowest possible answer where a = 113 and c = 1, 113*3-1 = 1*337+1=338
k-1 = 337 is prime, k + 1 = 3 * 113 (not divisible by any factors of 2020 = 2^2 * 5 *101) so 338 will be a ck on both sides. Same logic can be applied to most any base, as long as b + 1 has at least two prime factors > 2.

[LaurV]

Well, thanks for replying, I actually forgot about this stuff for a while, but right now being a new year, I decided to play a bit with base 2022 (for which the CK seems to be 50, so, not many things to check) and when I looked for the thread, I realized that I promised to post the base 2021. Looking for it, I found that not all of the remaining k were tested to 200k, so I re-run a part of it.

Summary in the attached file. If asked for a password, it is "00" (no quotes). That's to cheat the spiders on the way... (and because rar makes the archive much smaller, but its extension not accepted by the forum).

@Gary, feel free to put it anywhere you like, in your tables, or ignore it. I know you don't record bases larger than 1030, but this is "well done"

So, I am playing now with "twenty-twenty-too" like the covid-related saying goes... Hope I won't get bored.

base2021.zip

[LaurV]

Math question: What's the trick that makes 16*2022^n-1 always divisible by 17, for odd n?

I mean, for even n, it is clear that this is a^2-1, which is (a-1)(a+1), which is properly spotted by almost all sievers (like srsieve and related). Similar for 49, which is a square too, all even n are properly eliminated by srsieve before sieving, but the odd n survive, and it is not immediately evident how (and if) they factor.

That is related to base 2022, with which I am currently playing. The conjectured k is 50. After preliminary tests to n=2000, (yeah, it took very short time, I am not trying to play sweety here, but I do not put the time and resources into this, unless I have surplus ) there are only very few candidates remaining:

On R-side, there are no primes for 6, 8, 15, 16, 27, 49.
The trivials are 44 and 48.
The "largest" prime found is 43*2022^447-1

On S-side, there are no primes for 2, 6, 12 13.
The trivials are 42 and 46.
The "largest" prime(s) found are 7*2022^1871+1 and 20*2022^1813+1

So, the S-side is ok, we will find some more primes sooner or later, but what puzzles us is the R-side. First, because it seems that the remaining k's are mostly powers, 8, 16, 27, 49, but this may be explained by the fact that we tested less candidates for them (as half, or a third for cubes, of the candidates are eliminated by algebraic factorization for such k's), so probably a prime will pop later too.

But then, there are no candidates left to test for 16. This did puzzled us a lot. As all of the odd n's are divisible by 17, few questions troubled us:
1. is there any "aurifeuillian" factorization of expressions of the form 2^4*b^(2x+1)-1? or even a^4*b^(2x+1)-1?
2. if so, how do we teach srsieve to recognize it?
3. can we say that 16 is a new conjectured k for Riesel base 2022? (this would not infirm the "covering set" part, there is no infinite covering set here, all candidates are divisible by 17, so technically, you have a covering set of a single element ).
4. do we miss something obvious (like some trivial stuff?)

At the end, it seems not related at all to any algebraic factorization, neither to the fact that 16 is a power This was put there by the god or evil, to induce us into making stupid assumptions...

The trick is the fact that 2022 is 16 (mod 17). And 16 is "-1" (mod 17), so we have (-1)*(-1)^odd, which is always 1 (mod 17). Now you subtract 1, and there you are...

This still raises a final question, why srsieve doesn't detect such case as a trivial case.
.

[henryzz]

Originally Posted by LaurV

So, the S-side is ok, we will find some more primes sooner or later, but what puzzles us is the R-side. First, because it seems that the remaining k's are mostly powers, 8, 16, 27, 49, but this may be explained by the fact that we tested less candidates for them (as half, or a third for cubes, of the candidates are eliminated by algebraic factorization for such k's), so probably a prime will pop later too.

But then, there are no candidates left to test for 16. This did puzzled us a lot. As all of the odd n's are divisible by 17, few questions troubled us:
1. is there any "aurifeuillian" factorization of expressions of the form 2^4*b^(2x+1)-1? or even a^4*b^(2x+1)-1?
2. if so, how do we teach srsieve to recognize it?
3. can we say that 16 is a new conjectured k for Riesel base 2022? (this would not infirm the "covering set" part, there is no infinite covering set here, all candidates are divisible by 17, so technically, you have a covering set of a single element ).
4. do we miss something obvious (like some trivial stuff?)

At the end, it seems not related at all to any algebraic factorization, neither to the fact that 16 is a power This was put there by the god or evil, to induce us into making stupid assumptions...

The trick is the fact that 2022 is 16 (mod 17). And 16 is "-1" (mod 17), so we have (-1)*(-1)^odd, which is always 1 (mod 17). Now you subtract 1, and there you are...

This still raises a final question, why srsieve doesn't detect such case as a trivial case.
.

I get the following output from srsieve:

srsieve 1.1.4 -- A sieve for integer sequences in n of the form k*b^n+c.
(kr) For sequence 16*2022^n-1 -> (2^4)*2022^n-1
(kr) Sequence 16*2022^n-1 has 25000 terms removed due to algebraic factors of the form 2*2022^(n/4)-1
(kr) For sequence 16*2022^n-1 -> (4^2)*2022^n-1
(kr) Sequence 16*2022^n-1 has 25000 terms removed due to algebraic factors of the form 4*2022^(n/2)-1
(cr) For sequence 16*2022^n-1 -> 16*2022^4 = (2^4*3^2*337^2)^2
(cr) Sequence 16*2022^n-1 has 0 terms removed due to algebraic factors of the form (2^4*3^2*337^2)*2022^((n-4)/2)-1
(cr) For sequence 16*2022^n-1 -> 16*2022^8 = (2^6*3^4*337^4)^2
(cr) Sequence 16*2022^n-1 has 0 terms removed due to algebraic factors of the form (2^6*3^4*337^4)*2022^((n-8)/2)-1
Sieve range is 1 to 100172, using 317 baby steps, 316 giant steps.
Using a hashtable of 1024 short elements (maximum density 0.31)
srsieve started: 1 <= n <= 100000, 3 <= p <= 4000000000003
Beginning small sieve at p=3.
removed candidate sequence 16*2022^n-1 from the sieve
Sieving 3 <= p <= 19 eliminated 50000 terms, 0 remain.
Wrote 0 terms for 0 sequences to abc format file `sr_2022.pfgw'.
srsieve stopped: at p=19 because all candidate sequences were eliminated.

This indicates that it was able to remove half the terms through algebraic factorizations. 17 was a factor of the rest.
Not sure why your version of srsieve didn't detect it. I would update to the latest double-check and ask rouge if there is still an issue.

[Dr Sardonicus]

Originally Posted by LaurV

Math question: What's the trick that makes 16*2022^n-1 always divisible by 17, for odd n?
<snip>
The trick is the fact that 2022 is 16 (mod 17). And 16 is "-1" (mod 17), so we have (-1)*(-1)^odd, which is always 1 (mod 17). Now you subtract 1, and there you are...

Man, when I saw the initial question, I was because I knew this was something you knew or could easily figure out.

I'm glad I kept reading

This still raises a final question, why srsieve doesn't detect such case as a trivial case.

This trivial case for k*b^n - 1 appears to occur when gcd(k+1, b+1) > 1.

Why doesn't srsieve detect it? I don't know. Perhaps it doesn't occur very often.

EDIT: After becoming more awake, it occurred to me that individual users could perhaps check the gcd condition. In the present case, 16*2022^n - 1 would be seen as composite for all n and not tested at all.

I looked at earlier posts and found, e.g. 42*1031^n - 1 and 8*1031^n - 1, with trivial factors of 43 and 3, respectively, for odd n. When gcd(k+1,b+1) > 1, one could perhaps devise some way to skip the odd exponents altogether.

[rogue]

Originally Posted by henryzz

I get the following output from srsieve:

srsieve 1.1.4 -- A sieve for integer sequences in n of the form k*b^n+c.
(kr) For sequence 16*2022^n-1 -> (2^4)*2022^n-1
(kr) Sequence 16*2022^n-1 has 25000 terms removed due to algebraic factors of the form 2*2022^(n/4)-1
(kr) For sequence 16*2022^n-1 -> (4^2)*2022^n-1
(kr) Sequence 16*2022^n-1 has 25000 terms removed due to algebraic factors of the form 4*2022^(n/2)-1
(cr) For sequence 16*2022^n-1 -> 16*2022^4 = (2^4*3^2*337^2)^2
(cr) Sequence 16*2022^n-1 has 0 terms removed due to algebraic factors of the form (2^4*3^2*337^2)*2022^((n-4)/2)-1
(cr) For sequence 16*2022^n-1 -> 16*2022^8 = (2^6*3^4*337^4)^2
(cr) Sequence 16*2022^n-1 has 0 terms removed due to algebraic factors of the form (2^6*3^4*337^4)*2022^((n-8)/2)-1
Sieve range is 1 to 100172, using 317 baby steps, 316 giant steps.
Using a hashtable of 1024 short elements (maximum density 0.31)
srsieve started: 1 <= n <= 100000, 3 <= p <= 4000000000003
Beginning small sieve at p=3.
removed candidate sequence 16*2022^n-1 from the sieve
Sieving 3 <= p <= 19 eliminated 50000 terms, 0 remain.
Wrote 0 terms for 0 sequences to abc format file `sr_2022.pfgw'.
srsieve stopped: at p=19 because all candidate sequences were eliminated.

This indicates that it was able to remove half the terms through algebraic factorizations. 17 was a factor of the rest.
Not sure why your version of srsieve didn't detect it. I would update to the latest double-check and ask rouge if there is still an issue.

srsieve and srsieve2 remove terms that have an algebraic factorization prior to sieving. 17 is not an algebraic factor, but is removed by normal sieving. Could code be added to find these special factors? Yes, but since these specials factors are small, the terms are removed almost immediately after sieving is started.

[henryzz]

Originally Posted by rogue

srsieve and srsieve2 remove terms that have an algebraic factorization prior to sieving. 17 is not an algebraic factor, but is removed by normal sieving. Could code be added to find these special factors? Yes, but since these specials factors are small, the terms are removed almost immediately after sieving is started.

When I read the post I thought that the algebraic factors hadn't been detected not the 17. It makes sense that the 17 would just be sieved out as it is trivial to do so.


I have tested the Riesel side upto 10k and found 8*2022^7519-1 which removes the lowest weight k.

[gd_barnes]

Please see this:
https://mersenneforum.org/showpost.p...04&postcount=3

2022 == 16 mod 17

Therefore k's where k=m^2 and m==(4 or 13 mod 17) will have partial algebraic factors to make a full covering set.

In this case k=16, 169, 441, 900, etc. have the following factors:
even n: algebraic
odd n: 17

Since the conjecture is 50, only k=16 is eliminated. It should be removed before any searching or sieving is done.

k=16 is not considered the conjecture because it is only eliminated by some algebraic factors. The conjectures here must have "numeric fixed" covering sets. Otherwise many of the conjectures become not interesting due to a very low conjecture.

More often than other k's, squared k's on the Riesel side and cubed (and high-power k's) on both sides are remaining (that do not have a full covering set) simply due to the fact that part of their n's cannot contain a prime due to algebraic factors.

After Henry's find and using LaurV's original info. it looks like that only k=6, 15, 27, and 49 remain at n=10K for R2022.

You can see the main project Riesel page for many instances of algebraic factors like this. R1002 is the largest base on the project with this exact scenario.