Problems & Puzzles: Puzzles

Puzzle 1220 Prime Split Giorgos Kalogeropoulos sent the following puzzle: Split k into two primes p1 and p2 such that the largest prime factor (LPF) of k+1 is p1 and LPF(k-1) = p2.  The smallest k with this property is 323. We split k = 323 into two primes 3-23, so p1 = 3 and p2 = 23. LPF(k+1) = LPF(324) = LPF(2^2*3^4) = 3 = p1 LPF(k-1) = LPF(322) = LPF(2*7*23) = 23 = p2 Next k with this property is 357149993. We split k into two primes 3571-49993, so p1 = 3571 and p2 = 49993 LPF(357149994) = LPF(2*3*79*211*3571) = 3571 = p1 LPF(357149992) = LPF(2^3*19*47*49993) = 49993 = p2 It is allowed for p2 to have leading zeros. Q1. Find the first five integers with this property Q2. What is the biggest k that you can find with this property? Q3. Can you find at least one prime number k with this property?

---

From May 10-ro May 16, contributions came from Emmanuel Vantieghem, Simon Cavegn, Oscar Volpatti

***

Emmanuel wrote:

I could not find such numbers < 10^11.

Instead I made a list of 10000 "echo number" : numbers  k  with the property that they end with the LPF of  k - 1 :
   13, 57, 73, 111, 127, 163, 193, 197, 313, 323, 337, 419, 433, 687, 757, ...(https://oeis.org/A383896)
And I made a list of 10000 numbers  k  that start with the LPF of  k + 1 :
   35, 59, 255, 323, 383, 539, 599, 734, 755, 783, 1154, 1187, 1351, ...
The intersection of both lists gives :
   323, 13311, 174929, 1016261, 7779239, 8972979, 17213441, 19316211, ...
and (if expanded) will certainly contain all the numbers Giorgos is asking for.

***

Simon wrote:

Checked first 7000000 primes for p1 and p2, with few restrictions: At most 9 zeros in between, k < 1844674407370955161
Found no more solutions.

***

Oscar wrote:

I found ten more composites k, with lengths between 18 and 248 digits.

The smallest found value k = 130842100259067357 is actually the third integer with the given property.

Next solution must have more than 20 digits, but it may be smaller than k = 357142857142907142857142857.

My search strategy was not exaustive and it may have missed many solutions.

As an example, I actually found several more candidates satisfying the divisibility constraints:

k+1 = p1*q1,

k-1 = p2*q2.

But for some big candidates I wasn't able to verify LPF constraints by suitably factoring q1 and/or q2.  

d = 18

k = 130842100259067357

p1 = 1308421 

p2 = 00259067357   

q1 = 2*7*31*499*557*829

q2 = 2^2*3299*38273

d = 27

k = 357142857142907142857142857

p1 = 3571428571429

p2 = 07142857142857

q1 = 2*3*89*251*746079353

q2 = 2^3*509*3121*3934309

d = 42

k = 102184783842865700161290322580645161035739

p1 = 1021847838428657

p2 = 00161290322580645161035739

q1 = 2^2*5*1412507929237*3539803137743

q2 = 2*3^2*38453*915324710723

d = 47

k = 36123513517418758218100049850448654037886340977

p1 = 361235135174187582181

p2 = 00049850448654037886340977

q1 = 2*7^3*19341021209*7536964732987

q2 = 2^4*11*109*34499*315223*3473420341

d = 63

k = 262373535955669367364930103690030120481927710843373493975903611

p1 = 26237353595566936736493010369

p2 = 0030120481927710843373493975903611

q1 = 2^2*3*4491241*185546340829479721380645869

q2 = 2*5*871080139372822299651567944251

d = 68

k = 15714394475854795173302365164712499999999999999999999999999990056887

p1 = 157143944758547951733023651647 

p2 = 12499999999999999999999999999990056887

q1 = 2^3*7*11*41*13619*3231859610209*89957571810547879

q2 = 2*827*967*160690219*4891434203234659 

 

d = 74   

k = 24680178344972638345715366902272727272727272727272727272517983751155967627

p1 = 246801783449726383457153669

p2 = 02272727272727272727272727272517983751155967627

q1 = 2^2*71*28703*535033*825604004668549*27771670803621196843

q2 = 2*3*19*37*1128661*2281029364690486831

d = 146

k = 1257892503617358706270545505439913318140519750410909605641264915866912499999999999999999999999999999999999999999999999999999999999999999
8757842983

p1 = 12578925036173587062705455054399133181405197504109096056412649158669  

p2 = 124999999999999999999999999999999999999999999999999999999999999999998757842983   

q1 = 2^3*307*9847967*70498670291621164376639*586467739349185520696661014624951781662290787

q2 = 2*181*277987293617095846689623316119317860362545801195781128318511583617

d = 147 

k = 1463940224392757594921884149626402454734968261775935165015342093551636100033377837116154873164218958611481975967957276368491321762349799
73297730307

p1 = 14639402243927575949218841496264024547349682617759351650153420935516361

p2 = 0003337783711615487316421895861148197596795727636849132176234979973297730307

q1 = 2^2*89*103*587*2899021*925033877*58942960856587*2939231064491821311470113466722761136127

q2 = 2*59*113*129600232358659*719987899817846761*35251185289336187931413722724798134163

d = 248

k = 12339245055768155812168418572936892540199829039266182529970496174073935216436379829760667805470399957576688358664618865300005654829224157430
445600542863605519113322777652114906129834878986654603030988464148382718841890974892558244741008821533589683

p1 = 123392450557681558121684185729368925401998290392661825299704961740739352164363798297606678054703999575766883586646188653

p2 = 00005654829224157430445600542863605519113322777652114906129834878986654603030988464148382718841890974892558244741008821533589683

q1 = 2^2*277*2378219*17518489*7738164669968009*279945688351938759469259968179730495383479859563462102031403302340317531087063932936837876575639

q2 = 2*3*363678682610340112303977190073026679468156294550638619766663757237205783945768234849146082453230921416310261557708533356609

 

***