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.

______
The Ken Wilke rules are:

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:

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:

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)

***

Records   |  Conjectures  |  Problems  |  Puzzles