Mersenne Numbers Known from Number Practice to Be Composite

[Dr Sardonicus]

Originally Posted by Dobri

<snip>
On the basis of quite limited observations for k up to 11 (see posts #29 and #30), the values of k for another factor are obtained as follows:
- the sum of a prime number (or 1) and 2ⁿ such as 5 + 2² = 3² and 1 + 2³ = 3²;
- the sum of 1 and a prime number giving 2ⁿ such as 1 + 3 = 2² and 1 + 7 = 2³;
- the sum of two prime numbers giving 2ⁿ such as 3 + 5 = 2³; or
- the sum of 2ⁿ and a prime number giving a prime number such as 2² + 3 = 7 and 2³ + 3 = 11.

Originally Posted by Dobri

<snip>
For k = 13, only cases with Δk = 1, 4, 9, and 12 for a given Mersenne number are found, where Δk = k₂ - k₁ with k₂ = 13 and k₂ > k₁. Here 1 + 12 = 13 and 4 + 9 = 13.

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.

[Dobri]

Originally Posted by Dr Sardonicus

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.

Affirmative, this is a new category, although 4 = 2² and 9 was already included as 5 + 2² = 9 in the expanding scheme of values of k.
A distant loose analogy with a growing Pascal's triangle comes in mind...
It is to be seen to what extent 2ⁿ, n = 2, 3,..., would appear in the additive scheme with the increase of the values of k.

[Dobri]

k = 14: None;
k = 15: 3 + 12 = 7 + 2³ = 11 + 2² = 15.

[Dobri]

k = 16: 1 + 15 = 3 + 13 = 4 + 12 = 7 + 9 = 16.

[Dobri]

k = 17: 5 + 12 = 2³ + 9 = 17;
k = 18: None.

[User140242]

Originally Posted by Dobri

No cases have been forgotten.
In the quoted example, 2³⁷-1 = 137438953471, then 13743895347 / 223 = 616318177, and k₂ = (616318177-1)/(2×37) = 8328624, thus Δk = 8328624 - 3 = 8328621 = 3×7×396601, which is unrelated to k = 13.

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

[Dobri]

...
k = 19: 3 + 2⁴ = 2² + 15 = 7 + 12 = 19;
k = 20: 3 + 17 = 5 + 15 = 2³ + 12 = 9 + 11 = 20;
k = 21: 1 + 20 = 2² + 17 = 5 + 2⁴ = 2³ + 13 = 9 + 12 = 21;
k = 22: None;
k = 23: 3 + 20 = 2³ + 15 = 11 + 12 = 23;
k = 24: 1 + 23 = 3 + 21 = 2² + 20 = 5 + 19 = 7 + 17 = 2³ + 2⁴ = 9 + 15 = 2×12 = 24;
k = 25: 1 + 24 = 2² + 21 = 9 + 2⁴ = 12 + 13 = 25;
k = 26: None;
k = 27: 3 + 24 = 2² + 23 = 7 + 20 = 2³ +19 = 11 + 2⁴ = 12 + 15 = 27;
k = 28: 1 + 27 = 3 + 25 = 2² + 24 = 7 + 21 = 9 + 19 = 12 + 2⁴ = 13 + 15 = 28;
k = 29: 5 + 24 = 2³ + 21 = 9 + 20 = 12 + 17 = 29;
k = 30: None;
k = 31: 3 + 28 = 2² + 27 = 7 + 24 = 12 + 19 = 15 + 2⁴ = 31;
k = 32: 3 + 29 = 5 + 27 = 2³ + 24 = 9 + 23 = 11 + 21 = 12 + 20 = 15 + 17 = 32;
...
It is known that there are no factors 2pk + 1 of Mersenne numbers for k = 2(2m + 1), m = 0, 1, 2,...

The exhaustive computations indicate that if there is a factor 2pk₂ + 1 of a Mersenne number 2^p - 1 for a given pair of k₂ and p, then there is no factor 2pk₁ + 1 for said p for the positive values of k₁ = k₂ - 2(2m + 1), m = 0, 1, 2,....

[Dr Sardonicus]

Originally Posted by Dobri

<snip>
The exhaustive computations indicate that if there is a factor 2pk₂ + 1 of a Mersenne number 2^p - 1 for a given pair of k₂ and p, then there is no factor 2pk₁ + 1 for said p for the positive values of k₁ = k₂ - 2(2m + 1), m = 0, 1, 2,....

What a waste of computing power.

[LaurV]

Originally Posted by Dr Sardonicus

What a waste of computing power.

Agree. But let them discharge the energy. I went the same way for a while, 20 years ago (probably few other now-famous forumites too, hehe).

[Dobri]

Originally Posted by Dr Sardonicus

What a waste of computing power.

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 Δk instead of 2kp+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 lemma despite its simple proof.

[User140242]

Originally Posted by Dobri

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

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

#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;

}