Problems & Puzzles: Puzzles

Puzzle 1003. Right Perfect Primes

This is an update for an issue that started in our puzzle 203 and continued through the puzzles 858859. This is an issue that cover already 20 years, circa.

The integers there discussed are the so-called "Right Perfect Integers" and the aim is to discover what of these integers are primes.

Let's make a very short & crowded summary of the issue.

• No Odd Perfect Integers are known.

• Every Even Perfect Integer known is related to one Mersenne prime. If 2^p-1 is a Mersenne prime, then p is prime too and
2^(p-1)*(2^p-1) is an Even Perfect Integer.

• What if we add or subtract one unit to an Even Perfect Integer? Is it possible for these new odd integers to be primes?

• If we subtract one unit to an Even Perfect Integer, the only possible prime produced is 5, when p=2, 2^(2-1)*(2^2-1)-1=5. For any other p value a composite is produced. See the whole proof in Puzzle 203.

• But if we add one unit, 2^(p-1)*(2^p-1)+1 the corresponding Right Perfect Integers (RPI) has shown a more interesting and diverse behavior. Here is a condensed summary of this situation:

 Quantity of RPI Behavior of the RPI Nth Mersenne prime 1 Primality or Compositeness unknown 49 4 Primes (by E. Labos) 1, 2, 5 &7 2 Composite without known smallest prime factor 15, & 30 10 Composite with known smallest prime factor computed 9, 16, 17, 20, 26, 29, 31, 40, 41 & 46 34 Composite with known smallest prime factor obtained by the Wilke's rules All the others 51 Totals

*See below some details for all the 51 Mersenne Primes...

The status shown above is product of a collective work of several puzzlers that has sent their contributions to the Puzzles 203, 858 & 859, from 2001 to our days. Here is a short historical summary:

E. Labos, is the creator of the concept RPI. The participants in these three past puzzles are: J. K. Andersen, Jan van Delden, Carlos Rivera, J. C. Rosa, Shyam Sunder Gupta, Emmanuel Vantieghem, Polly T. Wang,  Johann Wiesenbauer and Ken Wilke (alphabetic order)

The Wilke's rules are:

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

Until new & interesting (for our purposes) Mersenne primes are gotten, nowadays (May 30, 2020) we have only two pending tasks (in red in the summary above):

a) To determine the primality or compositeness of the RPI associated to the Mersenne prime 49.

b) To get the smallest prime factor (SPF) of the RPI's associated to the Mersenne primes 15th & 30th

Four years ago (2016) Emmanuel Vantieghem and Jan van Delden worked a bit over these two tasks.

Q. Would you like to give a new try to any of these two tasks?

***

 Mersenne Primes (Mp), Perfect numbers (Pp) and Right Perfect Integers (Pp+1) Mp= 2^p-1 Pp= 2^(p-1)*(2^p-1) Extract from: https://primes.utm.edu/mersenne/index.html # p Digits in Mp Digits in Pp Status of Pp+1 1 2 1 1 Prime by E. Labos 2 3 1 2 Prime by E. Labos 3 5 2 3 Composite w/SPF by KW rule 4 7 3 4 Composite w/SPF by KW rule 5 13 4 8 Prime by E. Labos 6 17 6 10 Composite w/SPF by KW rule 7 19 6 12 Prime by E. Labos 8 31 10 19 Composite w/SPF by KW rule 9 61 19 37 Composite w/SPF computed 10 89 27 54 Composite w/SPF by KW rule 11 107 33 65 Composite w/SPF by KW rule 12 127 39 77 Composite w/SPF by KW rule 13 521 157 314 Composite w/SPF by KW rule 14 607 183 366 Composite w/SPF by KW rule 15 1279 386 770 Composite w/o SPF known 16 2203 664 1327 Composite w/SPF computed 17 2281 687 1373 Composite w/SPF computed 18 3217 969 1937 Composite w/SPF by KW rule 19 4253 1281 2561 Composite w/SPF by KW rule 20 4423 1332 2663 Composite w/SPF computed 21 9689 2917 5834 Composite w/SPF by KW rule 22 9941 2993 5985 Composite w/SPF by KW rule 23 11213 3376 6751 Composite w/SPF by KW rule 24 19937 6002 12003 Composite w/SPF by KW rule 25 21701 6533 13066 Composite w/SPF by KW rule 26 23209 6987 13973 Composite w/SPF computed 27 44497 13395 26790 Composite w/SPF by KW rule 28 86243 25962 51924 Composite w/SPF by KW rule 29 110503 33265 66530 Composite w/SPF computed 30 132049 39751 79502 Composite w/o SPF known 31 216091 65050 130100 Composite w/SPF computed 32 756839 227832 455663 Composite w/SPF by KW rule 33 859433 258716 517430 Composite w/SPF by KW rule 34 1257787 378632 757263 Composite w/SPF by KW rule 35 1398269 420921 841842 Composite w/SPF by KW rule 36 2976221 895932 1791864 Composite w/SPF by KW rule 37 3021377 909526 1819050 Composite w/SPF by KW rule 38 6972593 2098960 4197919 Composite w/SPF by KW rule 39 13466917 4053946 8107892 Composite w/SPF by KW rule 40 20996011 6320430 12640858 Composite w/SPF computed 41 24036583 7235733 14471465 Composite w/SPF computed 42 25964951 7816230 15632458 Composite w/SPF by KW rule 43 30402457 9152052 18304103 Composite w/SPF by KW rule 44 32582657 9808358 19616714 Composite w/SPF by KW rule 45 37156667 11185272 22370543 Composite w/SPF by KW rule 46 42643801 12837064 25674127 Composite w/SPF computed 47 43112609 12978189 25956377 Composite w/SPF by KW rule 48? 57885161 17425170 34850339 Composite w/SPF by KW rule 49? 74207281 22338618 44677235 Unknow if prime or composite 50? 77232917 23249425 46498850 Composite w/SPF by KW rule 51? 82589933 24862048 49724095 Composite w/SPF by KW rule

From May 30 to June 5, 2020, contributions came from Jim Howell, Jan van Delden.

***

Jim wrote:

I found a factor for RPI-15, (exponent 1279).  I used a program that I downloaded, that uses the Elliptic Curve Method of factoring.  Here is the result.

Input number is 54162526284365847412654465374391316140856490539031695784603920818387206994158534859198999921056719921919

057390080263646159280013827605439746262788903057303445505827028395139475207769044924431494861729435113126280837904930462

740681717960465867348720992572190569465545299629919823431031092624244463547789635441481391719816441605586788092147886677

321398756661624714551726964302217554281784254817319611951659855553573937788923405146222324506715979193757372820860878214

322052227584537552897476256179395176624426314480313446935085203657584798247536021172880403783048602873621259313789994900

336673941503747224966984028240806042108690077670395259231894666273615212775603535764707952250173858305171028603021234896

647851363949928904973292145107505979911456221519899345764984291329 (770 digits)

Using B1=5000000, B2=8316852668, polynomial Dickson(6), sigma=1297461449

Step 1 took 999368ms

Step 2 took 147416ms

********** Factor found in step 2: 72353441721527140856665601867

Found probable prime factor of 29 digits: 72353441721527140856665601867

Composite cofactor 74858258288286795772547768566502601446648291883068699755004532102558349669764397613431794044576894090

497514655279522018675512904052571197432656962855774628280931661411173805835656875734163916883116690518341114991485835140

038628051914707386461619674539978417143299730021018634652780836735906410508412629803385695633791064329603008805823656165

310752238592336541242428934597137653274098519497881022578473695214135367554205592895506845717489792532061695943917135080

689620322087822659326887200474897941240615834784848770017416246802810079414391637565446317880601990991844459444785416551

799906936685017446758667927391060888384025250831255524982150709122105926590683761693666300938148761842307998885691212446

3033034714097567520909321260485977266787 has 741 digits

I have verified that the 29-digit factor is prime.
It is not guaranteed to be the smallest prime factor.
I have been trying to find a factor of the 741-digit cofactor, using the ECM program. No results yet.

***

Jan wrote:

Time to use the heavy machinery. I installed gmp-ecm, an implementation of ECM, written in c. It took some time to get a working distribution, it is still not optimized for my p.c. and I’m still learning how to tweak the parameters. But the good news is that I found a prime divisor of RPP(1279): 72353441721527140856665601867. Its cofactor is composite. This factor was found in the second stage.

For those of you who want to reproduce this result, gmp-ecm used the following parameters: Using B1=3000000, B2=4592487916, polynomial Dickson(6), sigma=1:2906373405.

I only had to provide B1 and set the number of seeds (sigma’s) to try, for which one may consult a table in a README file. You can also specify with -go ‘N-1’ that RPP(1279)-1 has small factors. The initial group order that RPP(1279) outputs is equal to N-1. But I’m not sure how and if that relates to the group order #E(F[p]).

Every sigma took about 2 minutes. The prime factor was found on try 73.

I’m still waiting for RPP(130249) to finish its first try for sigma! The number of these seeds one needs depends on the size of the prime factor is expected to have.
After one try the routine gives an estimate of the amount of time one needs as a function of the number of digits of this prime factor. If it decides to give me some specifics, I’ll let you know.
I might decide to pull the plug on this one.

***

Later, on June 11, 2020, Jan van DElden wrote again:

Gmp-ecm finished its first run on RPI(30), i.e. exponent 132049. Below a summary of the expected duration to find a factor, given the number of digits of the factor:

Expected time to find a factor of n digits:

n           duration

35           2.83y

40           20.78y

45           179.69y

50           1776y

To be clear, the y denotes the unit of measurement: year.

Not my cup of tea..

If you increase the bounds that are used, the duration per run increases as well, but the number of runs might decrease significantly, thus a potential lower estimate would result.
And possibly one would get really lucky and only need just a few runs.

***

 Records   |  Conjectures  |  Problems  |  Puzzles