just for grins, here's level 40,000: 46356339851862148708778774137227130707236922642323608349807546756690214021600388 77796951548157965850907625470807504140268863386308875922216544076356172070784955 08689718922212371460438163457388805733846522157214621807992599715760660832053427 95799716796784140139028191025327274480096058745930537059476779301586186635483950 90114530007994024079764737450688935431742180956428699222647161605621043699723423 61357066032477782438136175391064066156733572693341827200463458908139533006189675 87500224082769814420516369456634022701442916302164734548555208715379599132991223 83546459911689173268242490107968480175270623804963957320188660754924681073968253 61937026883388010961558447940558444326814415625117941939452453236267175673340533 90009250682583549202001651118978466160265604335024521313599618289656307411831446 28861792280419299623490456434975101922619363730362392023785772196827723773921632 62531924787257608981890821638529080598561844791723400941061819348082078146338316 11533919022563936187509504021127351555514697579233824510041350209039730164643961 36542447221369089499771980454964375458365136995788788108390457745822089660593406 53269351626804707171480876062357074568859408144337576841853000283635263502643163 31534772155228950638910003746088045199925455245231901186938901605547509975145331 94788627189651125394551375551853272720730531013551025773362890692709302331864484 53904666521428499502734466208297755671892067819533624560549025578871965785953627 13628246143232542565967972065062492189428173368151413785169468562992000671896867 80275509827982732169801024311606965773426916151467275538759223775063671730434004 44433560341699842212946445837712590857742084989069463164327617310338639393468072 52275796519246602305431321549587373309794296507457642514625495684703088787933252 40566584074063817540455270668276854534974651331477347465734116702589482800704181 14459105359156696244278859839469851135572847495341380550121954457575018931579263 16060428524241726501353949632363901162306796764139520565316321061913689859142349 16492623807380681749381864725966760375534820526237529806450230956355225089537725 46247486530348927612746499479621157034976472271550730053568003956971067625207324 86574141147180481705193008142513527499146179647011276345211836681225894560245484 05264324766933842446243154060023313380969128238572821640145539472079456705550288 72432153951347093697705896569175696140299882824511462005903518484136384802417840 354793390473265076882327840633499701212359993957136041081274

Just for grins, here's the count for level 40,000: 40000 4635633985186214870877877413722713070723692264232360834980754675669021402160038877796951548157965850907625470807504140268863386308875922216544076356172070784955086897189222123714604381634573888057338465221572146218079925997157606608320534279579971679678414013902819102532727448009605874593053705947677930158618663548395090114530007994024079764737450688935431742180956428699222647161605621043699723423613570660324777824381361753910640661567335726933418272004634589081395330061896758750022408276981442051636945663402270144291630216473454855520871537959913299122383546459911689173268242490107968480175270623804963957320188660754924681073968253619370268833880109615584479405584443268144156251179419394524532362671756733405339000925068258354920200165111897846616026560433502452131359961828965630741183144628861792280419299623490456434975101922619363730362392023785772196827723773921632625319247872576089818908216385290805985618447917234009410618193480820781463383161153391902256393618750950402112735155551469757923382451004135020903973016464396136542447221369089499771980454964375458365136995788788108390457745822089660593406532693516268047071714808760623570745688594081443375768418530002836352635026431633153477215522895063891000374608804519992545524523190118693890160554750997514533194788627189651125394551375551853272720730531013551025773362890692709302331864484539046665214284995027344662082977556718920678195336245605490255788719657859536271362824614323254256596797206506249218942817336815141378516946856299200067189686780275509827982732169801024311606965773426916151467275538759223775063671730434004444335603416998422129464458377125908577420849890694631643276173103386393934680725227579651924660230543132154958737330979429650745764251462549568470308878793325240566584074063817540455270668276854534974651331477347465734116702589482800704181144591053591566962442788598394698511355728474953413805501219544575750189315792631606042852424172650135394963236390116230679676413952056531632106191368985914234916492623807380681749381864725966760375534820526237529806450230956355225089537725462474865303489276127464994796211570349764722715507300535680039569710676252073248657414114718048170519300814251352749914617964701127634521183668122589456024548405264324766933842446243154060023313380969128238572821640145539472079456705550288724321539513470936977058965691756961402998828245114620059035184841363848024178403547933904732650768823278406334997012123599939571360410812744961293200142617752823619141084620201788

Here's the code, it allows a param to specify the level, default is 100. uint16384_t allows computation to slightly above level 40000. #include #include #include // g++ xxx.cpp -std=c++11 -march=corei7 using namespace std; using namespace boost::multiprecision; typedef number > uint16384_t; uint32_t maxLevel = 100; static chrono::time_point start, timeFinished; const uint32_t levelSize[] = { 4, 7, 12, 12, 4, 5, 12, 6, 8, 10, // 1-10 10, 14, 12, 14, 18, 42, 42, 26, 14, 28, // 11-20 14, 24, 24, 5, 7, 10, 10, 8, 2, 9, // 21-30 9, 23, 2, 6, 32, 32, 8, 3, 5, 6, // 31-40 10, 18, 18, 6, 10, 8, 7, 8, 12, 20, // 41-50 34, 34, 20, 10, 7, 7, 11, 13, 21, 17, // 51-60 2, 1, 4, 7, 14, 14, 7, 4, 6, 8, // 61-70 10, 16, 28, 28, 9, 12, 12, 16, 18, 24, // 71-80 23, 16, 6, 5, 15, 6, 10, 10, 3, 27, // 81-90 27, 5 }; // 91-92 vector levelEvolution[] = { {63}, {64, 62}, {65}, {66}, {68}, // 1-5 {69}, {84, 55}, {70}, {71}, {76}, // 6-10 {77}, {82}, {78}, {79}, {80}, // 11-15 {81, 29, 91}, {81, 29, 90}, {81, 30}, {75, 29, 92}, {75, 32}, // 16-20 {72}, {73}, {74}, {83}, {86}, // 21-25 {87}, {88},

John Conway did extensive research a while back on this sequence. He discovered that after a certain point (level 8), each level can be written as a series of 92 subsequences that in turn evolve into one or several of the 92 subsequences. So it's possible to write a program that just keeps track of the number of times a particular subsequence has been seen, and then "evolve" it for the next level, which is iterating over a 92 element array for each level and creating a new 92 element array for the next. Since the size of each subsequence is known, calculating the length of a particular level is as simple as multiplying the count of each subsequence by the length, and adding them all together. I can post the source here if that's kosher. It's not pretty but it works :)

I don't know if anyone is looking at this anymore due to it being an old topic, but there is a way to calculate the length of these sequences in linear time. For example, it's possible to calculate the length of sequences 1..5000 in < 1 sec.

My runtimes are about 3500 sec at l=100 and about 50000 sec at l=110 for an increase of about 14.3x. So from l=100 to l=200 is 14.3 ^ 10 x the time, or 347,636,939,799 hours. ~39 million years, give or take :) l=3000? heh. I think that's a pretty good definition of "forever".

No problem. It was an interesting challenge! FWIW, I was looking further at the code and at how to optimize it. One interesting thing I found is that if the order of ProcessLevel() calls is reversed we get the same sequences but reversed! This means that the initial prefix for each level is always 1 and can be initialized as such, which then means the check for currentOccurrence != 0 in ProcessLevel() can be removed. Doesn't seem like much, but when that function is executed trillions of times it makes a noticeable difference. You must have a fast machine, 100 takes quite a bit longer for me.

I wish I could say that this is exploiting some underlying pattern, but it's really just a more efficient brute force implementation. It's more like a depth-first tree traversal - you never have to compute and store the entire string at one level before working on the next.

OK, here it is... #include #include #include using namespace std; #define maxLevel 100 static uint32_t currentLevel = 0; static chrono::time_point start, timeFinished; class LevelProcessor { public: LevelProcessor() : currentOccurrence(0), currentPrefix(0), myLevel(currentLevel++), totalSize(0) { } void ProcessLevel(uint32_t prefix); void FinishLevel(); uint32_t currentOccurrence; uint32_t currentPrefix; const uint32_t myLevel; uint64_t totalSize; }; static LevelProcessor processors[maxLevel]; void LevelProcessor::ProcessLevel(uint32_t prefix) { if (prefix == currentPrefix) { ++currentOccurrence; return; } if (currentOccurrence != 0) { if (myLevel < maxLevel - 1) { processors[myLevel + 1].ProcessLevel(currentOccurrence); processors[myLevel + 1].ProcessLevel(currentPrefix); } ++totalSize; } currentPrefix = prefix; currentOccurrence = 1; } void LevelProcessor::FinishLevel() { ++totalSize; if (myLevel < maxLevel - 1) { processors[myLevel + 1].ProcessLevel(currentOccurrence); processors[myLevel + 1].ProcessLevel(currentPrefix); } chrono::time_point timeFinished = chrono::system_clock::now(); chrono::duration elapsed_seconds = timeFinished - start; time_t end_time = chrono::system_clock::to_time_t(timeFinished); cout << "level " << myLevel + 1 << " is done, size = " << totalSize * 2 << " at " << "elapsed time: " << elapsed_seconds.count() << "secs" << endl; if (myLevel < maxLevel - 1) processors[myLevel + 1].FinishLevel(); } int main() { start = chrono::system_clock::now(); processors[1].ProcessLevel(1); processors[1].FinishLevel(); timeFinished = chrono::system_clock::now(); chrono::duration elapsed_seconds = timeFinished - start; time_t end_time = chrono::system_clock::to_time_t(timeFinished); cout << "finished computation at " << ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "secs" << endl; } So much for my indenting, oh well.

Since we only need to compute the length, storing the entire string isn't necessary. Furthermore, the computation can be done recursively and requires very little code/storage for each level of recursion. The memory footprint while running was about 16k IIRC. I removed some extraneous code and got the runtime at l=100 to about 1.5 hours. Probably could optimize it even more, but I don't see the point. I'd post code here but it seems to be discouraged.

level 1 size = 1
level 2 size = 2
level 3 size = 2
level 4 size = 4
level 5 size = 6
level 6 size = 6
level 7 size = 8
level 8 size = 10
level 9 size = 14
level 10 size = 20
level 11 size = 26
level 12 size = 34
level 13 size = 46
level 14 size = 62
level 15 size = 78
level 16 size = 102
level 17 size = 134
level 18 size = 176
level 19 size = 226
level 20 size = 302
level 21 size = 408
level 22 size = 528
level 23 size = 678
level 24 size = 904
level 25 size = 1182
level 26 size = 1540
level 27 size = 2012
level 28 size = 2606
level 29 size = 3410
level 30 size = 4462
level 31 size = 5808
level 32 size = 7586
level 33 size = 9898
level 34 size = 12884
level 35 size = 16774
level 36 size = 21890
level 37 size = 28528
level 38 size = 37158
level 39 size = 48410
level 40 size = 63138
level 41 size = 82350
level 42 size = 107312
level 43 size = 139984
level 44 size = 182376
level 45 size = 237746
level 46 size = 310036
level 47 size = 403966
level 48 size = 526646
level 49 size = 686646
level 50 size = 894810
level 51 size = 1166642
level 52 size = 1520986
level 53 size = 1982710
level 54 size = 2584304
level 55 size = 3369156
level 56 size = 4391702
level 57 size = 5724486
level 58 size = 7462860
level 59 size = 9727930
level 60 size = 12680852
level 61 size = 16530884
level 62 size = 21549544
level 63 size = 28091184
level 64 size = 36619162
level 65 size = 47736936
level 66 size = 62226614
level 67 size = 81117366
level 68 size = 105745224
level 69 size = 137842560
level 70 size = 179691598
level 71 size = 234241786
level 72 size = 305351794
level 73 size = 398049970
level 74 size = 518891358
level 75 size = 676414798
level 76 size = 881752750
level 77 size = 1149440192
level 78 size = 1498380104
level 79 size = 1953245418
level 80 size = 2546222700
level 81 size = 3319186080
level 82 size = 4326816254
level 83 size = 5640348764
level 84 size = 7352630884
level 85 size = 9584715106
level 86 size = 12494412020
level 87 size = 16287462624
level 88 size = 21231903676
level 89 size = 27677468012
level 90 size = 36079732206
level 91 size = 47032657188
level 92 size = 61310766500
level 93 size = 79923316046
level 94 size = 104186199146
level 95 size = 135814773100
level 96 size = 177045063068
level 97 size = 230791944956
level 98 size = 300854953626
level 99 size = 392187941864
level 100 size = 511247092564
finished computation at Fri Dec 1 16:48:41 2017
elapsed time: 7205.75secs