Problems & Puzzles: Puzzles

Puzzle 1074 Semiprimes stairs JM Bergot, sent the following nice puzzle:   Start at 217=7*31 7+31=38=2*19 2+19=21=3*7 3+7=10=2*5 2+5=7 STOP FOUR semprimes 10, 21, 38, 217 in this list. Q. Can you find a longer list depending on the starting semiprime?

---

During the week 5-11 Feb, 2022, contributions came from Giorgos Kalogeropoulos, Jeff Heleen, Gennady Gusev, Paul Cleary, Emmanuel Vantieghem, Oscar Volpatti. Fred Schneider.

***

Giorgos wrote:

Conjecture: 

We can construct lists of any length following this method:

We work in reverse order. It can be easily shown that the parity of the terms alternates.

Begin with a seed. (The seed is the stop-step in the puzzle example). The seed cannot be semiprime.

If we choose an odd seed S then S-2 must be prime and S non-semiprime. So, S can be  5, 7, 13, 19, 31...

If we choose an even seed S then S must not be semiprime AND there must exist a prime P such that S-P is prime AND P(S-P)-2 is prime.

So, the even seeds can be 8, 16, 20, 28, 40, 44, 50...

 

Let's take an even number S as seed.
 

1)Find the smallest prime P so that S-P is prime AND P(S-P)-2 is prime.

2)Next term will always be odd equal to P(S-P)

3)Next term will always be even equal to 2 * (P(S-P) - 2)

4)Use the even number from step 3 as new seed S and repeat from step 1.

If we choose to start with an odd seed then we start from step 2 with P=S-2.

 

For example using seed S=8 we can easily get a list of length 20: 

{82711117977818765380380118,41355558988909382690190061,2205747452605972747438,1102873726302986373721,
232135071838141222,116067535919070613,222778379883574,111389189941789,813059780734,406529890369,
311041774,155520889,448534,224269,1774,889,134,69,26,15,8} 

 

The longest list that my laptop found in 1 hour is of length 196 using seed S=16 and here is the 603-digit starting semiprime (of course these are probable semiprimes found by Mathematica):

22933809168449529498155496991764006553161230790648406407711950439819621322055961719294380541501675
10287707068606811921200326724581834449778154699755036501510632030647619454592588328666444200241213
19714241254570883276747143462487054989798858118265162005086813118394752568483450397194429421607715
58354352481469628059048416344406317696467994613749884369712328436806174513506634961984083589342894
38484005431143082541463545806728810917318009572308948809252545187916933441460785420873129575994076
82226196426586954055950414623895427933466634693878301004616089908001008618521572932572667678208010
650685980286718
 

I believe that there always exist primes that fulfill the two conditions of the first step but I don't have a proof.

If that is the case there exist lists of any length.
 

I am sending you a txt file with a list of length 282. It starts with a 928-digit semiprime and it stops at 19.

So, the seed that was used is s=19.

The average number of primes that need to be checked for the n-th term is approximately n^3

***

Jeff wrote:

The earliest occurance for the next few chains are:

FIVE:  62 - 33 - 14 - 9 - 6 - 5
SIX:   177 - 62 - 33 - 14 - 9 - 6 - 5
SEVEN: 886 - 445 - 94 - 49 - 14 - 9 - 6 - 5
EIGHT: 2649 - 886 - 445 - 94 - 49 - 14 - 9 - 6 - 5
NINE:  5294 - 2649 - 886 - 445 - 94 - 49 - 14 - 9 - 6 - 5
TEN:   68653 - 5294 - 2649 - 886 - 445 - 94 - 49 - 14 - 9 - 6 - 5

 

***

Gennady wrote:

The solution to the problem must begin from the end. Then probably the maximum result will be limited only by the computer's capabilities and time. I started with a prime number 13=11+2, another solution with 19=17+2 (attached files 2+11.txt and 2+17.txt the results are presented in reverse order). I got 40+ solutions each. It took  a few minutes. You can also start with any  twin primes (31=29+2, 43=41+2 etc). I don't think there is a need to count further after finding a way to get a solution.

***

Paul wrote:

I have found a slightly longer list with 32 terms that stops at 8.

 

Start at 985414984565973192400560355621326682527785921607257278 = 2*492707492282986596200280177810663341263892960803628639

2 + 492707492282986596200280177810663341263892960803628639 = 492707492282986596200280177810663341263892960803628641 = 3359*146682790200353258767573735579238863133043453647999

3359 + 146682790200353258767573735579238863133043453647999 = 146682790200353258767573735579238863133043453651358 = 2*73341395100176629383786867789619431566521726825679

2 + 73341395100176629383786867789619431566521726825679 = 73341395100176629383786867789619431566521726825681 = 90239*812746097587258606409499969964421498094191279

90239 + 812746097587258606409499969964421498094191279 = 812746097587258606409499969964421498094281518 = 2*406373048793629303204749984982210749047140759

2 + 406373048793629303204749984982210749047140759 = 406373048793629303204749984982210749047140761 = 47339*8584318401183575977624157354025449397899

47339 + 8584318401183575977624157354025449397899 = 8584318401183575977624157354025449445238 = 2*4292159200591787988812078677012724722619

2 + 4292159200591787988812078677012724722619 = 4292159200591787988812078677012724722621 = 19469*220461205022948687082648244748714609

19469 + 220461205022948687082648244748714609 = 220461205022948687082648244748734078 = 2*110230602511474343541324122374367039

2 + 110230602511474343541324122374367039 = 110230602511474343541324122374367041 = 36899*2987360159122858168007916810059

36899 + 2987360159122858168007916810059 = 2987360159122858168007916846958 = 2*1493680079561429084003958423479

2 + 1493680079561429084003958423479 = 1493680079561429084003958423481 = 18059*82711117977818765380362059

18059 + 82711117977818765380362059 = 82711117977818765380380118 = 2*41355558988909382690190059

2 + 41355558988909382690190059 = 41355558988909382690190061 = 18749*2205747452605972728689

18749 + 2205747452605972728689 = 2205747452605972747438 = 2*1102873726302986373719

2 + 1102873726302986373719 = 1102873726302986373721 = 4751*232135071838136471

4751 + 232135071838136471 = 232135071838141222 = 2*116067535919070611

2 + 116067535919070611 = 116067535919070613 = 521*222778379883053

521 + 222778379883053 = 222778379883574 = 2*111389189941787

2 + 111389189941787 = 111389189941789 = 137*813059780597

137 + 813059780597 = 813059780734 = 2*406529890367

2 + 406529890367 = 406529890369 = 1307*311040467

1307 + 311040467 = 311041774 = 2*155520887

2 + 155520887 = 155520889 = 347*448187

347 + 448187 = 448534 = 2*224267

2 + 224267 = 224269 = 137*1637

137 + 1637 = 1774 = 2*887

2 + 887 = 889 = 7*127

7 + 127 = 134 = 2*67

2 + 67 = 69 = 3*23

3 + 23 = 26 = 2*13

2 + 13 = 15 = 3*5

3 + 5 = 8 = Stop

 

32 Semiprimes

{15,26,69,134,889,1774,224269,448534,155520889,311041774,406529890369,813059780734,111389189941789,222778379883574,
116067535919070613,232135071838141222,1102873726302986373721,2205747452605972747438,41355558988909382690190061,
82711117977818765380380118,1493680079561429084003958423481,2987360159122858168007916846958,
110230602511474343541324122374367041,220461205022948687082648244748734078,4292159200591787988812078677012724722621,
8584318401183575977624157354025449445238,406373048793629303204749984982210749047140761,
812746097587258606409499969964421498094281518,73341395100176629383786867789619431566521726825681,
146682790200353258767573735579238863133043453651358,492707492282986596200280177810663341263892960803628641,
985414984565973192400560355621326682527785921607257278}

 

***

Emmanuel wrote:

A set like  217, 38, 21, 10, 7 (the last element being not semiprime) will be called a Bergot sequence.
It is easy to make a longer Bergot sequence.
For instance : the smallest number  m  such that the Bergot sequence that starts with  m  has length  k  is found in the next table :

m          k
6          2
21          3
38          4
134          5
393          6
1774          7
19137          8
55694          9
167073          10
334142          11
14366257          12
205563598          13
The next  m  is > 10^9.
(I avoided squares of primes).

But there is an easier way to find much longer sequences.
If a Bergot sequence starts with an even number  m (that also can be the last element) you can find a Bergot sequence with second element  m   simply by writing  m  as the sum of two primes  p  and  q.
If Goldbach's conjecture is true then this will always be possible.  The first element of the longer Bergot sequence is then  p*q.
If in addition  p*q - 2  is a prime r then we can make a still longer Bergot sequence : 2r -> p*q -> m (eventually -> ...).

This allowed me to find a Bergot sequence of length 257 with starting number  m = 12636872722864741485263398163379401184796108268514170994542735721645753406067144835240238384300541076167530505242783
27851426164402720008240289112576882074511392299373927311914457543532742661066408691375343590614307692120759606354679840262
74949915521333833173686688289184491992767337862511369890098832307533768591072689565741563892488515636757105702089993940198
68293464192227171085993057990126125413346720999726583105294101044790753004428774712547799643262140009200059567492873935222
42952886915321812493146859264841229833128648980302664646130989936262189599511570638708463632491323640150228357297511367015
18865744336691218115391298454294845977785954839180028311376928509149406605728909629308286001825043351832283465169782791960
3153052100203310556599659643241094589611801398591699221593521227409286429692015413198 (811 digits)

which ends in (I give only the elements that are products of PROVED primes; the omitted numbers are not checked on that kind of factorization)

... -> 17633203310197638685735811042265528872901224971448066957371728201641451508934344605442380696450648709200164170046749634987
52702614905820899508398 ->  
17633203310197638685735811042265528872901224971448066957371728201641451508934344605442380696450648709200164170046749634987527
02614905820899508398 -> 8816601655098819342867905521132764436450612485724033478685864100820725754467172302721190348225324354600082085023374817493763
51307452910449754201 ->
7791339314680069055813417864361442250683209011854146359269580060640979289731415356022225672041396932281199095982975121284001
725955981612198 -> 3895669657340034527906708932180721125341604505927073179634790030320489644865707678011112836020698466140599547991487560642000
862977990806101 ->
6394635761027881281968436008300470159406056880195586702814288742156615619378091390657578656948105602741587120333887977101455
926207798 -> 3197317880513940640984218004150235079703028440097793351407144371078307809689045695328789328474052801370793560166943988550727
963103901 -> 1080361102931228232223868978827512537532827764276207505822673626563464586698737179489976086580475960848252084030337655660541
3598 -> 5401805514656141161119344894137562687664138821381037529113368132817322933493685897449880432902379804241260420151688278302706
801 -> 5783028538973835362018999350309302197848510480784856023005942894356176440636911757410112456122426266130873748528431910798 -> 2891514269486917681009499675154651098924255240392428011502971447178088220318455878705056228061213133065436874264215955401 -> 19955377673323609417659884989921608147221549081721944330209121161485505216174410304453834933720820247658278347574598 -> 9977688836661804708829942494960804073610774540860972165104560580742752608087205152226917466860410123829139173787301 -> 67945228341097349718622139033706760506443860978699018482281531237820840510232995473084035075897078794061660198 -> 33972614170548674859311069516853380253221930489349509241140765618910420255116497736542017537948539397030830101 -> 177635512711432085183771259022809950657111569155130271223069221898731079666385171878242592316553495357398 -> 88817756355716042591885629511404975328555784577565135611534610949365539833192585939121296158276747678701 -> 474836841446444742243399480945661165408827550949564742989989847309344288572473447808442152368158798 -> 237418420723222371121699740472830582704413775474782371494994923654672144286236723904221076184079401 -> 4933984927434534614636624627960485103689057866430773114466113669333779677180255697421415210198 -> 2466992463717267307318312313980242551844528933215386557233056834666889838590127848710707605101 -> 2017446808766611936189207414920845475405415584039458139472532001340244497464590592965998 -> 1008723404383305968094603707460422737702707792019729069736266000670122248732295296483001 -> 3500336264555383869381890101153875673462354272933590128830574055257746916785672598 -> 1750168132277691934690945050576937836731177136466795064415287027628873458392836301 -> 27505824895530213184097582086421880537666427831127238592705952122913662990798 -> 13752912447765106592048791043210940268833213915563619296352976061456831495401 -> 182789676202037594758686200550391954555924639024490215132484164614926998 -> 91394838101018797379343100275195977277962319512245107566242082307463501 -> 257414717689723946214024262215063208959783915775696051999138733998 -> 128707358844861973107012131107531604479891957887848025999569367001 -> 63122785112732698924478730312668761392786639474177550759967398 -> 31561392556366349462239365156334380696393319737088775379983701 -> 210452777283080833120440658778376735834694635138520613398 -> 105226388641540416560220329389188367917347317569260306701 -> 569317523989960539526915848644900788931105603576398 -> 284658761994980269763457924322450394465552801788201 -> 3058906306697689312838714410454124743072260198 -> 1529453153348844656419357205227062371536130101 -> 3283434097127459229897570045291230071798 -> 1641717048563729614948785022645615035901 -> 644063181076394513514627313709541598 -> 322031590538197256757313656854770801 -> 34855675997207193068223147195598 -> 17427837998603596534111573597801 -> 174245273384092987673557798 -> 87122636692046493836778901 -> 83053037837985218148598 -> 41526518918992609074301 -> 5146426932580576798 -> 2573213466290288401 -> 379585995919198 -> 189792997959601 -> 73591703998 -> 36795852001 -> 205563598 -> 102781801 -> 1447702 -> 723853 -> 55694 -> 27849 -> 9286 -> 4645 -> 934 -> 469 -> 74 -> 39 -> 16.

My conjecture is that this procedure of 'stepping back' is never ending.  Mathematica needs about one hour (or less) for the next enlargement.

 

Note that this procedure cannot work when  m  is a multiple of  6, bigger than 6.

But there are other non-multiples of 6 that make the procedure fail like : 32, 62, 68, 82, 148, 152, 158, 172, 242, 268, 272, 298, 326, 338, 358, 368, 374, 398, 542 , ...

(I think only finitely many).

But that's maybe a different problem.

 

***

Oscar wrote:

If the set of permitted semiprimes includes prime squares, there's an infinite, repeating sequence:
4, 4, 4, 4, 4, ...
due to the fact that 4 = 2*2 = 2+2.
Let's restrict our attention to squarefree semiprimes only.
These are the smallest semiprimes generating a sequence of length k, for 1<=k<=14:


k  n
1  6
2  21
3  38
4  134
5  393
6  1774
7  19137
8  55694
9  167073
10  334142
11  14366257
12  205563598
13  2261199457
14  56672219342


Some of the resulting sequences can be extended backwards: as an example, both entries for k=2 and for k=3 also belong to the given example sequence with n=217 and k=4.  Let's call a sequence "maximal" if it can't be extended backwards.
These are the smallest semiprimes generating a maximal sequence of length k, for 1<=k<=13:


1  6
2  57
3  669
4  177
5  393
6  2913
7  19137
8  455965
9  1345593
10  78219685
11  14366257
12  10783542613
13  2261199457


The sequence with n=56672219342 and k=14 isn't maximal, but exaustive search provided no maximal sequence with n<8*10^10 and k>13.
By repeatedly extending it backwards, I built a maximal sequence with length k=101 starting from the following 254-digit semiprime (64 digits per row):

7079046780924889195669195558485343478371187734741511593335212987
7216493645621925399858204716604218252028279896325793789110966126
1791620658188704908479637234210144477756644676388160225585826480
59633173976525305321972413013263123231761551262917327788898481 


The attached file P1074OV.txt contains the factorizations of the 101 resulting semiprimes.

***

Fred wrote:

I conjecture that it is possible to construct an infinite set of semi-prime stairs.

Instead of starting with a large number and working down, we begin with a small number and flare out.

Let n = 2 * p
To add a stair, we need two primes p1 + p2 = n
Goldbach's conjecture states that every even number n >= 6 can be expressed as the sum of two primes. Those familiar with number theory know that statistically
the expected number of prime pair sum reps increases as n gets larger.

Then, to add the next stair, we need for 2 + x = p1 * p2
where x = p1 * p2 - 2 is a prime.

Then, we attempt to repeat the cycle.

So to "advance", I would find p1 and p2 = n such that p1, p2 and p1 * p2 -2
were all primes.

To bootstrap the list below,  I started with (2,37) by hand and
and then from (47,887).  I programmed a search which begin with p1 = 107
with p1 increasing by 30 if a match was not found.
Note: There were no dead ends on this list, each time a prime trio was found
I just continued outward to end up with the massive result at the end.
I killed this after running my program one night and the larger primes became extremely large.  I found a stair sequence of length of 351.  The final number was the product of 2 and 1203-digit prime:

(2,
15472008434623641890442190942244153632686176268591793702004356547870811469860623
0075799297350511140229293682334217194800164216757411447567612040007787129946353661206837306908802072334472402
1573269867077113196426761778975830083465102553119260128664654419844541205116032762743627046622893196087661664
141611327326583177037911289910094103839139815395405973003863548675257685931956042337812618890330852430
0240929550188080365558762108494073968110220173971353033954424554066999962145191388026940950641370531838122523
3480968289314426227217791029396424955221051722404906120922815957651719611096476661002171674859727141776213405
5348976309793637436988730187219815552188780268594966124237234845572062078794955442101049269089040056039846642
9546554392846377963155764749054640496419085994396110633024305418348774800
2141490696196639515638855753070659435064542111978352430818208851251931067762553631737471088698734044094710215
4998461072197942353103848533683055333347196256330974921509528001627819663785640393065024832020135900342196812
9385613747584661821557198805176218961970386897366618303779001123540790767241772241645294071179015079734443049
2153354357104324597456652856660650826761268261811836160904720613345693971867)

but I conjecture that the the sequence could have continued indefinitely.  
At each "step", when trying to find a prime only one of the massive number of choices has to create a prime trio.  
Note: That through these steps the largest "p1" was only 9 digits, less than the 100th root of p2.

See in the following .txt file the complete solution.

 

***