Mersenne Numbers Known from Number Practice to Be Composite
 

The Mersenne numbers with prime exponents [I]p[/I] > 3 for which [I]p[/I] mod 4 = 3 and 2[I]p[/I] + 1 is a prime number are known to be composite.
Out of the total of 50,847,534 prime exponents 2 ≤ [I]p[/I] ≤ 999,999,937, there are 1,655,600 prime exponents (3.256%) satisfying the aforesaid conditions.
Perhaps GIMPS could add notifications that the corresponding Mersenne numbers are known to be composite from elementary number theory.
The compressed list of the 1,655,600 prime exponents from 11 to 999,999,191 exceeds the limit of 4 MB.
Therefore, a Wolfram code that saves the prime exponents in a file is given below instead.
[code]
SetDirectory[NotebookDirectory[]]; fname = NotebookDirectory[] <> "Mp3mod4and2pplus1.dat"; file = File[fname]; If[FileExistsQ[file] == False, OpenWrite[file]; Close[file];];
OpenAppend[file];
Np = PrimePi[999999937]; Pcount = 0;
ic = 3; While[ic <= Np, p = Prime[ic]; If[(Mod[p, 4] == 3) && (PrimeQ[2*p + 1] == True), Pcount++; Write[file, p];]; ic++;];
Close[file]; Print[Pcount];
[/code]

How many don't already have known factors?

[QUOTE=Dobri;604130]The Mersenne numbers with prime exponents [I]p[/I] > 3 for which [I]p[/I] mod 4 = 3 and 2[I]p[/I] + 1 is a prime number are known to be composite.[/QUOTE]

More precisely, [$]2p + 1[/$] divides [$]M_p[/$] for the case you described. So all of these Mersenne numbers have known (small) factors, and all of them should be in the database already.

Yes they have the smallest factor 2kp+1 with k=1, so they were found back in ~1996 (or 2008 when the range extended to 1 billion). No "elementary" tricks will improve on a project running for 25-26 years.

GIMPS did have major improvements in the last 3-7 years with Jacobi check, Gerbicz error checking and finally PRP proofs, but they were far from elementary.

The information in this thread is provided for completeness and is not concerned with novelty indeed.
Searching for "1655600", two previous posts on the topic can be located, see
[URL]https://www.mersenneforum.org/showthread.php?p=300787&highlight=1655600#post300787[/URL] and
[URL]https://www.mersenneforum.org/showthread.php?p=180704&highlight=1655600#post180704[/URL].

For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p-1 (this is even true if p itself is not prime)

There should be conditions that 4*p+1, 6*p+1, 8*p+1, etc. always divides 2^p-1

You can check the sequence [URL="https://oeis.org/A001917"]https://oeis.org/A001917[/URL], for q == 1, 7 mod 8, A001917(primepi(q)) is even, and for q == 1, 7 mod 8, A001917(primepi(q)) is odd, thus for p == 3 mod 4, A001917(primepi(2*p+1)) is even, and hence 2*p+1 must divide 2^p-1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc.

[QUOTE=sweety439;604207]For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p-1 (this is even true if p itself is not prime)

There should be conditions that 4*p+1, 6*p+1, 8*p+1, etc. always divides 2^p-1

You can check the sequence [URL="https://oeis.org/A001917"]https://oeis.org/A001917[/URL], for q == 1, 7 mod 8, A001917(primepi(q)) is even, and for q == 1, 7 mod 8, A001917(primepi(q)) is odd, thus for p == 3 mod 4, A001917(primepi(2*p+1)) is even, and hence 2*p+1 must divide 2^p-1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc.[/QUOTE]

4p+1 never divides 2^p-1 right ? I can't find the sequences in OEIS

[QUOTE=kijinSeija;604210]4p+1 never divides 2^p-1 right ? I can't find the sequences in OEIS[/QUOTE]

Right, since 4p+1 is always == 5 mod 8, and for q == 5 mod 8, A001917(primepi(q)) is always odd and cannot be 4

[QUOTE=sweety439;604212]Right, since 4p+1 is always == 5 mod 8, and for q == 5 mod 8, A001917(primepi(q)) is always odd and cannot be 4[/QUOTE]

Thanks for your answer.

By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?

I know the condition for 2*p+1 but I have no idea for these two for example.

[QUOTE=kijinSeija;604214]Thanks for your answer.

By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?

I know the condition for 2*p+1 but I have no idea for these two for example.[/QUOTE]

No, I want to know how to compute A001917(q) for an odd prime q with given congruent class mod some numbers (say 8 or 24), I want to know the condition for A001917(q) is divisible by given number r, it is equivalent to 2 is r-th power residue ([URL="https://en.wikipedia.org/wiki/Quadratic_residue"]quadratic residue[/URL] for r=2, [URL="https://en.wikipedia.org/wiki/Cubic_reciprocity"]cubic residue[/URL] for r=3, [URL="https://en.wikipedia.org/wiki/Quartic_reciprocity"]quartic residue[/URL] for r=4, etc., we should use cubic reciprocity and quartic reciprocity to solve, I do not think it can be solved for r>4 (except r=8 and r=16), since a general quintic equation cannot be solved algebraically) mod q (where r is the largest such number dividing q-1), such prime q must divide Phi((q-1)/r,2), where Phi is the [URL="https://en.wikipedia.org/wiki/Cyclotomic_polynomial"]cyclotomic polynomial[/URL], and (let p = (q-1)/r) if p is prime, then this is 2^p-1, if p is twice a prime, then this is the Wagstaff number (2^(p/2)+1)/3, and if p is power of 2, then this is the Fermat number 2^(p/2)+1

[QUOTE=sweety439;604218]I do not think it can be solved for r>4 (except r=8 and r=16), since a general quintic equation cannot be solved algebraically[/QUOTE]

Well you didn't think enough. This has absolutely nothing to do with the unsolvability of the general quintic.

First, you use the phrase "cannot be solved" but you don't understand what it means in this context. Over the reals or the complex numbers, it means that we *literally cannot write down the solutions*. But here we're working over a finite field, namely the integers modulo some prime. So even though it isn't easy to find solutions to x^5 = 2, it is certainly possible to write them down if they exist. And secondly, while a general quintic cannot be solved over the complex numbers, the quintic x^5 = 2 most definitely can!

Conditions for 2 to be a quintic residue mod p [URL="https://projecteuclid.org/journals/duke-mathematical-journal/volume-18/issue-1/The-quintic-character-of-2--and-3/10.1215/S0012-7094-51-01802-9.full"]do exist[/URL] although they are not convenient to use. This can be done for higher order roots too but the conditions will get even worse.

[QUOTE=kijinSeija;604214]By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?[/QUOTE]The real problem is that for k > 1, the Galois group of the polynomial f(x) = x^(2*k) - 2 is non-Abelian. (It is however, a solvable group, meaning the equation f(x) = 0 is "solvable by radicals.")

The polynomial is irreducible (e.g. by Eisenstein's criterion). The 2k solutions to f(x) = 0 consist of the real 2k-th root of 2, multiplied by each of the 2k 2k[sup]th[/sup] roots of unity.

The significance of the Galois group being non-Abelian is that the factorization of f(x) == 0 (mod q) for prime q can [i]not[/i] be characterized in terms of congruences mod M for any integer M.

For k = 3, congruences only get us part of the way. We can say that p == 1 (mod 4) to insure that q = 6*p + 1 is congruent to 7 (mod 8), hence a quadratic residue (mod 2). But 2 also has to be a cubic residue (mod q). There's no integer congruence condition for that. There is the condition that, with q = a^2 + 3*b^2, b is divisible by 3. But that's not much help.

Within the limited sample of known Mersenne primes, there are 7 Mersenne primes, with prime exponents [I]p[/I] = 2, 5, 89, 9689, 21701, 859433, and 43112609, for which 2[I]p[/I] + 1 is a prime number. Obviously, [I]p[/I] mod 4 = 1 for [I]p[/I] = 5, 89, 9689, 21701, 859433, and 43112609.

Concerning [I]k[/I] = 5, there are 10 known Mersenne primes, with prime exponents [I]p[/I] = 3, 7, 13, 19, 31, 1279, 2203, 2281, 23209, and 44497, for which 2*5*[I]p[/I]+1 is a prime number. Here [I]p[/I] mod 6 = 1 for [I]p[/I] = 7, 13, 19, 31, 1279, 2203, 2281, 23209, and 44497.

[QUOTE=Dr Sardonicus;604242]The real problem is that for k > 1, the Galois group of the polynomial f(x) = x^(2*k) - 2 is non-Abelian. (It is however, a solvable group, meaning the equation f(x) = 0 is "solvable by radicals.")

The polynomial is irreducible (e.g. by Eisenstein's criterion). The 2k solutions to f(x) = 0 consist of the real 2k-th root of 2, multiplied by each of the 2k 2k[sup]th[/sup] roots of unity.

The significance of the Galois group being non-Abelian is that the factorization of f(x) == 0 (mod q) for prime q can [i]not[/i] be characterized in terms of congruences mod M for any integer M.

For k = 3, congruences only get us part of the way. We can say that p == 1 (mod 4) to insure that q = 6*p + 1 is congruent to 7 (mod 8), hence a quadratic residue (mod 2). But 2 also has to be a cubic residue (mod q). There's no integer congruence condition for that. There is the condition that, with q = a^2 + 3*b^2, b is divisible by 3. But that's not much help.[/QUOTE]


So if we add than p == 1 (mod 4) and 6*p+1 = 27a^2+b^2 should be the two conditions for 6*p+1 divides 2^p-1 right ?

[QUOTE=kijinSeija;604284]So if we add than p == 1 (mod 4) and 6*p+1 = 27a^2+b^2 should be the two conditions for 6*p+1 divides 2^p-1 right ?[/QUOTE]
Here is a counterexample: [I]p[/I] = 5, [I]p[/I] mod 4 = 1, and 2[I][SUP]p[/SUP][/I] - 1 = 6[I]p[/I] + 1 = 27×1[SUP]2[/SUP] + 2[SUP]2[/SUP] is the 3[SUP]rd[/SUP] Mersenne prime number [I]M[/I][SUB]5[/SUB].

[QUOTE=kijinSeija;604284]So if we add than p == 1 (mod 4) and 6*p+1 = 27a^2+b^2 should be the two conditions for 6*p+1 divides 2^p-1 right ?[/QUOTE]
Excluding [I]p[/I] = 5 for which 2[SUP]5[/SUP] - 1 = 6×5 + 1 = 27×1[SUP]2[/SUP] + 2[SUP]2[/SUP], there are no other counterexamples for [I]p[/I] mod 4 = 1 and [I]k[/I] = 3 within the limited sample of known Mersenne primes.

Starting from the composite Mersenne number for [I]p[/I] = 101, whenever [I]p[/I] mod 4 = 1 and [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) ≠ 0 there are no instances of 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP] for [I]p[/I] = 101, 107, 173, 181, 241, 257, 277, 293, 313,...

Starting from the composite Mersenne number for [I]p[/I] = 37, whenever [I]p[/I] mod 4 = 1 and [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) = 0 there are instances of 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP] for [I]p[/I] = 37, 73, 233, 397, 461, 557, 577, 601, 761,...

Therefore, the quoted statement could be considered as a possible conjecture for now.

[QUOTE=Dobri;604319]Here is a counterexample: [I]p[/I] = 5, [I]p[/I] mod 4 = 1, and 2[I][SUP]p[/SUP][/I] - 1 = 6[I]p[/I] + 1 = 27×1[SUP]2[/SUP] + 2[SUP]2[/SUP] is the 3[SUP]rd[/SUP] Mersenne prime number [I]M[/I][SUB]5[/SUB].[/QUOTE]

But 31 divides 31 for example. This is really a counterexample ?

Oh I see what you mean :grin:

[QUOTE=Dobri;604324]Excluding [I]p[/I] = 5 for which 2[SUP]5[/SUP] - 1 = 6×5 + 1 = 27×1[SUP]2[/SUP] + 2[SUP]2[/SUP], there are no other counterexamples for [I]p[/I] mod 4 = 1 and [I]k[/I] = 3 within the limited sample of known Mersenne primes.

Starting from the composite Mersenne number for [I]p[/I] = 101, whenever [I]p[/I] mod 4 = 1 and [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) ≠ 0 there are no instances of 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP] for [I]p[/I] = 101, 107, 173, 181, 241, 257, 277, 293, 313,...

Starting from the composite Mersenne number for [I]p[/I] = 37, whenever [I]p[/I] mod 4 = 1 and [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) = 0 there are instances of 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP] for [I]p[/I] = 37, 73, 233, 397, 461, 557, 577, 601, 761,...

Therefore, the quoted statement could be considered as a possible conjecture for now.[/QUOTE]

Thanks, this is interesting. How do you check that ? With Wolfram Alpha ?

[QUOTE=Dobri;604324]Starting from the composite Mersenne number for [I]p[/I] = 101, whenever [I]p[/I] mod 4 = 1 and [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) ≠ 0 there are no instances of 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP] for [I]p[/I] = 101, 107, 173, 181, 241, 257, 277, 293, 313,...[/QUOTE]
There is a typo, it has to be "... for [I]p[/I] = 101, [COLOR="Red"][B]137[/B][/COLOR], 173, 181, 241, 257, 277, 293, 313,..."

Like Mersenne composites, it seems than p == 3 (mod 4) and 6*p+1 = 27a^2+16b^2 should be the two condition for 6p+1 divides Wagstaff numbers (2^p+1)/3. (7, 47, 83, 107, 263, 271 ...) The sequence isn't in OEIS by the way.

[QUOTE=kijinSeija;604326]Thanks, this is interesting. How do you check that ? With Wolfram Alpha ?[/QUOTE]
I just connect a Raspberry Pi 4B device to the HDMI port of my 4K TV set and use Wolfram Mathematica for free.
Here is the Wolfram code for the Mersenne primes
[code]
MPData = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933};
Np = 51; ic = 1; While[ic <= Np, p = MPData[[ic]];
If[(Mod[p, 4] == 1) && (PrimeQ[2*3*p + 1] == True),
Ms = FindInstance[{2*3*p + 1 == 27*ac^2 + bc^2}, {ac, bc}, PositiveIntegers];
Print[p, " ", Ms];
]; ic++;];
[/code]
and the obtained output
[code]
5 {{ac->1,bc->2}}
13 {}
17 {}
61 {}
2281 {}
44497 {}
3021377 {}
57885161 {}
82589933 {}
[/code]
followed by the Wolfram code for the composite Mersenne numbers
[code]
kc = 3; ic = 1; While[ic <= 1000, p = Prime[ic]; fc = 2*kc*p + 1;
If[(Mod[p, 4] == 1) && (PrimeQ[fc] == True) && (MersennePrimeExponentQ[p] == False), Mn = 2^p - 1;
rc = FindInstance[{fc == 27*ac^2 + bc^2}, {ac, bc}, PositiveIntegers];
Print[p, " ", Mod[Mn, fc], " ", rc];];
ic++;];
[/code]
and the obtained output
[code]
37 0 {{ac->1,bc->14}}
73 0 {{ac->3,bc->14}}
101 209 {}
137 173 {}
173 897 {}
181 828 {}
233 0 {{ac->3,bc->34}}
241 703 {}
257 680 {}
277 1343 {}
293 507 {}
313 487 {}
373 294 {}
397 0 {{ac->9,bc->14}}
461 0 {{ac->7,bc->38}}
557 0 {{ac->9,bc->34}}
577 0 {{ac->11,bc->14}}
593 2122 {}
601 0 {{ac->3,bc->58}}
641 1891 {}
653 2748 {}
661 3077 {}
761 0 {{ac->13,bc->2}}
...
[/code]

It should be noted that it is assumed that 6[I]p[/I] + 1 is a prime number.
If 6[I]p[/I] + 1 is not a prime number, there are instances when [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) ≠ 0 and 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP], for example:
[I]p[/I] = 41, (2[SUP]41[/SUP] - 1) mod (6×41 + 1) = 31 ≠ 0, and 6×41 + 1 = 27×3[SUP]2[/SUP] +2[SUP]2[/SUP].

Yes of course 6*p+1 must be prime I guess but p isn't necessary prime.

For example : (6*21+1) = 127 divides (2^21-1) but 21 isn't prime.

[QUOTE=kijinSeija;604335]Yes of course 6*p+1 must be prime I guess but p isn't necessary prime.

For example : (6*21+1) = 127 divides (2^21-1) but 21 isn't prime.[/QUOTE]
This forms a sequence of composite [I]p[/I] values indeed,
[I]p[/I] = 21, 121, 153, 221, 237, 245, 305, 333, 357, 381, 445, 465, 545, 565, 605, 637, 657, 737, 753, 777, 793, 861, 917,...

[code]
kc = 3; ic = 2; While[ic <= 1000, p = ic; Mn = 2^p - 1; fc = 2*kc*p + 1;
If[(Mod[p, 4] == 1) && (Mod[Mn, fc] == 0) && (PrimeQ[p] == False) && (PrimeQ[fc] == True),
rc = FindInstance[{fc == 27*ac^2 + bc^2}, {ac, bc}, PositiveIntegers];
Print[p, " ", Mod[Mn, fc], " ", rc];];

[/code][code]
21 0 {{ac->1,bc->10}}
121 0 {{ac->3,bc->22}}
153 0 {{ac->3,bc->26}}
221 0 {{ac->7,bc->2}}
237 0 {{ac->7,bc->10}}
245 0 {{ac->1,bc->38}}
305 0 {{ac->5,bc->34}}
333 0 {{ac->7,bc->26}}
357 0 {{ac->1,bc->46}}
381 0 {{ac->9,bc->10}}
445 0 {{ac->9,bc->22}}
465 0 {{ac->5,bc->46}}
545 0 {{ac->11,bc->2}}
565 0 {{ac->1,bc->58}}
605 0 {{ac->9,bc->38}}
637 0 {{ac->7,bc->50}}
657 0 {{ac->11,bc->26}}
737 0 {{ac->11,bc->34}}
753 0 {{ac->5,bc->62}}
777 0 {{ac->13,bc->10}}
793 0 {{ac->13,bc->14}}
861 0 {{ac->7,bc->62}}
917 0 {{ac->1,bc->74}}
...

[/code]

The OP to this thread indicates that we're only interested in prime exponents p. (After all, Mersenne numbers with composite exponents have algebraic factorizations, so are already "known from number theory to be composite.")

It has long been known that if p = 4*n + 3 and q = 2*p + 1 = 8*n + 7 are both prime, then q divides 2^p - 1.

This is because the quadratic character of 2 (mod q) is determined by q (mod 8).

For given k > 1, there is alas no similarly convenient criterion for when p and q = 2*k+p + 1 both being prime implies q divides 2^p - 1.

Since p = (q-1)/2/k, we can say that 2^((q-1)/2) == 1 (mod q), so that q == 1 or 7 (mod 8). This condition excludes k with k%4 = 2 from consideration.

Suppose that k > 1, k%4 <> 2, p is prime, and q = 2*k*p + 1 is also prime. We can choose p%4 to insure that q%8 is 1 or 7:[list]If k%4 = 0, p == 1 or 3 (mod 4)[*]If k == 1 (mod 4) then p == 3 (mod 4)[*]If k == 3 (mod 4) then p == 1 (mod 4).[/list]AFAIK the fastest way to determine whether q = 2*k*p + 1 divides 2^p - 1 for k > 1 is to test whether Mod(2,q)^p == 1.

I can confidently predict that q = 2*k*p + 1 will divide 2^p - 1 for about 1/k of the primes p for which q is also prime, if p%4 is chosen so that 2 is a quadratic residue (mod q). I just can't predict [i]which[/i] 1/k it will be. Here is an actual count for p < 10^8:

[code]? c1=0;c2=0;forprime(p=3,100000000,if(p%4==3,q=10*p+1;if(isprime(q),c1++;if(Mod(2,q)^p==1,c2++))));print(c1" "c2)
259346 51816
?[/code]

The proportion of primes p == 3 (mod 4) such that q = 10*p + 1 is also prime, for which q also divides 2^p - 1, is 0.19979+ which is pretty close to 1/5.

Excluding the 3[SUP]rd[/SUP] Mersenne prime number [I]M[/I][SUB]5[/SUB] (for which [I]p[/I] = 5, [I]p[/I] mod 4 = 1, 2[I][SUP]p[/SUP][/I] - 1 = 6[I]p[/I] + 1 = 27×1[SUP]2[/SUP] + 2[SUP]2[/SUP] = 31 is a prime, and also 2[I]p[/I] + 1 = 11 is a prime):

1) Out of the total of 50,847,534 prime numbers 2 ≤ [I]p[/I] ≤ 999,999,937, there are 1,046,030 prime exponents (2.057%) [COLOR="Red"]with composite Mersenne numbers [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I] + 1) = 0[/COLOR] for which [I]p[/I] mod 4 = 1 and 6[I]p[/I] + 1 = 27[I]a[/I][SUP]2[/SUP] + [I]b[/I][SUP]2[/SUP] is a prime.

2) Out of the said 1,046,030 prime exponents of composite Mersenne numbers, there are 55,953 prime exponents for which 2[I]p[/I] + 1 is also a prime.

[I]Note[/I]: The conjecture in post #17 ([url]https://www.mersenneforum.org/showpost.php?p=604324&postcount=17[/url]) holds in the interval of prime exponents 2 ≤ [I]p[/I] ≤ 999,999,937.

Also, out of the total of 50,847,534 prime numbers 2 ≤ [I]p[/I] ≤ 999,999,937, there are 3,138,462 prime numbers ([I]p[/I] = 5 included) for which 6[I]p[/I] + 1 is a prime.
Here 3,138,462 = [COLOR="Red"]3[/COLOR] × 1,046,031 ([I]p[/I] = 5 included) + 369.
Out of the said 3,138,462 prime numbers, there are 168,529 prime numbers ([I]p[/I] = 5 included) for which 2[I]p[/I] + 1 is also a prime.
Here 168,529 = [COLOR="Red"]3[/COLOR] × 55,954 ([I]p[/I] = 5 included) + 667.

For [COLOR="Red"][I]k[/I] = 5[/COLOR], out of the total of 50,847,534 prime numbers 2 ≤ [I]p[/I] ≤ 999,999,937, there are [COLOR="Red"]408,660[/COLOR] prime exponents (0.8%) [COLOR="Red"]with composite Mersenne numbers [I]M[SUB]p[/SUB][/I] mod (10[I]p[/I] + 1) = 0[/COLOR] for which [I]p[/I] mod 4 = 3 and [COLOR="Red"][I]p[/I] mod 6 = 1[/COLOR].

Also, out of the total of 50,847,534 prime numbers 2 ≤ [I]p[/I] ≤ 999,999,937, there are 4,084,314 prime numbers for which 10[I]p[/I] + 1 is a prime.
Here 4,084,314 = 2,043,235 (for which [I]p[/I] mod 4 = 1) + 2,041,079 (for which [I]p[/I] mod 4 = 3),
4,084,314 = [COLOR="Red"]4,084,313[/COLOR] (for which [COLOR="Red"][I]p[/I] mod 6 = 1[/COLOR]) + 1 (for which [I]p[/I] = 3, 2[SUP]3[/SUP] - 1 < 10×3 + 1), and
2,041,079 = [COLOR="Red"]5[/COLOR] × 408,660 [COLOR="Red"]-[/COLOR] 2,221.

Number of 2[I]kp[/I]+1 primes for [I]p[/I] within tne range 2 ≤ [I]p[/I] ≤ 999,999,937 which divide the composite Mersenne numbers [I]M[SUB]p[/SUB][/I] = 2[I][SUP]p[/SUP][/I]-1 so that [I]M[SUB]p[/SUB][/I] mod (2[I]kp[/I]+1) = 0:

[I]k[/I]=1: 1655600 (for which [I]p[/I] mod 4 = 3 and [I]p[/I] mod 6 = 5);

[I]k[/I]=2: None;

[I]k[/I]=3: 1046030 (for which [I]p[/I] mod 4 = 1 and 2×3[I]p[/I]+1 = 27[I]a[/I][SUP]2[/SUP]+[I]b[/I][SUP]2[/SUP] is a prime);

[I]k[/I]=4: 773708 (for which [I]p[/I] mod 6 = 5), however, 54990 primes are already counted for [I]k[/I]=1 and [I]k[/I]=3 as follows: for 41786 primes [I]M[SUB]p[/SUB][/I] mod (2[I]p[/I]+1) = 0, and for 13204 primes [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I]+1) = 0;

[I]k[/I]=5: 408660 (for which [I]p[/I] mod 4 = 3 and [I]p[/I] mod 6 = 1);

[I]k[/I]=6: None;

[I]k[/I]=7: 258602 (for which [I]p[/I] mod 4 = 1 and [I]p[/I] mod 6 = 5), however, 15901 primes are already counted for [I]k[/I]=3 and [I]k[/I]=4 as follows: for 9327 primes [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I]+1) = 0, for 6751 primes [I]M[SUB]p[/SUB][/I] mod (8[I]p[/I]+1) = 0, and for 9327+6751-15901=177 primes [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I]+1) = 0 and [I]M[SUB]p[/SUB][/I] mod (8[I]p[/I]+1) = 0;
...

This is a continuation of the previous post #29 at [URL]https://www.mersenneforum.org/showpost.php?p=606844&postcount=29[/URL].
…
Number of 2[I]kp[/I]+1 primes for [I]p[/I] within the range 2 ≤ [I]p[/I] ≤ 999,999,937 which divide the composite Mersenne numbers [I]M[SUB]p[/SUB][/I] = 2[I][SUP]p[/SUP][/I]-1 so that [I]M[SUB]p[/SUB][/I] mod (2[I]kp[/I]+1) = 0:

[I]k[/I]=8: 375441 (for which [I]p[/I] mod 6 = 1), however, 15228 primes are already counted for [I]k[/I]=3 and [I]k[/I]=5 as follows (note that [I]k[/I]=8=3+5): for 9615 primes [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I]+1) = 0, and for 5613 primes [I]M[SUB]p[/SUB][/I] mod (10[I]p[/I]+1) = 0;

[I]k[/I]=9: 331102 (for which [I]p[/I] mod 4 = 3), however, 30369 primes are already counted for [I]k[/I]=1,4,5 and 8 as follows (note that [I]k[/I]=9=1+8=4+5): for 17824 primes [I]M[SUB]p[/SUB][/I] mod (2[I]p[/I]+1) = 0, for 6240 primes [I]M[SUB]p[/SUB][/I] mod (8[I]p[/I]+1) = 0, for 4931 primes [I]M[SUB]p[/SUB][/I] mod (10[I]p[/I]+1) = 0, and for 2002 primes [I]M[SUB]p[/SUB][/I] mod (16[I]p[/I]+1) = 0, so that 17824+6240+4931+2002-30369=628 Mersenne numbers have more than two factors;

[I]k[/I]=10: None;

[I]k[/I]=11: 149424 (for which [I]p[/I] mod 4 = 1 and [I]p[/I] mod 6 = 1), however, 6898 primes are already counted for [I]k[/I]=3 and [I]k[/I]=8 as follows (note that [I]k[/I]=11=3+8): for 5127 primes [I]M[SUB]p[/SUB][/I] mod (6[I]p[/I]+1) = 0, and for 1854 primes [I]M[SUB]p[/SUB][/I] mod (16[I]p[/I]+1) = 0, so that 5127+1854-6898=83 Mersenne numbers have more than two factors;
...

Hi,

I noticed something about the prime of the form p and 8p+1 and their divisibility by 2^p-1

If p = ((2a-1)^2+64(2b-1)^2-1)/8 and 8p+1 = (2a-1)^2+64(2b-1)^2, then 8p+1 divides 2^p-1

To find the exponent I use this code on PARI GP :

for(a=1, 1000, for(b=1, 1000, if(isprime((((2*a-1)^2+64*(2*b-1)^2-1)/8))&&isprime((2*a-1)^2+64*(2*b-1)^2), print(((2*a-1)^2+64*(2*b-1)^2-1)/8))))

But I don't how to sort by increasing order on PARI GP :confused:

I don't know if it's useful and I didn't found a counterexample but this interesting I guess :smile:

[QUOTE=kijinSeija;610882]I noticed something about the prime of the form p and 8p+1 and their divisibility by 2^p-1[/QUOTE]
It is actually viceversa :razz:, 2^p-1 is divisible by 8p+1.

And yes, this is an interesting find, I was not aware of. Up to now, we don't have a result that says anything about small factors of mersenne for exponents p which are prime and 1 (mod 4). For p=3 (mod 4) we have the SG result (if q=2p+1 is prime and p is 3 mod 4, than q divides m=2^p-1). But there is no similar result known to me which is touching prime p which are 1 (mod 4). If the "trick" behind of those formulas (which I didn't check yet) can be proved, this is an interesting result, with some mild theoretic value.

And no, this is not "useful" in practice, there is no practical value, the factors it uncovers are very small, only 8 times the value of p, which are eliminated by initial sieving/TF in the first millisecond (for k=4, in q=2kp+1). :sad:

Related to "sorting" in pari, you can add all the things to a list and use the sorting functions, if you need, or put everything in a file and sort it externally, but this effort is not really justified if you observe that the part coming from your "b" is much higher than the part from "a", so if you move b to external loop, they come out pretty sorted...

[CODE]for(b=1, 100, for(a=1, 100, q=(2*a-1)^2+64*(2*b-1)^2; p=(q-1)/8; if(isprime(p)&&isprime(q), print(q", divides 2^"p"-1"))))[/CODE](I also fixed a bit your calculation so you don't need to waste time calculating the same thing over and over, and also print both q and p. Note that there is no insurance of the fact that this is true, unless proved. You can add the "&&Mod(2,q)^p=1" in that "if" condition, and check if the resulted list is the same.

Edit:

Ok. Using these 3 lines, one by one, in order, we get:
[CODE]gp> cnt=0; for(b=1, 1000, for(a=1, 1000, q=(2*a-1)^2+64*(2*b-1)^2; p=(q-1)/8; if(isprime(p)&&isprime(q), cnt++; print(cnt": "q", "p))))
(6421 results are printed)
gp> cnt=0; for(b=1, 1000, for(a=1, 1000, q=(2*a-1)^2+64*(2*b-1)^2; p=(q-1)/8; if(isprime(p)&&isprime(q)&&Mod(2,q)^p==1, cnt++; print(cnt": "q", "p))))
(6421 results are printed)

gp> cnt=0; for(b=1, 1000, for(a=1, 1000, q=(2*a-1)^2+64*(2*b-1)^2; p=(q-1)/8; if(isprime(p)&&isprime(q)&&Mod(2,q)^p==1&&Mod(p,4)==1, cnt++; print(cnt": "q", "p))))
(3420 results are printed)[/CODE]


Buddy, you are onto something...

[QUOTE=kijinSeija;610882]Hi,

I noticed something about the prime of the form p and 8p+1 and their divisibility by 2^p-1

If p = ((2a-1)^2+64(2b-1)^2-1)/8 and 8p+1 = (2a-1)^2+64(2b-1)^2, then 8p+1 divides 2^p-1[/QUOTE]

This is equivalent to saying that if 8p+1 is prime and of the form (2a-1)^2+64(2b-1)^2, then 2 is an 8th power mod 8p+1.

You've rediscovered an old result on when 2 is an 8th power modulo a prime. Reuschle (1856) stated, and [URL="https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/plms/s2-9.1.244"]Western (1911) proved[/URL], that if q is a prime of the form 8k+1:
- If k is even, then 2 is an 8th power mod q if and only if q is of the form x^2 + 256y^2
- If k is odd, then 2 is an 8th power mod q if and only if q is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2.

Here we are in the k odd case, and your (2a-1)^2+64(2b-1)^2 exactly corresponds to saying that 8p+1 is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2. So in fact we can strengthen your statement to an "if and only if".

Ok thanks for your answer I understand a little more now. :grin:

Do you think you can prove the same thing about Wagstaff composite numbers ?

I found than if 8p+1 = 256a^2+(2*b-1)^2 and p and 8p+1 is prime, then 8p+1 divides (2^p+1)/3.

[CODE] cnt=0; for(b=1, 1000, for(a=1, 1000, q=256*(a)^2+(2*b-1)^2; p=(q-1)/8; if(isprime(p)&&isprime(q), cnt++; print(cnt": "q", "p))))[/CODE]

So I think the proof the same with some minor change.

[QUOTE=charybdis;610957]This is equivalent to saying that if 8p+1 is prime and of the form (2a-1)^2+64(2b-1)^2, then 2 is an 8th power mod 8p+1.

You've rediscovered an old result on when 2 is an 8th power modulo a prime. Reuschle (1856) stated, and [URL="https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/plms/s2-9.1.244"]Western (1911) proved[/URL], that if q is a prime of the form 8k+1:
- If k is even, then 2 is an 8th power mod q if and only if q is of the form x^2 + 256y^2
- If k is odd, then 2 is an 8th power mod q if and only if q is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2.

Here we are in the k odd case, and your (2a-1)^2+64(2b-1)^2 exactly corresponds to saying that 8p+1 is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2. So in fact we can strengthen your statement to an "if and only if".[/QUOTE]Thank you very much for digging up a pertinent reference on when 2 is an 8[sup]th[/sup] power (mod q) when q is congruent to 1 (mod 8).

An even older result is the criterion for when 2 is a biquadratic (fourth power) residue (mod q); namely, when

q = x^2 + 64*y^2 (x, y positive integers).

As already indicated, however, it is much, [i]much[/i] quicker to determine whether q = 8*p + 1 divides 2^p - 1 by modulo arithmetic, than it is to determine whether q is of the appropriate quadratic form.

I would expect that q = 8*p + 1 divides 2^p - 1 for about a quarter of the primes p for which q = 8*p + 1 is prime. Unfortunately, [i]which[/i] quarter is not predictable using linear congruences.

I don't necessarily trust my thinking here, so someone may want to check on the proportion...

[b]EDIT:[/b] I checked it myself for p < 10[sup]8[/sup], with the results following:
[code]? c1=0;c2=0;forprime(p=3,100000000,q=8*p+1;if(ispseudoprime(q),c1++;if(Mod(2,q)^p-1==0,c2++)));print(c1" "c2" "1.*c2/c1)

392989 98264 0.25004262205812376427838947146103326047[/code]

[QUOTE=charybdis;610957]This is equivalent to...[/QUOTE]
Very :goodposting: :tu:

[QUOTE=kijinSeija;610959]Ok thanks for your answer I understand a little more now. :grin:

Do you think you can prove the same thing about Wagstaff composite numbers ?

I found than if 8p+1 = 256a^2+(2*b-1)^2 and p and 8p+1 is prime, then 8p+1 divides (2^p+1)/3.
<snip>[/QUOTE]Reread the explanatory post by [b][color=blue]charybdis[/color][/b]. Also note the result I mentioned about when 2 is a fourth power residue (mod q). The result you state is an easy consequence of your hypothesis and those results.

A repetitive pattern in observed after [I]k[/I] = 12 for the primes [I]p[/I] and the values of [I]k[/I] for which primes 2[I]kp[/I] + 1 can be found that divide the Mersenne numbers 2[I][SUP]p[/SUP][/I] - 1,
see the previous posts #29 and #30 at [URL]https://www.mersenneforum.org/showpost.php?p=606844&postcount=29[/URL] and [URL]https://www.mersenneforum.org/showpost.php?p=607412&postcount=30[/URL].

For example, for [I]p[/I] = 1277 (where [I]p[/I] mod 4 = 1 and [I]p[/I] mod 6 = 5), possible prime factors that divide M[M]1277[/M] have to be of the following forms (note that 3 + 4 = 7 and 3 × 4 = 12):

2(12[I]m[/I]+3)[I]p[/I] + 1,
2(12[I]m[/I]+4)[I]p[/I] + 1,
2(12[I]m[/I]+7)[I]p[/I] + 1, and
2(12([I]m[/I]+1))[I]p[/I] + 1, [I]m[/I] = 0, 1, 2,...

It seems that the primes of the forms

2(12[I]m[/I]+1)[I]p[/I] + 1,
2(12[I]m[/I]+5)[I]p[/I] + 1,
2(12[I]m[/I]+8)[I]p[/I] + 1,
2(12[I]m[/I]+9)[I]p[/I] + 1, and
2(12[I]m[/I]+11)p + 1, [I]m[/I] = 0, 1, 2,...,

cannot be factors of M[M]1277[/M].

Can you also work this stuff (mod 4620) ?
Or, start with (mod 420) first...

[QUOTE=Dobri;611207]A repetitive pattern in observed after [I]k[/I] = 12 for the primes [I]p[/I] and the values of [I]k[/I] for which primes 2[I]kp[/I] + 1 can be found that divide the Mersenne numbers 2[I][SUP]p[/SUP][/I] - 1,
see the previous posts #29 and #30 at [URL]https://www.mersenneforum.org/showpost.php?p=606844&postcount=29[/URL] and [URL]https://www.mersenneforum.org/showpost.php?p=607412&postcount=30[/URL].

For example, for [I]p[/I] = 1277 (where [I]p[/I] mod 4 = 1 and [I]p[/I] mod 6 = 5), possible prime factors that divide M[M]1277[/M] have to be of the following forms (note that 3 + 4 = 7 and 3 × 4 = 12):

2(12[I]m[/I]+3)[I]p[/I] + 1,
2(12[I]m[/I]+4)[I]p[/I] + 1,
2(12[I]m[/I]+7)[I]p[/I] + 1, and
2(12([I]m[/I]+1))[I]p[/I] + 1, [I]m[/I] = 0, 1, 2,...

It seems that the primes of the forms

2(12[I]m[/I]+1)[I]p[/I] + 1,
2(12[I]m[/I]+5)[I]p[/I] + 1,
2(12[I]m[/I]+8)[I]p[/I] + 1,
2(12[I]m[/I]+9)[I]p[/I] + 1, and
2(12[I]m[/I]+11)p + 1, [I]m[/I] = 0, 1, 2,...,

cannot be factors of M[M]1277[/M].[/QUOTE]For odd p we have (2^((p+1)/2))^2 == 2 (mod q) for every prime factor q of 2^p - 1, so 2 is a quadratic residue (mod q). As is well known, this means that q == 1 or 7 (mod 8).

It is also well known that if p is an odd prime, and q divides 2^p - 1, then q = 2*k*p + 1 for some positive integer k. If p == 1 (mod 4) we then have 2*k*p + 1 == 2*k + 1 == 1 or 7 (mod 8). Thus, k == 0 or 3 (mod 4).

For p == 1 (mod 4), this automatically rules out q = 2*k*p + 1 for k = 12*m + 1, 12*m + 5, or 12*m + 9 since 2*k*p + 1 == 3 (mod 8) for such k.

[QUOTE=Dobri;611207]

2(12[I]m[/I]+3)[I]p[/I] + 1,
2(12[I]m[/I]+4)[I]p[/I] + 1,
2(12[I]m[/I]+7)[I]p[/I] + 1, and
2(12([I]m[/I]+1))[I]p[/I] + 1, [I]m[/I] = 0, 1, 2,...

[/QUOTE]




I found this from an empirical observation but I think it is easy to prove that taking a prime number p

we have (2^p - 1)=7 (mod 8) or also

(2^p - 1)=1+2*p+8*p*k if p%4==3 , where % is the modulo operator

or (2^p - 1)=1+6*p+8*p*k if p%4==1


and if (2^p - 1)=N1*N2 then N1=1 (mod 8) and N2=7 (mod 8) but also N1=1 (mod 2*p) and N2=1 (mod 2*p)

then the only possible solution to find possible factors is this

N1=1+8*p*k1 and

N2=1+2*p+8*p*k2 if p%4==3 or N2=1+6*p+8*p*k2 if p%4==1

so if we exclude multiples of 3 for m>=0

N1=1+24*p*(m+1) or 1+16*p+24*p*m if p%6=1
N1=1+24*p*(m+1) or 1+ 8*p+24*p*m if p%6=5

and

N2=1+10*p+24*p*m or 1+18*p+24*p*m if p%6=1 and p%4==3
N2=1+ 2*p+24*p*m or 1+18*p+24*p*m if p%6=5 and p%4==3



or



N2=1+6*p+24*p*m or 1+22*p+24*p*m if p%6=1 and p%4==1
N2=1+6*p+24*p*m or 1+14*p+24*p*m if p%6=5 and p%4==1

[QUOTE=User140242;611220]
then the only possible solution to find possible factors is this
N1=1+8*p*k1 and
N2=1+2*p+8*p*k2 if p%4==3 or N2=1+6*p+8*p*k2 if p%4==1
[/QUOTE]
OK, perfect, using the standard notation, where the factors q of m=2^p-1 are of the form q=2kp+1, and in the same time they are either 1 or -1 (mod 8), you just found the classes of k, depending on the classes of p, (mod 4).
As p is prime, it can only be 1 or 3 (mod 4), because it can not be even.
1. if p=1 (mod 4), then k can only be 0 or 3 (mod 4).
2. if p=3 (mod 4), then k can only be 0 or 1 (mod 4).

Now stop here, the other stuff (mod 6, etc.) is not useful, as it doesn't reduce the searching space.

Next step is to put 3 into equation, and find the classes of k, depending on the classes of p (mod 12).
As p is prime, it can only be 1, 5, 7, or 11 (mod 12).
What are the classes of k, in each case?
1. when p=1 (mod 12), k can only be ??? (mod 12)
2. when p=5 (mod 12), k can only be ??? (mod 12)
3. when p=7 (mod 12), k can only be ??? (mod 12)
4. when p=11 (mod 12), k can only be ??? (mod 12)
Fill in the question marks. (You actually did this already, but in somehow obfuscated way, with (mod 4) and (mod 6)).

Next step is to put 5 into equation, and find the classes of k, depending on the classes of p (mod 60).
There are 16 classes of p (mod 60).

Next step is to put 7 into equation, and find the classes of k, depending on the classes of p (mod 420).
That is what (and why) I was asking you to do, in my previous post.
There are 96 classes of p (mod 420).

To find more about these numbers, and where do they come from, you can read about Euler's Phy function.

Next step is to put 11 into equation, and find the classes of k, depending on the classes of p (mod 4620).
There are 960 classes of p (mod 4620).

If you succeed to reach this point, congratulations, you just discovered how mfaktc and its relatives work...
:party:

[QUOTE=LaurV;611260]

Now stop here, the other stuff (mod 6, etc.) is not useful, as it doesn't reduce the searching space.

[/QUOTE]
If you use the result in a wheel sieve with a bW basis, you can call classes or possible remainders (modulo bW).

If a basis bW=8*p is used, the possible factors are of the type q = 1+8*k*p and q=1+2*p+8*k*p if p%4==3 or q=1+6*p+8*k*p if p%4==1.
so there are 2 classes or possible remainders [1 , 1+2*p] if p%4==3 or [1 , 1+6*p] if p%4==1.

If a basis bW=24*p is used as mentioned above, the possible factors are:


[QUOTE]

N1=1+24*p*(m+1) or 1+16*p+24*p*m if p%6=1
N1=1+24*p*(m+1) or 1+ 8*p+24*p*m if p%6=5

and

N2=1+10*p+24*p*m or 1+18*p+24*p*m if p%6=1 and p%4==3
N2=1+ 2*p+24*p*m or 1+18*p+24*p*m if p%6=5 and p%4==3

or

N2=1+6*p+24*p*m or 1+22*p+24*p*m if p%6=1 and p%4==1
N2=1+6*p+24*p*m or 1+14*p+24*p*m if p%6=5 and p%4==1[/QUOTE]
so there are 4 possible classes or remainders based on the value of p%4 and p%6 in fact combining the results of p%4 and p%6 is the same as evaluating p%12.

[QUOTE=User140242;611263]so there are 4 possible classes or remainders based on the value of p%4 and p%6 in fact combining the results of p%4 and p%6 is the same as evaluating p%12.[/QUOTE]

[QUOTE=LaurV;611260](You actually did this already, but in somehow obfuscated way, with (mod 4) and (mod 6)).
[/QUOTE]

Bingo!

You still get 4 classes to test for factors; to reduce more the percentages, you need new primes in the modulo.

Sorry, busy here around, I just looked for [URL="https://www.mersenneforum.org/showthread.php?t=17126"]this thread[/URL], which you should read carefully, especially from post #32 onward, till the end.

[QUOTE=LaurV;611265]Sorry, busy here around, I just looked for [URL="https://www.mersenneforum.org/showthread.php?t=17126"]this thread[/URL], which you should read carefully, especially from post #32 onward, till the end.[/QUOTE]


In addition you can calculate the possible remainders and automatically you can find the possible factors:

[CODE]
tf_c(p,fromk=0,tok=10000)=
{
PrimesBase=[2,3,5,7,11];
n_PB=5;
PrimesBaseProd=2;
for(i=1,n_PB,PrimesBaseProd*=PrimesBase[i];);
bW=2*p*PrimesBaseProd;
RW=List();
listput(RW,1);
for(i=1,PrimesBaseProd-1,for(j=1,n_PB,;if(Mod(1+2*p*i,PrimesBase[j])^1==0,break;);if ((j==n_PB)&&(Mod(1+2*p*i,PrimesBase[j])^1!=0)&&(Mod(1+2*p*i,8)^1==1||Mod(1+2*p*i,8)^1==7),listput(RW,1+2*p*i););););
nR=length(RW);
for(k=fromk, tok, for(i=1,nR,q=RW[i]+bW*k; if(Mod(2,q)^p==1, if(q>1,print("M"p" has a factor: "q); break;));));
}

[/CODE]

Why would you do that? It will take a lot of time to build that list, and it will find a lot of unneeded composite factors which you need to factor later to find the real prime factors.

[QUOTE=LaurV;611310]Why would you do that? It will take a lot of time to build that list, and it will find a lot of unneeded composite factors which you need to factor later to find the real prime factors.[/QUOTE]


You can use n_PB as a parameter and if you check the number of remainders that nR uses they are 2 if n_PB = 1, 4 if n_PB = 2, 16 if n_PB = 3, 96 if n_PB = 4 and 960 if n_PB = 5.


That is, it is the same job as creating the table but you can perform an automatic operation as needed.


Of course with this method it checks (tok-fromk)*nR elements instead with forstep it checks (tok-fromk)/nR elements but the factors are the same only the size of the interval changes.


Finally, multiples of small factors can be easily eliminated for each row.



Here you find an example with 2 classes and to speed up we use two vectors for the two classes:
[URL]https://gist.github.com/user140242/04a9a58713695631c2d2738788bb1cae[/URL]

[QUOTE=User140242;611314]

Finally, multiples of small factors can be easily eliminated for each row.
[/QUOTE]






To extend the example for classes greater than 2 for each class we must use this:

It is possible to eliminate the multiples of the small factors p_j>PrimesBase[n_PB] with p_j<bW and p_j!=p and p_j!=RW[n]
for each RW[i] take a vector FACTOR of size dim_step+1 with dim_step=(tok-fromk) initially set to True

all multiples of p_j can be set to False in this way:



[CODE]
r_t1=Euclidean_Diophantine(bW,p_j); //function return y in Diophantine equation bW * x + p_j * y = 1
r_t=(r_t1*RW[i])%bW;
if (r_t>0)
r_t-=bW;
C2=(-bW+p_j)*r_t/bW;
C1=r_t-bW+p_j;
for (m =bW+C1+C2; m<=dim_step && m>=0; m += p_j)
FACTOR[m] = false;
[/CODE]and then use it in this way to check for possible factors:


[CODE]
for(k=0;k<=dim_step;k++)
if (FACTOR[k])
{
D=RW[i]+bW*k;
....
}[/CODE]

[QUOTE=Dr Sardonicus;611217]...
For p == 1 (mod 4), this automatically rules out q = 2*k*p + 1 for k = 12*m + 1, 12*m + 5, or 12*m + 9 since 2*k*p + 1 == 3 (mod 8) for such k.[/QUOTE]
Thanks, this nicely eliminates the cases for [I]k[/I] = 12[I]m[/I] + 1, 12[I]m[/I] + 5, and 12[I]m[/I] + 9 indeed.
[QUOTE=Dobri;611207]...
2(12[I]m[/I]+8)[I]p[/I] + 1,
...
2(12[I]m[/I]+11)p + 1, [I]m[/I] = 0, 1, 2,...,

cannot be factors of M[M]1277[/M].[/QUOTE]
However, the cases for [I]k[/I] = 12[I]m[/I] + 8 and 12[I]m[/I] + 11 still need a theoretical interpretation.
I do not have a counterexample with [I]p[/I] mod 6 = 5 that would result in a prime [I]q[/I] = 2[I]kp [/I]+ 1 for [I]k[/I] = 12[I]m[/I] + 8 or 12[I]m[/I] + 11 that divides 2[I][SUP]p[/SUP][/I] - 1.
Currently, I am checking the known prime factors in the GIMPS database for a counterexample.
Such a counterexample with [I]p[/I] mod 6 = 5 could be rare or does not exist.

[QUOTE=Dobri;611321]However, the cases for [I]k[/I] = 12[I]m[/I] + 8 and 12[I]m[/I] + 11 still need a theoretical interpretation.
I do not have a counterexample with [I]p[/I] mod 6 = 5 that would result in a prime [I]q[/I] = 2[I]kp [/I]+ 1 for [I]k[/I] = 12[I]m[/I] + 8 or 12[I]m[/I] + 11 that divides 2[I][SUP]p[/SUP][/I] - 1.
Currently, I am checking the known prime factors in the GIMPS database for a counterexample.
Such a counterexample with [I]p[/I] mod 6 = 5 could be rare or does not exist.[/QUOTE]

These have the simplest explanation of all. If p and k are both 2 mod 3 then 2kp+1 is divisible by 3 and so can't be prime.

[QUOTE=charybdis;611323]These have the simplest explanation of all. If p and k are both 2 mod 3 then 2kp+1 is divisible by 3 and so can't be prime.[/QUOTE]
Thanks, this flawlessly eliminates the cases for [I]k[/I] = 12[I]m[/I] + 8 and 12[I]m[/I] + 11 indeed.
Also, divisibility by 3 is observed for [I]k[/I] = 12[I]m[/I] + 5 since 2(12[I]m[/I] + 5)(6[I]n[/I] + 5) + 1 gives the coefficient 2×5×5 + 1 = 51 which is divisible by 3.
Despite the equivalence between 2 mod 3 and 5 mod 6 (and between 1 mod 3 and 1 mod 6) for prime number considerations, I still use 'mod 6' for uniformity with a few other threads.

What I am trying to evaluate is the [COLOR="Red"]additive[/COLOR] dependence between the values of [I]k[/I] for several factors for a given Mersenne number.
On the basis of [U]quite limited[/U] observations for [I]k[/I] up to 11 (see posts #29 and #30), the values of [I]k[/I] for another factor are obtained as follows:
- the sum of a prime number (or 1) and 2[I][SUP]n[/SUP] [/I] such as 5 + 2[SUP]2[/SUP] = 3[SUP]2[/SUP] and 1 + 2[SUP]3[/SUP] = 3[SUP]2[/SUP];
- the sum of 1 and a prime number giving 2[I][SUP]n[/SUP] [/I] such as 1 + 3 = 2[SUP]2[/SUP] and 1 + 7 = 2[SUP]3[/SUP];
- the sum of two prime numbers giving 2[I][SUP]n[/SUP] [/I] such as 3 + 5 = 2[SUP]3[/SUP]; or
- the sum of 2[I][SUP]n[/SUP] [/I] and a prime number giving a prime number such as 2[SUP]2[/SUP] + 3 = 7 and 2[SUP]3[/SUP] + 3 = 11.

The exhaustive computations for [I]k[/I] = 12 are ongoing. The custom source code was modified to collect data not only for [I]p[/I] < 10[SUP]9[/SUP] but also for [I]p[/I] < 2[SUP]30[/SUP].

For [I]k[/I] = 12, all possible pairs of two factors for a given Mersenne number are observed with Δ[I]k[/I] = 1, 3, 4, 5, 7, 8, 9, and 11, where Δ[I]k[/I] = [I]k[/I][SUB]2[/SUB] - [I]k[/I][SUB]1[/SUB] with [I]k[/I][SUB]2[/SUB] = 12 and [I]k[/I][SUB]2[/SUB] > [I]k[/I][SUB]1[/SUB]. No cases of three factors for a given Mersenne number are found.

For [I]k[/I] = 13, only cases with Δ[I]k[/I] = 1, 4, 9, and 12 for a given Mersenne number are found, where Δ[I]k[/I] = [I]k[/I][SUB]2[/SUB] - [I]k[/I][SUB]1[/SUB] with [I]k[/I][SUB]2[/SUB] = 13 and [I]k[/I][SUB]2[/SUB] > [I]k[/I][SUB]1[/SUB]. Here 1 + 12 = 13 and 4 + 9 = 13.

[QUOTE=Dobri;611616]For [I]k[/I] = 12, all possible pairs of two factors for a given Mersenne number are observed with Δ[I]k[/I] = 1, 3, 4, 5, 7, 8, 9, and 11, where Δ[I]k[/I] = [I]k[/I][SUB]2[/SUB] - [I]k[/I][SUB]1[/SUB] with [I]k[/I][SUB]2[/SUB] = 12 and [I]k[/I][SUB]2[/SUB] > [I]k[/I][SUB]1[/SUB]. No cases of three factors for a given Mersenne number are found.

For [I]k[/I] = 13, only cases with Δ[I]k[/I] = 1, 4, 9, and 12 for a given Mersenne number are found, where Δ[I]k[/I] = [I]k[/I][SUB]2[/SUB] - [I]k[/I][SUB]1[/SUB] with [I]k[/I][SUB]2[/SUB] = 13 and [I]k[/I][SUB]2[/SUB] > [I]k[/I][SUB]1[/SUB]. Here 1 + 12 = 13 and 4 + 9 = 13.[/QUOTE]

It is possible to find the values ​​of Δk like this:

if you use a basis bW=2*p*k we have

for k = 12 = 2*2*3

q = r + bW*d where r are the possible remainders with 0 <= r <bW if we consider that q = 1 mod 2p then r = 1 mod 2p

hence r = 1 + 2p*b with 0 <= b < k

so for example if k = 12 and p = 29 the possible remainders are

(1, 59, 117, 175, 233, 291, 349, 407, 465, 523, 581, 639)

from these remainders you have to remove those that have factors in common with bW or remove the multiples of 3 since r = 1 mod 2p

and since bW = 0 mod 8 we must consider that it must be r = 7 mod 8 or r = 1 mod 8 therefore remain

(1, 175, 233, 407) so if you take the indices we find Δk or we consider (r-1)/2/p

(0,3,4,7)

for p = 31 we find (1, 311, 497, 559) or (0, 5, 8, 9)

for p = 37 we find (1, 223, 593, 815) or (0, 3, 8, 11)

for p = 47 we find (1, 95, 377, 847) or (0, 1, 4, 9)

as mentioned in a previous post there are 4 cases based on the value of p%4 and p%6

if k = 13 then bW is not divisible by 8 it is not convenient to use it in any case the procedure does not change

surely you have forgotten some cases for example p=37 and q=223 then k1 = 3 and Δk = 13-3 = 10

[QUOTE=User140242;611621]...

surely you have forgotten some cases for example p=37 and q=223 then k1 = 3 and Δk = 13-3 = 10[/QUOTE]
No cases have been forgotten.
In the quoted example, 2[SUP]37[/SUP]-1 = 137438953471, then 13743895347 / 223 = 616318177, and [I]k[/I][SUB]2[/SUB] = (616318177-1)/(2×37) = 8328624, thus Δk = 8328624 - 3 = 8328621 = 3×7×396601, which is unrelated to [I]k[/I] = 13.

[QUOTE=Dobri;611381]<snip>
On the basis of [U]quite limited[/U] observations for [I]k[/I] up to 11 (see posts #29 and #30), the values of [I]k[/I] for another factor are obtained as follows:
- the sum of a prime number (or 1) and 2[I][SUP]n[/SUP] [/I] such as 5 + 2[SUP]2[/SUP] = 3[SUP]2[/SUP] and 1 + 2[SUP]3[/SUP] = 3[SUP]2[/SUP];
- the sum of 1 and a prime number giving 2[I][SUP]n[/SUP] [/I] such as 1 + 3 = 2[SUP]2[/SUP] and 1 + 7 = 2[SUP]3[/SUP];
- the sum of two prime numbers giving 2[I][SUP]n[/SUP] [/I] such as 3 + 5 = 2[SUP]3[/SUP]; or
- the sum of 2[I][SUP]n[/SUP] [/I] and a prime number giving a prime number such as 2[SUP]2[/SUP] + 3 = 7 and 2[SUP]3[/SUP] + 3 = 11.[/quote][QUOTE=Dobri;611616]<snip>
For [I]k[/I] = 13, only cases with Δ[I]k[/I] = 1, 4, 9, and 12 for a given Mersenne number are found, where Δ[I]k[/I] = [I]k[/I][SUB]2[/SUB] - [I]k[/I][SUB]1[/SUB] with [I]k[/I][SUB]2[/SUB] = 13 and [I]k[/I][SUB]2[/SUB] > [I]k[/I][SUB]1[/SUB]. Here 1 + 12 = 13 and 4 + 9 = 13.[/QUOTE]In the sum 4 + 9 = 13 neither 4 nor 9 is prime, and neither 4 nor 9 is equal to 1, so the sum does not fit any of the categories you list.

[QUOTE=Dr Sardonicus;611628]In the sum 4 + 9 = 13 neither 4 nor 9 is prime, and neither 4 nor 9 is equal to 1, so the sum does not fit any of the categories you list.[/QUOTE]
Affirmative, this is a new category, although 4 = 2[SUP]2[/SUP] and 9 was already included as 5 + 2[SUP]2[/SUP] = 9 in the expanding scheme of values of [I]k[/I].
A distant loose analogy with a growing Pascal's triangle comes in mind...
It is to be seen to what extent 2[I][SUP]n[/SUP][/I], [I]n[/I] = 2, 3,..., would appear in the additive scheme with the increase of the values of [I]k[/I].

[I]k[/I] = 14: None;
[I]k[/I] = 15: 3 + 12 = 7 + 2[SUP]3[/SUP] = 11 + 2[SUP]2[/SUP] = 15.

[I]k[/I] = 16: 1 + 15 = 3 + 13 = 4 + 12 = 7 + 9 = 16.

[I]k[/I] = 17: 5 + 12 = 2[SUP]3[/SUP] + 9 = 17;
[I]k[/I] = 18: None.

[QUOTE=Dobri;611625]No cases have been forgotten.
In the quoted example, 2[SUP]37[/SUP]-1 = 137438953471, then 13743895347 / 223 = 616318177, and [I]k[/I][SUB]2[/SUB] = (616318177-1)/(2×37) = 8328624, thus Δk = 8328624 - 3 = 8328621 = 3×7×396601, which is unrelated to [I]k[/I] = 13.[/QUOTE]


I didn't quite understand what you were looking for but the only possible values ​​of k%12 are these:

if p%12 == 1 then k%12 = (0, 3, 8, 11)
if p%12 == 5 then k%12 = (0, 3, 4, 7)
if p%12 == 7 then k%12 = (0, 5, 8, 9)
if p%12 == 11 then k%12 = (0, 1, 4, 9).


for example if k=13 then k%12=1 then the possible cases of have when p%12=11
and possible k%12 are (0, 1, 4, 9) with k%12=0 corresponding to 12
so you find that only cases 0+1=0+12+1=13 and 4+9=13


if k=14 then k%12=2 there are no cases

if k=15 then k%12=3 the possible cases are
p%12=1 then k%12=(0, 3, 8, 11)
and p%12=5 then k%12=(0, 3, 4, 7)
from which you find that only cases 3+0 or 3+0+12=15 and 4+11=15 and 7+8=15

if k=16 then k%12=4 the possible cases are
p%12=11 then k%12=(0, 1, 4, 9)
and p%12=5 then k%12=(0, 3, 4, 7)
from which you find that only cases 3+1=3+12+1=15+1=16 and 7+9=16 and 4+0=4+0+12=16 and 3+1=3+1+12=3+13=16

...
[I]k[/I] = 19: 3 + 2[SUP]4[/SUP] = 2[SUP]2[/SUP] + 15 = 7 + 12 = 19;
[I]k[/I] = 20: 3 + 17 = 5 + 15 = 2[SUP]3[/SUP] + 12 = 9 + 11 = 20;
[I]k[/I] = 21: 1 + 20 = 2[SUP]2[/SUP] + 17 = 5 + 2[SUP]4[/SUP] = 2[SUP]3[/SUP] + 13 = 9 + 12 = 21;
[COLOR="Red"][I]k[/I] = 22: None;[/COLOR]
[I]k[/I] = 23: 3 + 20 = 2[SUP]3 [/SUP]+ 15 = 11 + 12 = 23;
[I]k[/I] = 24: 1 + 23 = 3 + 21 = 2[SUP]2[/SUP] + 20 = 5 + 19 = 7 + 17 = 2[SUP]3[/SUP] + 2[SUP]4[/SUP] = 9 + 15 = 2×12 = 24;
[I]k[/I] = 25: 1 + 24 = 2[SUP]2[/SUP] + 21 = 9 + 2[SUP]4[/SUP] = 12 + 13 = 25;
[COLOR="red"][I]k[/I] = 26: None;[/COLOR]
[I]k[/I] = 27: 3 + 24 = 2[SUP]2[/SUP] + 23 = 7 + 20 = 2[SUP]3[/SUP] +19 = 11 + 2[SUP]4[/SUP] = 12 + 15 = 27;
[I]k[/I] = 28: 1 + 27 = 3 + 25 = 2[SUP]2 [/SUP]+ 24 = 7 + 21 = 9 + 19 = 12 + 2[SUP]4[/SUP] = 13 + 15 = 28;
[I]k[/I] = 29: 5 + 24 = 2[SUP]3[/SUP] + 21 = 9 + 20 = 12 + 17 = 29;
[COLOR="red"][I]k[/I] = 30: None;[/COLOR]
[I]k[/I] = 31: 3 + 28 = 2[SUP]2[/SUP] + 27 = 7 + 24 = 12 + 19 = 15 + 2[SUP]4[/SUP] = 31;
[I]k[/I] = 32: 3 + 29 = 5 + 27 = 2[SUP]3[/SUP] + 24 = 9 + 23 = 11 + 21 = 12 + 20 = 15 + 17 = 32;
...
It is known that there are no factors 2[I]pk[/I] + 1 of Mersenne numbers for [I]k[/I] = 2(2[I]m[/I] + 1), [I]m[/I] = 0, 1, 2,...

The exhaustive computations indicate that [COLOR="Red"]if there is a factor 2[I]pk[/I][SUB]2[/SUB] + 1 of a Mersenne number 2[I][SUP]p[/SUP][/I] - 1 for a given pair of [I]k[SUB]2[/SUB][/I] and [I]p[/I], then there is no factor 2[I]pk[/I][SUB]1[/SUB] + 1 for said [I]p[/I] for the positive values of [I]k[/I][SUB]1[/SUB] = [I]k[/I][SUB]2[/SUB] - 2(2[I]m[/I] + 1), [I]m[/I] = 0, 1, 2,...[/COLOR].

[QUOTE=Dobri;611685]<snip>
The exhaustive computations indicate that [COLOR="Red"]if there is a factor 2[I]pk[/I][SUB]2[/SUB] + 1 of a Mersenne number 2[I][SUP]p[/SUP][/I] - 1 for a given pair of [I]k[SUB]2[/SUB][/I] and [I]p[/I], then there is no factor 2[I]pk[/I][SUB]1[/SUB] + 1 for said [I]p[/I] for the positive values of [I]k[/I][SUB]1[/SUB] = [I]k[/I][SUB]2[/SUB] - 2(2[I]m[/I] + 1), [I]m[/I] = 0, 1, 2,...[/COLOR].[/QUOTE]What a waste of computing power.

[QUOTE=Dr Sardonicus;611689]What a waste of computing power.[/QUOTE]
Agree. But let them discharge the energy. I went the same way for a while, 20 years ago :razz: (probably few other now-famous forumites too, hehe).

[QUOTE=Dr Sardonicus;611689]What a waste of computing power.[/QUOTE]
On the contrary, a waste of computing power was avoided.
This made it possible to obtain the results in post #62 much faster than the ones posted earlier.
After stumbling upon this result during the evaluation of pairs of factors, I was able to modify my custom source code and deal with Δ[I]k[/I] instead of 2[I]kp[/I]+1 == 1 or 7 (mod 8) using a single subtraction instead of addition and two multiplications which reduced the computation time.
For this reason, perhaps the statement in post #62 deserves the status of a [COLOR="Red"]lemma[/COLOR] despite its simple proof.

[QUOTE=Dobri;611733]On the contrary, a waste of computing power was avoided.
This made it possible to obtain the results in post #62 much faster than the ones posted earlier.
...
[/QUOTE]



In my opinion the result highlighted post #62 does not allow to exclude factors that are not possible in fact for example if k=16 and p=5 mod 12 it is also necessary to exclude the factors k2%12=1=16-15 and k2%12=9=16-7

with this code if you take (RW[i] -1)/2/P you can easily find the possible values ​​of k%PrimesBaseProd with PrimesBaseProd=12 if you set n_PB=2


[CODE]
#include <iostream>
#include <vector>
#include <cstdlib>
#include <stdint.h>

int main()
{

int64_t P=86000063;
int64_t PrimesBase[5]={2,3,5,7,11};
int n_PB = 5;

int64_t bW;
std::vector<int64_t> RW;
if (n_PB>1)
{
int64_t PrimesBaseProd=2;
for (int i=0; i<n_PB;i++)
PrimesBaseProd*=PrimesBase[i];
bW=2*P*PrimesBaseProd;
int64_t r_t1,r_t7;
int j;
r_t1=1;
r_t7=1+2*P;
if (P%4==1)
r_t7+=4*P;
for (int64_t k=1; k<=PrimesBaseProd/4;k++)
{
for (j=1;j<n_PB;j++)
if (r_t1%PrimesBase[j]==0)
break;
if (j==n_PB)
RW.push_back(r_t1);
for (j=1;j<n_PB;j++)
if (r_t7%PrimesBase[j]==0)
break;
if (j==n_PB)
RW.push_back(r_t7);
r_t1+=8*P;
r_t7+=8*P;
}
}
else
{
bW=8*P;
RW.push_back(1);
RW.push_back(1+2*P);
if (P%4==1)
RW[1]+=4*P;
}
int64_t nR=RW.size();


return 0;

}


[/CODE]

You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what? :razz:

[QUOTE=LaurV;611746]You just invented a very obfuscated way to compute Eulers's Totient (pari: eulerphi) function, or what? :razz:[/QUOTE]


If you are referring to post #66


To search for possible remainders q (modulo bW), proceed as described in post [URL="https://www.mersenneforum.org/showpost.php?p=611621&postcount=54"]#54[/URL]:

Set bW=2*p*k then k=bW/2/p=PrimesBaseProd=2*p1*p2*...*pn

if q is a possible factor

q=1+2*p*k1=RW[i]+bW*j with 0<=i<nR possibile remainder RW[i] = q (modulo bW)

then k1=(RW[i]-1)/2/p+(bW/2/p)*j with (RW[i]-1)/2/p = k1 (modulo bW/2/p) = k1 (mod k)

so if k=0(mod 4) then bW=0(mod 8) to speed up the search it is possible to evaluate only p=1(mod 4) or p=3(mod 4) cases in fact if r is a remainders then it must be r=1(mod 8) or r=7(mod 8):

for 0 <= a < k/4

r=1+8*p*a

and

r=1+2*p+8*p*a if p%4=3 or r=1+6*p+8*p*a if p%4=1

from these remainders you have to remove those that have factors in common with bW

so since r=1(mod 2*p) if p1=2 remove those are divisible by p2,...,pn


Note that as mentioned in a previous post the value of nR depends on n_PB:

nR=2 if n_PB = 1, nR=4 if n_PB = 2, nR=16 if n_PB = 3, nR=96 if n_PB = 4 and nR=960 if n_PB = 5

and if you have no memory problems you can add prime numbers > 11 in PrimesBase and increase n_PB although I don't know if there are any advantages in terms of speed.

In reference to your question in #67 the eulerphi function maybe allows you to calculate nR but I am interested in the possible remainders so you can use q = RW[i] + bW * j.


For example it is possible to calculate the vector v used in [URL="https://www.mersenneforum.org/showpost.php?p=319334&postcount=35"]Trial factoring, part 2 of 3[/URL] simply by setting n_PB=2 and adding this piece of code


[CODE]
std::vector<int64_t> v;
v.push_back((RW[1]-1)/2/P);
for (int64_t i=2;i<nR;i++)
v.push_back((RW[i]-1)/2/P-(RW[i-1]-1)/2/P);
v.push_back(PrimesBaseProd-(RW[nR-1]-1)/2/P);

[/CODE]

[QUOTE=User140242;611737]In my opinion the result highlighted post #62 does not allow to exclude factors that are not possible in fact for example if k=16 and p=5 mod 12 it is also necessary to exclude the factors k2%12=1=16-15 and k2%12=9=16-7...[/CODE][/QUOTE]
Post #62 is concerned with arbitrary primes [I]p[/I], placing additional conditions on [I]p[/I] gives further refinements indeed.

[QUOTE=Dobri;611773]Post #62 is concerned with arbitrary primes [I]p[/I], placing additional conditions on [I]p[/I] gives further refinements indeed.[/QUOTE]You disregarded the careful explanation in [url=https://www.mersenneforum.org/showpost.php?p=611260&postcount=42]this post[/url] and reference to more explanation in [url=https://www.mersenneforum.org/showpost.php?p=611265&postcount=45]this post[/url], and continued to do unnecessary computations

[quote=Dobri;611321]However, the cases for k = 12m + 8 and 12m + 11 still need a theoretical interpretation.
I do not have a counterexample with p mod 6 = 5 that would result in a prime q = 2kp + 1 for k = 12m + 8 or 12m + 11 that divides 2p - 1.
Currently, I am checking the known prime factors in the GIMPS database for a counterexample.
Such a counterexample with p mod 6 = 5 could be rare or does not exist.[/quote]In other words, you were searching the entire GIMPS database for prime factors q of Mersenne numbers with exponent p == 5 (mod 6) for which q is divisible by 3.

Then, in [url=https://www.mersenneforum.org/showpost.php?p=611685&postcount=62]this post[/url] you proclaimed "exhaustive computations indicate" something that is obvious from the first formulas for k given in the first post linked to above.

So perhaps you can help me with a similar problem. I've run extensive computations, reducing battalions of supercomputers to molten slag, which indicate that no number greater than 5 which in decimal ends in 0, 2, 4, 5, 6, or 8, is prime. Of course, I have no idea why this could possibly be true.

[QUOTE=Dr Sardonicus;611816]You disregarded the careful explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611260&postcount=42"]this post[/URL] and reference to more explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611265&postcount=45"]this post[/URL], and continued to do unnecessary computations

In other words, you were searching the entire GIMPS database for prime factors q of Mersenne numbers with exponent p == 5 (mod 6) for which q is divisible by 3.

Then, in [URL="https://www.mersenneforum.org/showpost.php?p=611685&postcount=62"]this post[/URL] you proclaimed "exhaustive computations indicate" something that is obvious from the first formulas for k given in the first post linked to above.

So perhaps you can help me with a similar problem. I've run extensive computations, reducing battalions of supercomputers to molten slag, which indicate that no number greater than 5 which in decimal ends in 0, 2, 4, 5, 6, or 8, is prime. Of course, I have no idea why this could possibly be true.[/QUOTE]
One could have better read between the lines and understood that me "searching the entire GIMPS database" happened as much as someone else was "reducing battalions of supercomputers to molten slag".
It can be argued from the standpoint of hardware and software testing that there is no such thing as unnecessary computations though.
Running computation tests produces errors and soon or later one of the "battalions of supercomputers" would [U]in error[/U] (for instance, see [URL]https://en.wikipedia.org/wiki/Integer_overflow[/URL]) give a prime.

Examples of the first Mersenne numbers for which there are three consecutive factors for a given value of [I]k[/I][SUB]3[/SUB] with [I]k[/I][SUB]3[/SUB] = [I]k[/I][SUB]2[/SUB] + [I]k[/I][SUB]1[/SUB] are:
- M[M]1527857[/M] with factors {21389999, 12222857, 9167143}. Here 7 = 4 + 3.
- M[M]159541[/M] with factors {3509903, 2552657, 957247}. Here 11 = 8 + 3.

[QUOTE=Dr Sardonicus;611816]You disregarded the careful explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611260&postcount=42"]this post[/URL] and reference to more explanation in [URL="https://www.mersenneforum.org/showpost.php?p=611265&postcount=45"]this post[/URL], and continued to do unnecessary computations

In other words, you were searching the entire GIMPS database for prime factors q of Mersenne numbers with exponent p == 5 (mod 6) for which q is divisible by 3.

Then, in [URL="https://www.mersenneforum.org/showpost.php?p=611685&postcount=62"]this post[/URL] you proclaimed "exhaustive computations indicate" something that is obvious from the first formulas for k given in the first post linked to above.

So perhaps you can help me with a similar problem. I've run extensive computations, reducing battalions of supercomputers to molten slag, which indicate that no number greater than 5 which in decimal ends in 0, 2, 4, 5, 6, or 8, is prime. Of course, I have no idea why this could possibly be true.[/QUOTE]
:goodposting: :tu:
The last paragraph is priceless.... :missingteeth:

[QUOTE=Dobri;611887]Examples of the first Mersenne numbers for which there are three consecutive factors for a given value of [I]k[/I][SUB]3[/SUB] with [I]k[/I][SUB]3[/SUB] = [I]k[/I][SUB]2[/SUB] + [I]k[/I][SUB]1[/SUB] are:
- M[M]1527857[/M] with factors {21389999, 12222857, 9167143}. Here 7 = 4 + 3.
- M[M]159541[/M] with factors {3509903, 2552657, 957247}. Here 11 = 8 + 3.[/QUOTE]
This is a clear example of Guy's Strong Law of Small Numbers. Pick enough small numbers, and you will find plenty of triplets (a, b, c) such as a=b+c.

I still have this "feeling" that mersenne factors and fermat factors have more chances to be also aliquot factors, compared with the other primes. If you think about, THERE IS a connection, because all those "drivers" are related to perfect numbers, which in turn are strong related to mersenne primes. If the drivers are persistent, guides are persistent (guide is a driver from which some factors were removed, so it is just a "partial" driver), then why the factors alone couldn't be persistent too? So, when I look to factorDB aliquot sequences and see the small primes that factor each terms, I have the tendency to only see 3, 5, 7, 17, 23, 47, 89, 223, 233, etc, and I have this "feeling" that there are more such primes than "the others" of comparable size, and they are also "persistent" (their chances to appear again and again from a term to the next seems higher) than the other primes that come and go. So, maybe you can try to "intensively test" all the aliquot factors in factorDB and see if they are indeed factors of some mersenne numbers in our range of interest? (i.e. under 1G exponents, or under 32 bits exponents more generally). That way, at least, you would use your energy in a more useful way, and maybe you get lucky and really find some huge factors there :razz:

One would expect q1 = 6*p + 1, q2 = 8*p + 1, and q3 = 14*p + 1 all to be prime for infinitely many p == 1 (mod 4). One would also expect 2 to be a 6th power residue (mod q1), 8th power residue (mod q2), and 14th-power residue (mod q3) for a positive proportion of such (q1, q2, q3). (My best guess at the "positive proportion" is 1/84.)

I checked for such p, q1, q2, q3 up to the limit p < 1.1 x 10[sup]8[/sup]. Up to that limit, there are 2383 p == 1 (mod 4) for which q1, q2, and q3 are all prime. Of these, there are 23 for which q1, q2, and q3 all divide 2^p - 1.

Thus, among p < 1.1 x 10[sup]8[/sup] the proportion of prime triples (q1, q2, q3) all dividing 2^p - 1 is a bit lower than 1/84.

The values p q1 q2 q3 with p < 10[sup]7[/sup] are

1527857 9167143 12222857 21389999
1684937 10109623 13479497 23589119
3524537 21147223 28196297 49343519
6317357 37904143 50538857 88442999