Puzzle 982. Home primes second class

Problems & Puzzles: Puzzles

Puzzle 982. Home primes second class

Igor Schein sent the following nice puzzle

Define the following iterative process:

1) Start with an integer N_0 as a seed

2) Factor N_0 into prime factors, sort them in ascending order, strip the smallest and concatenate the rest.

3) Repeat

Clearly the iteration terminates either immediately after a 2-prime is reached or right when a prime is reached

There're quite a few seeds producing sequences which terminates after 30 iterations, the smallest being 1290240:

N = 1290240 = 2*2*2*2*2*2*2*2*2*2*2*2*3*3*5*7

N_1 = 222222222223357 = 47*6361*743300171

N_2 = 6361743300171 = ...

...

N_30 = 114747277701901451 is prime

Q1 - are there longer sequences?
Q2 - if so, are there arbitrary long sequences?

Contributions came from Giovanni Resta and Emmanuel Vantieghem, along the week 21-28 Dec. 2019

***

Giovanni wrote

For puzzle 982 it is s not difficult to find longer sequences.
For example, one of length 34 starts at 894564 and the first of length
60 at 88530880.

I think there is no limit to the length, since it is rather easy to
create longer sequences
going backward, because the fact that we delete the first prime gives a
lot of freedom.

For example, take the number 227125339 which produces a sequence of
length 41.
Since 227 and 125339 are prime numbers, then any number equal to
p*227*125339 with
p a prime <= 227 will give a sequence of length 42 since from
p*227*125339 in one step we obtain
227125339. Constructing seeds of long sequences boils down to find if
the representation of
a given number can be "partitioned" in a sequence of non-decreasing
primes. On the contrary,
computing the length of the sequence starting from very large numbers
may be prohibitive since it involves
prime factorization.

For example, one sequence of length 100 starts at
734235571954395799425054 and one of length 1000 starts at
63497039014690072131736443494830362628662746495573725400055123481212341053233427807
43117426753058831807639089398691762864950154088315463308590657896654286495708034471
22274235870138203426642855382712370978614288361509448523672079671041187067358318142
76092621459752183553931787936226347457715308206740680334865931019052366209186978296
2739944704491339683371074378021099917348709597178600793052469983003707125938214496242058.

The sequence of length 100 for 734235571954395799425054 is copied below.
I can send the one for 1000 if needed.

all the best,
Giovanni

734235571954395799425054 = 2*3*3*41*173*7727*744255485037973
33411737727744255485037973 = 17*7057*278503094363912806517
7057278503094363912806517 = 3*3*3*73*212447*2001997*8418536653
337321244720019978418536653 = 13*152837*470731*1808557*199419139
1528374707311808557199419139 = 1019*65119*94597*243484080682267
6511994597243484080682267 = 3*107*401*50589993841280630827
10740150589993841280630827 = 149*509*141614042404422954347
509141614042404422954347 = 11*76184833*607543515604769
76184833607543515604769 = 3*3*3*27941*4212211*23974673197
3327941421221123974673197 = 11*95003*676421*4707914708129
950036764214707914708129 = 3*31907101*9925029585260743
319071019925029585260743 = 103*3541*1195067*732035183623
35411195067732035183623 = 23*54517*28241047322081453
5451728241047322081453 = 3*523433*3471777184502647
5234333471777184502647 = 3*59*29572505490266579111
5929572505490266579111 = 11*183573251*2936441137351
1835732512936441137351 = 3*41*14924654576719033637
4114924654576719033637 = 131*653*48103581293346259
65348103581293346259 = 3*73*151*487*6719*7547*80021
731514876719754780021 = 3*4783*148171997*344060957
4783148171997344060957 = 19*383*64157*115133*88985161
3836415711513388985161 = 149*8034589*3204614007401
80345893204614007401 = 3*53*505320083047886839
53505320083047886839 = 3*17*1049123923197017389
171049123923197017389 = 3*6983*8165025725485561
69838165025725485561 = 3*18211*34602193*36943169
182113460219336943169 = 373*20261*38953*618630641
2026138953618630641 = 7*3802957*76111410659
380295776111410659 = 3*61949*2046284180597
619492046284180597 = 11*19*73*1109*36612976969
1973110936612976969 = 17*1709*67914189123773
170967914189123773 = 29*383*15392807615839
38315392807615839 = 3*3*4257265867512871
34257265867512871 = 23*109*13664645340053
10913664645340053 = 3*709*22441*228644579
70922441228644579 = 7*47*435559*494926589
47435559494926589 = 7*31*61*529603*6766499
31615296036766499 = 1399*68507*329871343
68507329871343 = 3*11*19*1493*73182913
1119149373182913 = 3*3*41*3032925130577
3413032925130577 = 7*103*988511*4788767
1039885114788767 = 13*53*71*21257284793
537121257284793 = 3*1487*18523*6500231
1487185236500231 = 47*970217*32613569
97021732613569 = 211*35863*12821533
3586312821533 = 13*179483*1537027
1794831537027 = 3*31*19299263839
3119299263839 = 11*11*397*64935347
1139764935347 = 23*32779*1511791
327791511791 = 29*5639*2004461
56392004461 = 13*17*1291*197651
171291197651 = 7*17*677*2126177
176772126177 = 3*3*20939*938027
320939938027 = 23*43*8117*39979
43811739979 = 7*60661*103177
60661103177 = 599*1013*99971
101399971 = 53*173*11059
17311059 = 3*3*1297*1483
312971483 = 11*227*125339
227125339 = 7*7*7*499*1327
774991327 = 11*11*137*46751
1113746751 = 3*3*13*9519203
3139519203 = 3*3*3*31*3750919
33313750919 = 17*23*83*919*1117
23839191117 = 3*3*7*29*3221*4051
372932214051 = 3*29*31*5851*23633
2931585123633 = 3*53*181*9941*10247
53181994110247 = 23*41*137*411654017
41137411654017 = 3*3*7*97*227*1123*26407
3797227112326407 = 3*3*617*26399*25903081
36172639925903081 = 19*59*32268189050761
5932268189050761 = 3*3*47*14024274678607
34714024274678607 = 3*3*17*37*83*73881161689
317378373881161689 = 3*3*116989*301432303589
3116989301432303589 = 3*19*149*2753*76537*1741793
191492753765371741793 = 11*14551*108637*11012579449
1455110863711012579449 = 3*7*7*7*43*4297*7653267603511
7774342977653267603511 = 3*7*11*317*106167711058124293
711317106167711058124293 = 3*17*487*25733*1112944981965133
17487257331112944981965133 = 3*29*47*17851*239575299826917647
294717851239575299826917647 = 19*37*43591*3908029*2460914398291
374359139080292460914398291 = 29*13187*978913765856897887717
13187978913765856897887717 = 3*782707307*5616394445203877
7827073075616394445203877 = 19*887*5387*18979*1764977*2573729
88753871897917649772573729 = 3*12442957*2377620043689980599
124429572377620043689980599 = 427327*1726509893*168653051509
1726509893168653051509 = 3*3*3*3*40808393*522317478973
33340808393522317478973 = 3*7*13*283*431545947961044247
713283431545947961044247 = 11*97*11212987081*59617861661
971121298708159617861661 = 7*13*73*146187159221460126127
1373146187159221460126127 = 3*3*7*73*298574948284240369673
3773298574948284240369673 = 433*4943*16979*103831841489773
494316979103831841489773 = 757*7183783*90898442837183
718378390898442837183 = 3*23*109*3547*392321*68639629
23109354739232168639629 = 17*977*1021500239*1362090179
97710215002391362090179 = 3*22343*131317*11100851070203
2234313131711100851070203 = 23*29*31*6311*10103*1694759109983
29316311101031694759109983 = 3*29*47*60133693369*119226922063
294760133693369119226922063 = 3*109*6121*310823*2725187*173855789
10961213108232725187173855789 = 17*644777241660748540421991517
644777241660748540421991517 = 644777241660748540421991517 (prime)

***

Emmanuel wrote

I made a record list for the length of the iterative process (I took 1 < n0 < 500000000) :

n0 Length
4 1
8 2
28 3
172 4
224 5
376 6
408 7
1404 8
4064 9
4608 22
332028 27
602300 29
894564 34
2077752 35
3826414 44
4181108 45
29116750 46
43954440 47
58661376 54
88530880 60
185969072 61
199070714 70
479392896 77

There is a length of 83 for n0 = 32372821974135720 (found 'by accident').
But there can be bigger lengths for smallest n0.

There might be arbitrary big lengths and it is also possible that the iterative process never ends.

***

Records | Conjectures | Problems | Puzzles