Problem 80. Twin primes generating successive...

Problem 80. Twin primes generating consecutive...

G. L. Honaker, Jr. sent the following curio and nice puzzle:

5 is the smaller in a set of twin primes whose product is the concatenation of two consecutive primes, (not necessarily twins) i.e., 5*7 = 3.5 (dot is for concatenation.

Q1. Is there one more solution?

There is another curio and puzzle related to the above one:

891077215721081784886888257701070827 is the smaller in a set of twin primes whose product is the concatenation of two consecutive integers, i.e., 891077215721081784886888257701070827*891077215721081784886888257701070829 = 794018604377235322848433897872605582.794018604377235322848433897872605583 (dot is for concatenation).

Q2. Are there more solutions?

note: for both questions the consecutive numbers, in the concatenation, might appear in any of the two orders.

On Set. 2, 2025, Oscar Volpati wrote:

I was able to find four more solutions to question Q2 of problem 80.

Search strategy.

We need to find twin primes p and q, whose product is the concatenation of two consecutive integers a and b.

If integer b has n digits, then equality p*q = a*10^n+b holds.

Substitute p = x-1, q = x+1, b = a+1 (ascending case), then rearrange, obtaining:

x^2 = a*(10^n+1) + 2,

or, viewed as a congruence relation:

x^2 == 2 mod 10^n+1.

In other words;

2 must be a quadratic residue modulo w(n) = 10^n+1;

x must be a square root of 2 modulo w(n).

If complete factorization of number w(n) is known, we are able to check if 2 is a quadratic residue modulo each prime factor of w(n), and eventually to efficiently compute all possible square roots modulo w(n) by using Tonelli-Shanks algorithm and chinese remainder theorem; then, for each square root x found, we can check if x-1 and x+1 are both prime.

We only need to consider numbers n of the form n = 4*k, because:

2 is non-residue for prime 11, which divides w(n) whenever n = 2*k+1;

2 is non-residue for prime 101, which divides w(n) whenever n = 4*k+2.

Complete factorization of w(n) is currently known for many small numbers n=4*k; first few exceptions are 332, 356, 392, 400...

After known solution for n=36, found by Israel, there are four more solutions for n=396.

Note: quadratic residue 2 admits 2^22 = 4194304 distinct square roots modulo w(396).

Solution 1:

p=43421977283748161694072633893336245227391609730149263562729144351205199724796175015090831582520633502568118225295
4355463934702107964728269885096262688644034853639395077615105799339919571601786192665103151170947581386505769710635
8281169731316477061803013796578132204324130645367278268832822528117841212561164863854548598492928577776677190168812
51956101283374338871503089431823276421261037909974359

q=43421977283748161694072633893336245227391609730149263562729144351205199724796175015090831582520633502568118225295
4355463934702107964728269885096262688644034853639395077615105799339919571601786192665103151170947581386505769710635
8281169731316477061803013796578132204324130645367278268832822528117841212561164863854548598492928577776677190168812
51956101283374338871503089431823276421261037909974361

a=18854681112303413822576251552573222041179970908589967901630491213534262123467515417959431671101045859278289799547
2072329020523891831735526214027114750246510828728078518168950474473546121279840909283103404117348405135650173510498
6448301850740446178599990463411654198611390106011822536831126178742916867747564935245124486253351521466845313072487
89935557410917696361947584483395574902075975857409598

b=18854681112303413822576251552573222041179970908589967901630491213534262123467515417959431671101045859278289799547
2072329020523891831735526214027114750246510828728078518168950474473546121279840909283103404117348405135650173510498
6448301850740446178599990463411654198611390106011822536831126178742916867747564935245124486253351521466845313072487
89935557410917696361947584483395574902075975857409599

Solution 2:

p=6926194940047018231075250440120916569154218944767304567848697763518419498517283951214660494476098160236154363163
940350744550124878160062066526929127821523438648048402913709622918287757826018857708269439761253689675136319449129
259753483696163048939606864446410462863907843143899148375860569277119108527813494706655718646292621967798156829917
3914978874060061374111892271305964203583405377795224439

q=6926194940047018231075250440120916569154218944767304567848697763518419498517283951214660494476098160236154363163
940350744550124878160062066526929127821523438648048402913709622918287757826018857708269439761253689675136319449129
9259753483696163048939606864446410462863907843143899148375860569277119108527813494706655718646292621967798156829917
3914978874060061374111892271305964203583405377795224441

a=4797217634753291846832451142924997630503479914489772148256327662897429568890924219899803582698811791173955211228
421393431940084773799783552880160578764670115641655536950814260923251076801043586429108797363235821252049289836489
657919967606712714397884945818358083289034784300961249284449346258237959295262728564564560213989343715243898260919
62816622886154229923319027800821831198068009669973313598

b=4797217634753291846832451142924997630503479914489772148256327662897429568890924219899803582698811791173955211228
421393431940084773799783552880160578764670115641655536950814260923251076801043586429108797363235821252049289836489
657919967606712714397884945818358083289034784300961249284449346258237959295262728564564560213989343715243898260919
62816622886154229923319027800821831198068009669973313599

Solution 3:

p=744327641287170657821553108647606582183193069683596569626959039525161984224686049208268854589238227685023628865
90496919430419854623049083241405167816559545550665201934307502733126683033272497547981888938175485693673502243184
90333143029690172233926128750116669388059180787718002446121361759308315882231578477774840726947806076836805219862
05187179717864091713524226897544646272052850452950191099589

q=744327641287170657821553108647606582183193069683596569626959039525161984224686049208268854589238227685023628865
90496919430419854623049083241405167816559545550665201934307502733126683033272497547981888938175485693673502243184
90333143029690172233926128750116669388059180787718002446121361759308315882231578477774840726947806076836805219862
05187179717864091713524226897544646272052850452950191099591

a=554023637584122997683936635345442956841378092504970263617137430644454780538395523675417135731340814094008520893
61333419897342636691611329096701601308784531760426323553614293494021907031823018859897006300449656971203624271901
71227710024603694058033483337150669760488515201428324452777824470751168383547803325517483385565509847307563076905
97869881475467335078626482995588820062280155100053298168098

b=554023637584122997683936635345442956841378092504970263617137430644454780538395523675417135731340814094008520893
61333419897342636691611329096701601308784531760426323553614293494021907031823018859897006300449656971203624271901
71227710024603694058033483337150669760488515201428324452777824470751168383547803325517483385565509847307563076905
97869881475467335078626482995588820062280155100053298168099

Solution 4:

p=842998528349081253534543744292255092008169997391901355230148830053031617780085904214756929998540884814037325533
90113518261684440509100477143949635330812998640468575374492022972006347014332490583623250990611411184312556031918
84225925818632362497180065185045651861118415342355491599057552891845554461853749566343226689489462308440434253241
01560773341817937869825508635287259190902056756694480244731

q=842998528349081253534543744292255092008169997391901355230148830053031617780085904214756929998540884814037325533
90113518261684440509100477143949635330812998640468575374492022972006347014332490583623250990611411184312556031918
4225925818632362497180065185045651861118415342355491599057552891845554461853749566343226689489462308440434253241
01560773341817937869825508635287259190902056756694480244733

a=710646518798716749885888068749207298094224769539941699269220820976910827480616761800098916500398265681769559108
80345886594343862274820615198265133053007535500422085601773222087329184834218012271348479234042981460819335778881
13628907237586053273332977796517912237637948440293680166145685557626507748689351132603445028861708285667521894708
61232316681860397280231859083596903980370829107018613751822

b=710646518798716749885888068749207298094224769539941699269220820976910827480616761800098916500398265681769559108
80345886594343862274820615198265133053007535500422085601773222087329184834218012271348479234042981460819335778881
13628907237586053273332977796517912237637948440293680166145685557626507748689351132603445028861708285667521894708
61232316681860397280231859083596903980370829107018613751823

Near-solution 1 (padding a zero between a and b):

p=132459146553851342468280137462907961256778599572127168697613627395797864545120181932512550120074838267571230326
59057805265238126151009926482025922634455162830662638971286039357787806318583237184481840508325480848875839163958
35421682349209766242757752418692049470798449717329600245535868022007278163866966872347571257642365709639746293074
56819077973483466158758874520522061472502928227161025854387

q=132459146553851342468280137462907961256778599572127168697613627395797864545120181932512550120074838267571230326
59057805265238126151009926482025922634455162830662638971286039357787806318583237184481840508325480848875839163958
35421682349209766242757752418692049470798449717329600245535868022007278163866966872347571257642365709639746293074
56819077973483466158758874520522061472502928227161025854389

a=175454255057746679753551477481149198001863462921815045236879131688015185707960318175844297731340424747776160190
36744929447331682342201909117211197538670317928844322930798442734879878759821392616177464616015926438519996155203
11266610030568379022116623393621117023528351707179913008880470871056872332420700450997101497259869054570856604313
6871120401742203937574666339046302194963345933385378854542

b=175454255057746679753551477481149198001863462921815045236879131688015185707960318175844297731340424747776160190
36744929447331682342201909117211197538670317928844322930798442734879878759821392616177464616015926438519996155203
11266610030568379022116623393621117023528351707179913008880470871056872332420700450997101497259869054570856604313
6871120401742203937574666339046302194963345933385378854543

Near-solution 2 (padding two zeros between a and b):

p=74891688847257450592533099102261206779237782525996460265784865603376736693575606072413598847688542715795769060
5355911014478369335640359989895083006535689204246346823555373439692349804852379918505844207975493234609783331418
8791147898745726973002965182584337093992132422114590993822389648067629658023532183990139167585416473901223039798
9523382152486351780807942344738574335059458424304892164596791

q=74891688847257450592533099102261206779237782525996460265784865603376736693575606072413598847688542715795769060
5355911014478369335640359989895083006535689204246346823555373439692349804852379918505844207975493234609783331418
8791147898745726973002965182584337093992132422114590993822389648067629658023532183990139167585416473901223039798
9523382152486351780807942344738574335059458424304892164596793

a=56087650583944260087479955598379183082820338846270912471402524153899483208377130690000895227479365175852060873
7027126416273432642983530105401634916988199642286958484866128375200352678198799197715448156417298083380558565492
7936245334100742797636571396498214703077990244602709792997299753006996562533654344909042668587693662004192283002
038247576992628454326369288980353346927584133305031936691262

b=56087650583944260087479955598379183082820338846270912471402524153899483208377130690000895227479365175852060873
7027126416273432642983530105401634916988199642286958484866128375200352678198799197715448156417298083380558565492
7936245334100742797636571396498214703077990244602709792997299753006996562533654344909042668587693662004192283002
038247576992628454326369288980353346927584133305031936691263

***