Puzzle 859. A follow-up to Puzzle 203.

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, 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:

https://mersenneforum.org/showthread.php?t=10336

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.

***

On January 4, 2023, Martin Hopf wrote:

Q3: Can you try to prove that RPP(74207281) is prime or composite? ...

It is a proven composite!

On December 23rd 2022, a 17-digit factor was found with the elliptic curve method:

14344999215792989

It is worth to mention that the fast modular reduction with right perfect numbers plays a key role here. Implementing it in the elliptic curve method made it possible to find a factor in reasonable time.

See also the updated list and primes of the form 'perfect number' + 1 (a.k.a. RPN) at mersenneforum.org.
I found this factor with a self written Pari/GP implementation on late December 22nd 2022 (UTC).
After the software was running satisfactorily, one ECM-curve with B1=5,400 and B2=350,000 took over 50 hours to complete. I succeeded after the 8th curve with a bit of luck. So the total computation-time for finding this factor was about 410 hours (17 days)

***

Records | Conjectures | Problems | Puzzles