Problems & Puzzles: Puzzles

Puzzle 859. A follow-up to Puzzle 203.

In the puzzles 203 & 858 we have been studying these integers that are one unit more than a perfect number. We have called these integers RPP, and are defined by the following expression:

RPP(p)=(2^(p-1))*(2^p-1)+1

We remind that p and (2^p-1) are prime numbers, the second one named "Mersenne prime".

As you know, at this day (December 10, 2016) there are known only 49 Mersenne primes, and these correspond to the following 49 p primes:

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.

As a result of the Puzzles 203 & 858 we already know the following facts:

a) RPP(p) is prime for only 4 p values: 2, 3, 13 & 19 (Labos, E)

b) RPP(p) is composite applying the Ken Wilke rules, for the following 32 p values: 5, 7, 17, 31, 89, 107, 127, 521, 607, 3217, 4253, 9689, 9941, 11213, 19937, 21701, 44497, 86243, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 25964951, 30402457, 32582657, 37156667, 43112609, 57885161

The Ken Wilke rules imply that all of these 32 RPP integers are composite and are divisible by at least one of the following four primes: 7, 11, 29 & 71

c) The puzzlers have provided the least prime factor for the following 4
RPP(p) values:

 p Least prime factor of RPP(p) Author 61 2432582681 KW 20996011 1552147 JKA 24036583 149 JKA 42643801 3593 EV

d) For the following 8 p values: 1279, 2203, 2281, 4423, 23209, 110503, 132049, & 216091 the puzzlers have proved that the corresponding RPP(p) values are composites... but they haven't provided the least prime factor of each RPP(p)...

e) For p=74207281 we still do not know if RPP(p) is prime or composite

Q1. Send the least prime factor for the RPP(p) corresponding to the 8 p values listed in d)

Q2. Are there more simple rules to discard RPP(p) as primes, other than the Wilke ones?

Q3. Can you try to prove that RPP(74207281) is prime or composite? If composite please send the least prime factor.

______

if p is a prime of the form 6k+5, then RPP(p) is divisible by 7.
if p is a prime of the form 10k+7, then RPP(p) is divisible by 11
if p is a prime of the form 28k+3, then RPP(p) is divisible by 29
if p is a prime of the form 70k+5, then RPP(p) is divisible by 71.

Contributions came from Emmanuel Vantieghem and Jan van Delden

***

Emmanuel wrote, Dec 16, 2016:

Q1.
I list  {prime, smallest divisor}  for all prime in the set sub d) :
{1279, unknown but > 3*10^10}
{2203, 1498429
{2281, 197
{4423, 2163571
{23209, 35603
{110503, 491
{132049, unknow but > 3*10^10}
{216091, 6920341}

Q2.
Let us abreviate   2^(k-1) (2^k - 1) + 1   as  f(k)
I think the Ken Wilke rules are obtained as follows :
Take an odd prime  q  and let  S(q) = {k_1, k_2, ..., k_n}  be the set of all numbers  k  between  1  and  q-1  such that  f(k)  is divisible by  q.
Then the "rule" is :
If  k  is a number of the form   (q-1)m + k_1 or k_2 or ... k_n,  then  f(k)  is divisible by  q  (i = 1, 2, ..., n).
Here is the list of all  q < 1000  for which  S(q)  is not empty :
q       S(q)
11  {4,7}
29  {3,26}
37  {16,21}
53  {12,41}
67  {26,41}
71  {5,31,40,66}
79  {12,28,51,67}
107  {21,86}
137  {31,38,99,106}
149  {51,98}
163  {52,111}
179  {32,147}
191  {42,54,137,149}
197  {72,125}
211  {29,182}
263  {30,102,161,233}
317  {16,301}
347  {14,333}
373  {115,258}
379  {157,222}
389  {180,209}
421  {170,251}
443  {140,303}
449  {102,123,326,347}
463  {96,136,327,367}
491  {238,253}
541  {82,459}
547  {73,474}
557  {57,500}
599  {147,153,446,452}
613  {59,554}
653  {23,630}
659  {154,505}
701  {218,483}
709  {273,436}
739  {7,240,253,486,499,732}
757  {103,654}
821  {335,486}
823  {195,217,606,628}
827  {282,545}
863  {134,298,565,729}
877  {144,733}
883  {390,493}
907  {442,465}
947  {309,638}
977  {120,369,608,857}
991  {181,315,676,810}
Examples of how to turn this into "rules" :
q = 11 : if  k  is a number of the form  10m + 4 or 7  then  f(k)  is divisible by  q.
q = 29 : if  k  is a number of the form  28m + 3 or 26  then  f(k)  is divisible by  q.
...
q = 71 : if  k  is a number of the form  70m + 5, 31, 40  or  66  then  f(k)  is divisible by  q.
...
q = 739 : if  k  is a number of the form  738m + 7, 240, 253, 486, 499 or 732, then  f(k)  is divisible by  q.

Of course, in the puzzle we have restrict ourselves to prime  k.

Note that  S(q)  is empty for a lot of  q.  Here are the first such  q (less than 300) :
3, 5, 13, 17, 19, 23, 31, 41, 43, 47, 59, 61, 73, 83, 89, 97, 101, 103, 109, 113, 127, 131, 139, 151, 157, 167, 173, 181, 193, 199, 223, 227, 229, 233, 239, 241, 251, 257, 269, 271, 277, 281, 283, 293
Most of these primes are of the form  7m + 3, 5 or 6 (which I can explain a bit further).  But there are also others :
23, 43, 109, 113, 127, 151, 193, 233, 239, 277, 281, ...

Here is my explanation (as I mentioned this allready in my contribution to puzzle 858).
Write  f(k)  in the form  2x^2 - x + 1, where  x = 2^(k-1).
Such a quadratic polynomial (in x) cannot be congruent  0  mod q  (for some  x) if it's discriminant  (-7)  is not quadratic residue mod q.
With the quadratic reciprocity law we easily can find out that  S(q) is not empty for all  q  of the form  7m + 0, 1, 2  or  4.
So, if  q  is of that form, then there will be two solutions of the congruence  2x^2 - x + 1 = 0 (mod q)
(if  q = 7  then the two solutions coincide) say  a  and  b.  But, it is not at all sure that  a  end/or   b  are congruent to a power of  2.
This is sure the case when  2  is a primitive root modulo q.  If this is not the case, then there are two possibilities :
1) there is some power of  2  congruent to  a(or b).  Then there is some power of  2  congruent to  b(or a)
2) there is no power of  2  that is congruent  a(or b) : then there will be no power of  2 congruent b(or a).

***

Jan wrote, no later than Dec 27, 2016:

Q1.

RPP(1279)     no divisor < 155768000183

RPP(2203)     divisor 60449

RPP(2281)     divisor 197

RPP(4423)     divisor 2163571

RPP(23209)   divisor 35603

RPP(110503) divisor 491

RPP(132049) no divisor < 127782809321

RPP(216091) divisor 4673

I used Emmanuel’s remark regarding quadratic residues to reduce the amount of work needed.

Q3.

My routine would take 34 years (based on a testduration of 1 hour). I would use a Fermat base-2 test.

Maybe it is nice to mention that this test is conclusive (prime/not prime) iff:

gcd(2^(2^(p-1)) mod N - 1,N)=1, with N=RPP(p)

If the value of the gcd is equal to 0, the number 2 is not admissible.

If the value of the gcd is greater than 1 we found a divisor of RPP(p).

In that case the divisor of RPP(p) is a divisor of a Fermat number F(k)=2^(2^k)+1, k in [0..p-2].

So if the gcd turns out to generate a divisor of N than PrimeGrid might be interested in this divisor (if unknown)

***

On May21, 2020 Carlos Rivera wrote:

As an un update for this puzzle, the supposedly 50th and 51th Mersenne primes 2^p-1 already discovered (2017 and 2018, respectively) are such that p=77232917 and p=82589933. It happens that both p values are equal to 5 mod 6, so applying the Wilke's rules their corresponding RPP are composites divided by 7.

***

On July, 13 2022, Andreas Höglund wrote:

Q1:

RPP(1279):       factor: 72353441721527140856665601867
RPP(132049):    factor: 194528547122653

List of all RPP factors (except RPP(74207281)) in post #10 here:

I found those 2 factors above using GMP-ECM back in 2008 for that thread (I’m ATH in that thread).

Q3:
Still no factors for RPP(74207281) below 2.3*10^13.

***

 Records   |  Conjectures  |  Problems  |  Puzzles