|
The answer for the length of the 100th number is 511,247,092,564 digits.
The length escalates frighteningly quickly. The LENGTH of the 3000th number in the chain is, get this, 4029857719515768641307384677908679928310793769651641917926155107836565892187598804862177357001771122238068645667821323998368650130801806344030981271295995422208436642014734696538407619447946889047668430308242548524802874469136450965097114152481264391293269162985708430576259447637028591596189605329702198409448541645531801518246316682171504624370 digits long. That's not the number. That's how long it is in digits!
That's more digits than there are the estimated number of atoms in the observable universe, by many orders of magnitude!
System.ItDidntWorkException: Something didn't work as expected.
C# - How to debug code[ ^].
Seriously, go read these articles.
Dave Kreskowiak
modified 4-Dec-17 12:28pm.
|
|
|
|
|
I've left my totally brute-force string-based solution running for 4 days and it's only on the 64th iteration having got up to 50 within an hour - so, yeah, that rather underlines how it can never really be achieved in reasonable time without an awful lot more finesse.
I really enjoyed this as a coding challenge even though I didn't get remotely close to cracking it. A simple looking task on the surface but one that soon reveals itself to be monumentally problematic.
98.4% of statistics are made up on the spot.
|
|
|
|
|
I got the same value for the 100th but it took me almost 21h with iterators.
Did you actually calculate the 3000th????
Paulo Gomes
Measuring programming progress by lines of code is like measuring aircraft building progress by weight.
—Bill Gates
Everything should be made as simple as possible, but not simpler.
—Albert Einstein
|
|
|
|
|
No, I didn't. I don't have an algorithm to go that high in my lifetime. At least not yet. I'm still working on the problem in some spare time.
There is only a single place on the entire 'net where that number is listed, here[^]. Seems to be down right now though.
System.ItDidntWorkException: Something didn't work as expected.
C# - How to debug code[ ^].
Seriously, go read these articles.
Dave Kreskowiak
|
|
|
|
|
That's quite a number.
Got me spending electricity for almost 21h
Paulo Gomes
Measuring programming progress by lines of code is like measuring aircraft building progress by weight.
—Bill Gates
Everything should be made as simple as possible, but not simpler.
—Albert Einstein
|
|
|
|
|
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.
|
|
|
|
|
|
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 
|
|
|
|
|
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 <chrono>
#include <ctime>
#include <boost multiprecision="" cpp_int.hpp="">
// g++ xxx.cpp -std=c++11 -march=corei7
using namespace std;
using namespace boost::multiprecision;
typedef number<cpp_int_backend<1024 *="" 16,="" 1024="" unsigned_magnitude,="" unchecked,="" void=""> > uint16384_t;
uint32_t maxLevel = 100;
static chrono::time_point<chrono::system_clock> 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<uint32_t> 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},
{89, 92},
{1},
{3}, // 26-30
{4},
{2, 61, 29, 85},
{5},
{28},
{24, 33, 61, 29, 91}, // 31-35
{24, 33, 61, 29, 90},
{7},
{8},
{9},
{10}, // 36-40
{21},
{22},
{23},
{11},
{19}, // 41-45
{12},
{13},
{14},
{15},
{18}, // 46-50
{16},
{17},
{20},
{6, 61, 29, 92},
{26}, // 51-55
{27},
{25, 29, 92},
{25, 29, 67},
{25, 29, 85},
{25, 29, 68, 61, 29, 89}, // 56-60
{61},
{33},
{40},
{41},
{42}, // 61-65
{43},
{38, 39},
{44},
{48},
{54}, // 66-70
{49},
{50},
{51},
{52},
{47, 38}, // 71-75
{47, 55},
{47, 56},
{47, 57},
{47, 58},
{47, 59}, // 76-80
{47, 60},
{47, 33, 61, 29, 92},
{45},
{46},
{53}, // 81-85
{38, 29, 89},
{38, 30},
{38, 31},
{34},
{36}, // 86-90
{35},
{37} // 91-92
};
uint16384_t levelCounts[92];
uint16384_t evolvedLevelCounts[92];
int main(int argc, char** argv)
{
if (argc != 1)
{
maxLevel = atoi(argv[1]);
if (maxLevel < 9)
{
maxLevel = 10;
}
}
start = chrono::system_clock::now();
time_t start_time = chrono::system_clock::to_time_t(start);
cout << "Starting run of " << maxLevel << " levels at " << ctime(&start_time) << endl;
for (auto& sequence: levelEvolution)
{
for (auto& seq: sequence )
{
--seq; // Adjust indices for 0-based array
}
}
for (uint32_t i = 0; i < 92; ++i)
{
levelCounts[i] = 0;
}
// Prime the counts for the starting level (9).
levelCounts[23] = 1;
levelCounts[38] = 1;
uint16384_t * workingCounts = levelCounts;
uint16384_t * evolvedCounts = evolvedLevelCounts;
for (uint32_t i = 9; i <= maxLevel; ++i)
{
for (uint32_t j = 0; j < 92; ++j)
{
evolvedCounts[j] = 0;
}
for (uint32_t j = 0; j < 92; ++j)
{
if (workingCounts[j] != 0)
{
for (auto& level: levelEvolution[j])
{
evolvedCounts[level] += workingCounts[j];
}
}
}
uint16384_t totals = 0;
for (uint32_t j = 0; j < 92; ++j)
{
if (evolvedCounts[j] != 0)
{
totals += evolvedCounts[j] * levelSize[j];
}
}
cout << i << " " << totals << endl;
swap(workingCounts, evolvedCounts);
}
timeFinished = chrono::system_clock::now();
chrono::duration<double> 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;
}
|
|
|
|
|
Interesting. I'll have to dig into this when I have time.
I never ran into Conways work on this sequence, probably because when I originally looked at the problem, it was before the Internet. 
|
|
|
|
|
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
35479339047326507688232784063349970121235999395713604108127449612932001426177528
23619141084620201788080083140987338010778250161606960215149603259861170492658302
12975452002526132439169063773862701572890207737639046620470189466430502245679979
16198357370515859170453073684972699761812225970758494544050009917709503381557111
73543734113588277788892462233549700462320186861810656981116575842484370850783857
37156970395888447961935400339982806803163931351754091377833208507592575036288539
43619653259571587881116891400191681996965087013346716456940951616231526342337559
22241131826468717844288886151665338872587683127247296643882994293525890623632269
98899639749620311060570650319390387466685081217222229801898949627461276386554685
75925868571795637003613173158189546475397882560651029182246939487648119509781384
83254335022715944566042014377015037012349598676358164527637612495305877589262579
03025748995759629880604102212835811596890977542757761897823254135797701029135648
28324492418638056252913540819652284351393709299122041013948984025392618267020987
17716299323126735895308105721886983055589269483847585894614437157473289506651755
20127994882222268865020612535412447648431213938031098108934933403092592283945592
73307000676107614091852393510174723997390157033476366980121917558567579790804621
20421454810519341754334192575220517893409416476768669110220447974669839721344355
57731809058641546041338288083422963287728556049349369149409545485068038045669290
50244833541934020160968155682656526425764519156103546712484406437600149172250665
24410006792663740299986552127547781411567919529620245672391639259693048418190886
93816150811438892723455573117860779553736835735824130699585567369234242121913990
37529048872399969032088678439419617810194984208040034198565129784389572247225698
36214121761026386502166863108118461662943119877095043507008571437742362072559239
97006356865928904357981519736398094731789012715571211268539057197421110638828135
53906541822964030553384835401343893791957040661434347231499413811074712905565923
32719307598487738031259070058790951140359030037330458646767016580498283331087358
78462166906603077546284766094279575721162305387953903063203373016734903308334724
1817304220792889912794154410981053798092739160
|
|
|
|
|
|
|
They still need a head.
Why do all these robot makers not give the things at least a vestigial head?
|
|
|
|
|
It's just a small gymnast in a costume.
There are two kinds of people in the world: those who can extrapolate from incomplete data.
There are only 10 types of people in the world, those who understand binary and those who don't.
|
|
|
|
|
Can't wait until we become their pets.
Jeremy Falcon
|
|
|
|
|
That's what we have graphite bombs for.
|
|
|
|
|
Very impressive engineering. The amount of stress on those joints is really quite high. It is one of the problems with robotics, the materials available to man are really not as good as bone and cartilage.
|
|
|
|
|
|
Growing up as the "geek kid" that would always be picked on, I quite related to Gomer.
|
|
|
|
|
Surprise! Surprise! Surprise! 
|
|
|
|
|
Not really at 87 it wasn't.
|
|
|
|
|
Just bought a bag of nuts form Tesco with a flash on the front advising of an important allergen update. Looking at the back of the pack with some urgency, I saw the following:
Ingredients: Almonds, Cashew Nuts, Brazil Nuts, Hazelnuts, Peanuts
Allergy Advice For allergens, see ingredients in bold. Also, may contain other nuts.
Now, the only thing that I can think of that may have been added is "Also, may contain other nuts" - at which point I'm somewhat at a loss to understand how anyone with a nut allergy would go anywhere near a packet bearing the title "Unsalted Mixed Nuts."
Am I missing something?
98.4% of statistics are made up on the spot.
|
|
|
|
|
That's the lawyer equivalent of "paid per line of code".
System.ItDidntWorkException: Something didn't work as expected.
C# - How to debug code[ ^].
Seriously, go read these articles.
Dave Kreskowiak
|
|
|
|
|
PeejayAdams wrote: Am I missing something?
Yes. Without that warning anyone with an allergy could buy a pack just so they could sue Tesco.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
![Rose | [Rose]](https://codeproject.freetls.fastly.net/script/Forums/Images/rose.gif)
