在 C++ 程序中获取超出输出限制
Getting OUTPUT LIMIT EXCEED in C++ Program
我正在解决 Weird Algorithm 问题：
Consider an algorithm that takes as input a positive integer n. If n
is even, the algorithm divides it by two, and if n is odd, the
algorithm multiplies it by three and adds one. The algorithm repeats
this, until n is one. For example, the sequence for n=3 is as follows:
3→10→5→16→8→4→2→1
Your task is to simulate the execution of the algorithm for a given
value of n.
Input
The only input line contains an integer n.
Output
Print a line that contains all values of n during the algorithm.
Constraints
1≤n≤10^6
问题已解决，但面临 OUTPUT LIMIT EXCEED 问题。搜索了很多但找不到任何方法来摆脱这个问题。
它工作正常，直到我输入 = 270271，它给出了意外的输出，包括负值。
#include <iostream>
using namespace std;
void fun(int n) {
if (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
cout << " " << n;
fun(n);
}
}
int main() {
int n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
尽量不要在这里使用递归，如果递归深度太多，它可能会导致二进制文件崩溃，而且 Collatz 序列有时可能会很长，请尝试使用 while 循环。溢出的堆栈可能会产生这种超出输出。
此外，在某些输入上，您可能会溢出 int。请改用 uint64_t。就像我下面的代码一样。
完整更正的程序：
#include <iostream>
#include <cstdint>
using namespace std;
void fun(uint64_t n) {
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
cout << " " << n;
}
}
int main() {
uint64_t n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
输入：
270271
输出：
270271 810814 405407 1216222 608111 1824334 912167 2736502 1368251 4104754 2052377 6157132 3078566 1539283 4617850 2308925 6926776 3463388 1731694 865847 2597542 1298771 3896314 1948157 5844472 2922236 1461118 730559 2191678 1095839 3287518 1643759 4931278 2465639 7396918 3698459 11095378 5547689 16643068 8321534 4160767 12482302 6241151 18723454 9361727 28085182 14042591 42127774 21063887 63191662 31595831 94787494 47393747 142181242 71090621 213271864 106635932 53317966 26658983 79976950 39988475 119965426 59982713 179948140 89974070 44987035 134961106 67480553 202441660 101220830 50610415 151831246 75915623 227746870 113873435 341620306 170810153 512430460 256215230 128107615 384322846 192161423 576484270 288242135 864726406 432363203 1297089610 648544805 1945634416 972817208 486408604 243204302 121602151 364806454 182403227 547209682 273604841 820814524 410407262 205203631 615610894 307805447 923416342 461708171 1385124514 692562257 2077686772 1038843386 519421693 1558265080 779132540 389566270 194783135 584349406 292174703 876524110 438262055 1314786166 657393083 1972179250 986089625 2958268876 1479134438 739567219 2218701658 1109350829 3328052488 1664026244 832013122 416006561 1248019684 624009842 312004921 936014764 468007382 234003691 702011074 351005537 1053016612 526508306 263254153 789762460 394881230 197440615 592321846 296160923 888482770 444241385 1332724156 666362078 333181039 999543118 499771559 1499314678 749657339 2248972018 1124486009 3373458028 1686729014 843364507 2530093522 1265046761 3795140284 1897570142 948785071 2846355214 1423177607 4269532822 2134766411 6404299234 3202149617 9606448852 4803224426 2401612213 7204836640 3602418320 1801209160 900604580 450302290 225151145 675453436 337726718 168863359 506590078 253295039 759885118 379942559 1139827678 569913839 1709741518 854870759 2564612278 1282306139 3846918418 1923459209 5770377628 2885188814 1442594407 4327783222 2163891611 6491674834 3245837417 9737512252 4868756126 2434378063 7303134190 3651567095 10954701286 5477350643 16432051930 8216025965 24648077896 12324038948 6162019474 3081009737 9243029212 4621514606 2310757303 6932271910 3466135955 10398407866 5199203933 15597611800 7798805900 3899402950 1949701475 5849104426 2924552213 8773656640 4386828320 2193414160 1096707080 548353540 274176770 137088385 411265156 205632578 102816289 308448868 154224434 77112217 231336652 115668326 57834163 173502490 86751245 260253736 130126868 65063434 32531717 97595152 48797576 24398788 12199394 6099697 18299092 9149546 4574773 13724320 6862160 3431080 1715540 857770 428885 1286656 643328 321664 160832 80416 40208 20104 10052 5026 2513 7540 3770 1885 5656 2828 1414 707 2122 1061 3184 1592 796 398 199 598 299 898 449 1348 674 337 1012 506 253 760 380 190 95 286 143 430 215 646 323 970 485 1456 728 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
如果序列中的数字甚至大于 uint64_t，那么您可以使用 unsigned __int128，它在 CLang/GCC 编译器中可用（但在 MSVC 中不可用）。然后你会得到下面的代码。
您可能注意到我对 cout 使用了 128 位输出的特殊处理，因为 __int128 没有内置 cout。我还使用了最长的已知 60 位起始序列（取 from here），它从 60 位数字开始，它有 2283 个步骤并且有 128 位中间值，我用它来显示 128 -位计算和输出在行动。
#include <iostream>
#include <cstdint>
#include <iomanip>
using namespace std;
using uint128_t = unsigned __int128;
void fun(uint128_t n) {
uint64_t num_steps = 0;
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
uint64_t const mod = 10'000'000'000'000'000'000ULL;
if (n / mod == 0)
cout << " " << uint64_t(n);
else
cout << " " << uint64_t(n / mod) << setfill('0')
<< setw(19) << uint64_t(n % mod);
++num_steps;
}
//cout << endl << "Num steps: " << num_steps << endl;
}
int main() {
uint64_t n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
输出（部分，由于 Whosebug 限制）：
931386509544713451 2794159528634140354 1397079764317070177 4191239292951210532 2095619646475605266 1047809823237802633 3143429469713407900 1571714734856703950 785857367428351975 2357572102285055926 1178786051142527963 3536358153427583890 1768179076713791945 5304537230141375836 2652268615070687918 1326134307535343959 3978402922606031878 1989201461303015939 5967604383909047818 2983802191954523909 8951406575863571728 4475703287931785864 2237851643965892932 1118925821982946466 559462910991473233 1678388732974419700 839194366487209850 419597183243604925 1258791549730814776 629395774865407388 314697887432703694 157348943716351847 472046831149055542 236023415574527771 708070246723583314 354035123361791657 1062105370085374972 531052685042687486 265526342521343743 796579027564031230 398289513782015615 1194868541346046846 597434270673023423 1792302812019070270 896151406009535135 2688454218028605406 1344227109014302703 4032681327042908110 2016340663521454055 6049021990564362166 3024510995282181083 9073532985846543250 4536766492923271625 13610299478769814876 6805149739384907438 3402574869692453719 10207724609077361158 5103862304538680579 15311586913616041738 7655793456808020869 22967380370424062608 11483690185212031304 5741845092606015652 2870922546303007826 1435461273151503913 4306383819454511740 2153191909727255870 1076595954863627935 3229787864590883806 1614893932295441903 4844681796886325710 2422340898443162855 7267022695329488566 3633511347664744283 10900534042994232850 5450267021497116425 16350801064491349276 8175400532245674638 4087700266122837319 12263100798368511958 6131550399184255979 18394651197552767938 9197325598776383969 27591976796329151908 13795988398164575954 6897994199082287977 20693982597246863932 10346991298623431966 5173495649311715983 15520486947935147950 7760243473967573975 23280730421902721926 11640365210951360963 34921095632854082890 17460547816427041445 52381643449281124336 26190821724640562168 13095410862320281084 6547705431160140542 3273852715580070271 9821558146740210814 4910779073370105407 14732337220110316222 7366168610055158111 22098505830165474334 11049252915082737167 33147758745248211502 16573879372624105751 49721638117872317254 24860819058936158627 74582457176808475882 37291228588404237941 111873685765212713824 55936842882606356912 27968421441303178456 13984210720651589228 6992105360325794614 3496052680162897307 10488158040488691922 5244079020244345961 15732237060733037884 7866118530366518942 3933059265183259471 11799177795549778414 5899588897774889207 17698766693324667622 8849383346662333811 26548150039987001434 13274075019993500717 39822225059980502152 19911112529990251076 9955556264995125538 4977778132497562769 14933334397492688308 7466667198746344154 3733333599373172077 11200000798119516232 5600000399059758116 2800000199529879058 1400000099764939529 4200000299294818588 2100000149647409294 1050000074823704647 3150000224471113942 1575000112235556971 4725000336706670914 2362500168353335457 7087500505060006372 3543750252530003186 1771875126265001593 5315625378795004780 2657812689397502390 1328906344698751195 3986719034096253586 1993359517048126793 5980078551144380380 2990039275572190190 1495019637786095095 4485058913358285286 2242529456679142643 6727588370037427930 3363794185018713965 10091382555056141896 5045691277528070948 2522845638764035474 1261422819382017737 3784268458146053212 1892134229073026606 946067114536513303 2838201343609539910 1419100671804769955 4257302015414309866 2128651007707154933 6385953023121464800 3192976511560732400 1596488255780366200 798244127890183100 399122063945091550 199561031972545775 598683095917637326 299341547958818663 898024643876455990 449012321938227995 1347036965814683986 673518482907341993 2020555448722025980 1010277724361012990 505138862180506495 1515416586541519486 757708293270759743 2273124879812279230 1136562439906139615 3409687319718418846 1704843659859209423 5114530979577628270 2557265489788814135 7671796469366442406 3835898234683221203 11507694704049663610 5753847352024831805 17261542056074495416 8630771028037247708 4315385514018623854 2157692757009311927 6473078271027935782 3236539135513967891 9709617406541903674 4854808703270951837 14564426109812855512 7282213054906427756 3641106527453213878 1820553263726606939 5461659791179820818 2730829895589910409 8192489686769731228 4096244843384865614 2048122421692432807 6144367265077298422 3072183632538649211 9216550897615947634 4608275448807973817 13824826346423921452 6912413173211960726 3456206586605980363 10368619759817941090 5184309879908970545 15552929639726911636 7776464819863455818 3888232409931727909 11664697229795183728 5832348614897591864 2916174307448795932 1458087153724397966 729043576862198983 2187130730586596950 1093565365293298475 3280696095879895426 1640348047939947713 4921044143819843140 2460522071909921570 1230261035954960785 3690783107864882356 1845391553932441178 922695776966220589 2768087330898661768 1384043665449330884 692021832724665442 346010916362332721 1038032749086998164 519016374543499082 259508187271749541 778524561815248624 389262280907624312 194631140453812156 97315570226906078 48657785113453039 145973355340359118 72986677670179559 218960033010538678 109480016505269339 328440049515808018 164220024757904009 492660074273712028 246330037136856014 123165018568428007 369495055705284022 184747527852642011 554242583557926034 277121291778963017 831363875336889052 415681937668444526 207840968834222263 623522906502666790 311761453251333395 935284359754000186 467642179877000093 1402926539631000280 701463269815500140 350731634907750070 175365817453875035 526097452361625106 263048726180812553 789146178542437660 394573089271218830 197286544635609415 591859633906828246 295929816953414123 887789450860242370 443894725430121185 1331684176290363556 665842088145181778 332921044072590889 998763132217772668 499381566108886334 249690783054443167 749072349163329502 374536174581664751 1123608523744994254 561804261872497127 1685412785617491382 842706392808745691 2528119178426237074 1264059589213118537 3792178767639355612 1896089383819677806 948044691909838903 2844134075729516710 1422067037864758355 4266201113594275066 2133100556797137533 6399301670391412600 3199650835195706300 1599825417597853150 799912708798926575 2399738126396779726 1199869063198389863 3599607189595169590 1799803594797584795 5399410784392754386 2699705392196377193 8099116176589131580 4049558088294565790 2024779044147282895 6074337132441848686 3037168566220924343 9111505698662773030 4555752849331386515 13667258547994159546 6833629273997079773 20500887821991239320 10250443910995619660 5125221955497809830 2562610977748904915 7687832933246714746 3843916466623357373 11531749399870072120 5765874699935036060 2882937349967518030 1441468674983759015 4324406024951277046 2162203012475638523 6486609037426915570 3243304518713457785 9729913556140373356 4864956778070186678 2432478389035093339 7297435167105280018 3648717583552640009 10946152750657920028 5473076375328960014 2736538187664480007 8209614562993440022 4104807281496720011 12314421844490160034 6157210922245080017 18471632766735240052 9235816383367620026 4617908191683810013 13853724575051430040 6926862287525715020 3463431143762857510 1731715571881428755 5195146715644286266 2597573357822143133 7792720073466429400 3896360036733214700 1948180018366607350 974090009183303675 2922270027549911026 1461135013774955513 4383405041324866540 2191702520662433270 1095851260331216635 3287553780993649906 1643776890496824953 4931330671490474860 2465665335745237430 1232832667872618715 3698498003617856146 1849249001808928073 5547747005426784220 2773873502713392110 1386936751356696055 4160810254070088166 2080405127035044083 6241215381105132250 3120607690552566125 9361823071657698376 4680911535828849188 2340455767914424594 1170227883957212297 3510683651871636892 1755341825935818446 877670912967909223 2633012738903727670 1316506369451863835 3949519108355591506 1974759554177795753 5924278662533387260 2962139331266693630 1481069665633346815 4443208996900040446 2221604498450020223 6664813495350060670 3332406747675030335 9997220243025091006 4998610121512545503 14995830364537636510 7497915182268818255 22493745546806454766 11246872773403227383 33740618320209682150 16870309160104841075 50610927480314523226 25305463740157261613 75916391220471784840 37958195610235892420 18979097805117946210 9489548902558973105 28468646707676919316 14234323353838459658 7117161676919229829 21351485030757689488 10675742515378844744 5337871257689422372 2668935628844711186 1334467814422355593 4003403443267066780 2001701721633533390 1000850860816766695 3002552582450300086 1501276291225150043 4503828873675450130 2251914436837725065 6755743310513175196 3377871655256587598 1688935827628293799 5066807482884881398 2533403741442440699 7600211224327322098 3800105612163661049 11400316836490983148 5700158418245491574 2850079209122745787 8550237627368237362 4275118813684118681 12825356441052356044 6412678220526178022 3206339110263089011 9619017330789267034 4809508665394633517 14428525996183900552 7214262998091950276 3607131499045975138 1803565749522987569 5410697248568962708 2705348624284481354 1352674312142240677 4058022936426722032 2029011468213361016 1014505734106680508 507252867053340254 253626433526670127 760879300580010382 380439650290005191 1141318950870015574 570659475435007787 1711978426305023362 855989213152511681 2567967639457535044 1283983819728767522 641991909864383761 1925975729593151284 962987864796575642 481493932398287821 1444481797194863464 722240898597431732 361120449298715866 180560224649357933 541680673948073800 270840336974036900 135420168487018450 67710084243509225 203130252730527676 101565126365263838 50782563182631919 152347689547895758 76173844773947879 228521534321843638 114260767160921819 342782301482765458 171391150741382729 514173452224148188 257086726112074094 128543363056037047 385630089168111142 192815044584055571 578445133752166714 289222566876083357 867667700628250072 433833850314125036 216916925157062518 108458462578531259 325375387735593778 162687693867796889 488063081603390668 244031540801695334 122015770400847667 366047311202543002 183023655601271501 549070966803814504 274535483401907252 137267741700953626 68633870850476813 205901612551430440 102950806275715220 51475403137857610 25737701568928805 77213104706786416 38606552353393208 19303276176696604 9651638088348302 4825819044174151 14477457132522454 7238728566261227 21716185698783682 10858092849391841 32574278548175524 16287139274087762 8143569637043881 24430708911131644 12215354455565822 6107677227782911 18323031683348734 9161515841674367 27484547525023102 13742273762511551 41226821287534654 20613410643767327 61840231931301982 30920115965650991 92760347896952974 46380173948476487 139140521845429462 69570260922714731 208710782768144194 104355391384072097 313066174152216292 156533087076108146 78266543538054073 234799630614162220 117399815307081110 58699907653540555 176099722960621666 88049861480310833 264149584440932500 132074792220466250 66037396110233125 198112188330699376 99056094165349688 49528047082674844 24764023541337422 12382011770668711 37146035312006134 18573017656003067 55719052968009202 27859526484004601 83578579452013804 41789289726006902 20894644863003451 62683934589010354 31341967294505177 94025901883515532 47012950941757766 23506475470878883 70519426412636650 35259713206318325 105779139618954976 52889569809477488 26444784904738744 13222392452369372 6611196226184686 3305598113092343 9916794339277030 4958397169638515 .......... 112784912014 56392456007 169177368022 84588684011 253766052034 126883026017 380649078052 190324539026 95162269513 285486808540 142743404270 71371702135 214115106406 107057553203 321172659610 160586329805 481758989416 240879494708 120439747354 60219873677 180659621032 90329810516 45164905258 22582452629 67747357888 33873678944 16936839472 8468419736 4234209868 2117104934 1058552467 3175657402 1587828701 4763486104 2381743052 1190871526 595435763 1786307290 893153645 2679460936 1339730468 669865234 334932617 1004797852 502398926 251199463 753598390 376799195 1130397586 565198793 1695596380 847798190 423899095 1271697286 635848643 1907545930 953772965 2861318896 1430659448 715329724 357664862 178832431 536497294 268248647 804745942 402372971 1207118914 603559457 1810678372 905339186 452669593 1358008780 679004390 339502195 1018506586 509253293 1527759880 763879940 381939970 190969985 572909956 286454978 143227489 429682468 214841234 107420617 322261852 161130926 80565463 241696390 120848195 362544586 181272293 543816880 271908440 135954220 67977110 33988555 101965666 50982833 152948500 76474250 38237125 114711376 57355688 28677844 14338922 7169461 21508384 10754192 5377096 2688548 1344274 672137 2016412 1008206 504103 1512310 756155 2268466 1134233 3402700 1701350 850675 2552026 1276013 3828040 1914020 957010 478505 1435516 717758 358879 1076638 538319 1614958 807479 2422438 1211219 3633658 1816829 5450488 2725244 1362622 681311 2043934 1021967 3065902 1532951 4598854 2299427 6898282 3449141 10347424 5173712 2586856 1293428 646714 323357 970072 485036 242518 121259 363778 181889 545668 272834 136417 409252 204626 102313 306940 153470 76735 230206 115103 345310 172655 517966 258983 776950 388475 1165426 582713 1748140 874070 437035 1311106 655553 1966660 983330 491665 1474996 737498 368749 1106248 553124 276562 138281 414844 207422 103711 311134 155567 466702 233351 700054 350027 1050082 525041 1575124 787562 393781 1181344 590672 295336 147668 73834 36917 110752 55376 27688 13844 6922 3461 10384 5192 2596 1298 649 1948 974 487 1462 731 2194 1097 3292 1646 823 2470 1235 3706 1853 5560 2780 1390 695 2086 1043 3130 1565 4696 2348 1174 587 1762 881 2644 1322 661 1984 992 496 248 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Num steps: 2283
上面的 128 位代码甚至可以处理已知最长的序列（参见 here) with 2968 steps. But starting value can't be inputted through std::cin, one way is to put it as a constant like in this modified code，这导致输出（部分）：
7219136416377236271195 21657409249131708813586 10828704624565854406793 32486113873697563220380 16243056936848781610190 8121528468424390805095 24364585405273172415286 12182292702636586207643 36546878107909758622930 18273439053954879311465 54820317161864637934396 27410158580932318967198 13705079290466159483599 41115237871398478450798 20557618935699239225399 61672856807097717676198 30836428403548858838099 92509285210646576514298 46254642605323288257149 138763927815969864771448 69381963907984932385724 34690981953992466192862 17345490976996233096431 52036472930988699289294 26018236465494349644647 78054709396483048933942 39027354698241524466971 117082064094724573400914 58541032047362286700457 175623096142086860101372 87811548071043430050686 43905774035521715025343 131717322106565145076030 65858661053282572538015 197575983159847717614046 98787991579923858807023 296363974739771576421070 148181987369885788210535 444545962109657364631606 222272981054828682315803 666818943164486046947410 333409471582243023473705 1000228414746729070421116 500114207373364535210558 250057103686682267605279 750171311060046802815838 375085655530023401407919 1125256966590070204223758 562628483295035102111879 1687885449885105306335638 843942724942552653167819 2531828174827657959503458 1265914087413828979751729 3797742262241486939255188 1898871131120743469627594 949435565560371734813797 2848306696681115204441392 1424153348340557602220696 712076674170278801110348 356038337085139400555174 178019168542569700277587 534057505627709100832762 267028752813854550416381 801086258441563651249144 400543129220781825624572 200271564610390912812286 100135782305195456406143 300407346915586369218430 150203673457793184609215 450611020373379553827646 225305510186689776913823 675916530560069330741470 337958265280034665370735 1013874795840103996112206 506937397920051998056103 1520812193760155994168310 760406096880077997084155 2281218290640233991252466 1140609145320116995626233 3421827435960350986878700 1710913717980175493439350 855456858990087746719675 2566370576970263240159026 1283185288485131620079513 3849555865455394860238540 1924777932727697430119270 ............. 160113203 480339610 240169805 720509416 360254708 180127354 90063677 270191032 135095516 67547758 33773879 101321638 50660819 151982458 75991229 227973688 113986844 56993422 28496711 85490134 42745067 128235202 64117601 192352804 96176402 48088201 144264604 72132302 36066151 108198454 54099227 162297682 81148841 243446524 121723262 60861631 182584894 91292447 273877342 136938671 410816014 205408007 616224022 308112011 924336034 462168017 1386504052 693252026 346626013 1039878040 519939020 259969510 129984755 389954266 194977133 584931400 292465700 146232850 73116425 219349276 109674638 54837319 164511958 82255979 246767938 123383969 370151908 185075954 92537977 277613932 138806966 69403483 208210450 104105225 312315676 156157838 78078919 234236758 117118379 351355138 175677569 527032708 263516354 131758177 395274532 197637266 98818633 296455900 148227950 74113975 222341926 111170963 333512890 166756445 500269336 250134668 125067334 62533667 187601002 93800501 281401504 140700752 70350376 35175188 17587594 8793797 26381392 13190696 6595348 3297674 1648837 4946512 2473256 1236628 618314 309157 927472 463736 231868 115934 57967 173902 86951 260854 130427 391282 195641 586924 293462 146731 440194 220097 660292 330146 165073 495220 247610 123805 371416 185708 92854 46427 139282 69641 208924 104462 52231 156694 78347 235042 117521 352564 176282 88141 264424 132212 66106 33053 99160 49580 24790 12395 37186 18593 55780 27890 13945 41836 20918 10459 31378 15689 47068 23534 11767 35302 17651 52954 26477 79432 39716 19858 9929 29788 14894 7447 22342 11171 33514 16757 50272 25136 12568 6284 3142 1571 4714 2357 7072 3536 1768 884 442 221 664 332 166 83 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Num steps: 2968
我正在解决 Weird Algorithm 问题：
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows: 3→10→5→16→8→4→2→1
Your task is to simulate the execution of the algorithm for a given value of n.
Input
The only input line contains an integer n.
Output
Print a line that contains all values of n during the algorithm.
Constraints
1≤n≤10^6
问题已解决，但面临 OUTPUT LIMIT EXCEED 问题。搜索了很多但找不到任何方法来摆脱这个问题。
它工作正常，直到我输入 = 270271，它给出了意外的输出，包括负值。
#include <iostream>
using namespace std;
void fun(int n) {
if (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
cout << " " << n;
fun(n);
}
}
int main() {
int n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
尽量不要在这里使用递归，如果递归深度太多，它可能会导致二进制文件崩溃，而且 Collatz 序列有时可能会很长，请尝试使用 while 循环。溢出的堆栈可能会产生这种超出输出。
此外，在某些输入上，您可能会溢出 int。请改用 uint64_t。就像我下面的代码一样。
完整更正的程序：
#include <iostream>
#include <cstdint>
using namespace std;
void fun(uint64_t n) {
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
cout << " " << n;
}
}
int main() {
uint64_t n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
输入：
270271
输出：
270271 810814 405407 1216222 608111 1824334 912167 2736502 1368251 4104754 2052377 6157132 3078566 1539283 4617850 2308925 6926776 3463388 1731694 865847 2597542 1298771 3896314 1948157 5844472 2922236 1461118 730559 2191678 1095839 3287518 1643759 4931278 2465639 7396918 3698459 11095378 5547689 16643068 8321534 4160767 12482302 6241151 18723454 9361727 28085182 14042591 42127774 21063887 63191662 31595831 94787494 47393747 142181242 71090621 213271864 106635932 53317966 26658983 79976950 39988475 119965426 59982713 179948140 89974070 44987035 134961106 67480553 202441660 101220830 50610415 151831246 75915623 227746870 113873435 341620306 170810153 512430460 256215230 128107615 384322846 192161423 576484270 288242135 864726406 432363203 1297089610 648544805 1945634416 972817208 486408604 243204302 121602151 364806454 182403227 547209682 273604841 820814524 410407262 205203631 615610894 307805447 923416342 461708171 1385124514 692562257 2077686772 1038843386 519421693 1558265080 779132540 389566270 194783135 584349406 292174703 876524110 438262055 1314786166 657393083 1972179250 986089625 2958268876 1479134438 739567219 2218701658 1109350829 3328052488 1664026244 832013122 416006561 1248019684 624009842 312004921 936014764 468007382 234003691 702011074 351005537 1053016612 526508306 263254153 789762460 394881230 197440615 592321846 296160923 888482770 444241385 1332724156 666362078 333181039 999543118 499771559 1499314678 749657339 2248972018 1124486009 3373458028 1686729014 843364507 2530093522 1265046761 3795140284 1897570142 948785071 2846355214 1423177607 4269532822 2134766411 6404299234 3202149617 9606448852 4803224426 2401612213 7204836640 3602418320 1801209160 900604580 450302290 225151145 675453436 337726718 168863359 506590078 253295039 759885118 379942559 1139827678 569913839 1709741518 854870759 2564612278 1282306139 3846918418 1923459209 5770377628 2885188814 1442594407 4327783222 2163891611 6491674834 3245837417 9737512252 4868756126 2434378063 7303134190 3651567095 10954701286 5477350643 16432051930 8216025965 24648077896 12324038948 6162019474 3081009737 9243029212 4621514606 2310757303 6932271910 3466135955 10398407866 5199203933 15597611800 7798805900 3899402950 1949701475 5849104426 2924552213 8773656640 4386828320 2193414160 1096707080 548353540 274176770 137088385 411265156 205632578 102816289 308448868 154224434 77112217 231336652 115668326 57834163 173502490 86751245 260253736 130126868 65063434 32531717 97595152 48797576 24398788 12199394 6099697 18299092 9149546 4574773 13724320 6862160 3431080 1715540 857770 428885 1286656 643328 321664 160832 80416 40208 20104 10052 5026 2513 7540 3770 1885 5656 2828 1414 707 2122 1061 3184 1592 796 398 199 598 299 898 449 1348 674 337 1012 506 253 760 380 190 95 286 143 430 215 646 323 970 485 1456 728 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
如果序列中的数字甚至大于 uint64_t，那么您可以使用 unsigned __int128，它在 CLang/GCC 编译器中可用（但在 MSVC 中不可用）。然后你会得到下面的代码。
您可能注意到我对 cout 使用了 128 位输出的特殊处理，因为 __int128 没有内置 cout。我还使用了最长的已知 60 位起始序列（取 from here），它从 60 位数字开始，它有 2283 个步骤并且有 128 位中间值，我用它来显示 128 -位计算和输出在行动。
#include <iostream>
#include <cstdint>
#include <iomanip>
using namespace std;
using uint128_t = unsigned __int128;
void fun(uint128_t n) {
uint64_t num_steps = 0;
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
uint64_t const mod = 10'000'000'000'000'000'000ULL;
if (n / mod == 0)
cout << " " << uint64_t(n);
else
cout << " " << uint64_t(n / mod) << setfill('0')
<< setw(19) << uint64_t(n % mod);
++num_steps;
}
//cout << endl << "Num steps: " << num_steps << endl;
}
int main() {
uint64_t n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
输出（部分，由于 Whosebug 限制）：
931386509544713451 2794159528634140354 1397079764317070177 4191239292951210532 2095619646475605266 1047809823237802633 3143429469713407900 1571714734856703950 785857367428351975 2357572102285055926 1178786051142527963 3536358153427583890 1768179076713791945 5304537230141375836 2652268615070687918 1326134307535343959 3978402922606031878 1989201461303015939 5967604383909047818 2983802191954523909 8951406575863571728 4475703287931785864 2237851643965892932 1118925821982946466 559462910991473233 1678388732974419700 839194366487209850 419597183243604925 1258791549730814776 629395774865407388 314697887432703694 157348943716351847 472046831149055542 236023415574527771 708070246723583314 354035123361791657 1062105370085374972 531052685042687486 265526342521343743 796579027564031230 398289513782015615 1194868541346046846 597434270673023423 1792302812019070270 896151406009535135 2688454218028605406 1344227109014302703 4032681327042908110 2016340663521454055 6049021990564362166 3024510995282181083 9073532985846543250 4536766492923271625 13610299478769814876 6805149739384907438 3402574869692453719 10207724609077361158 5103862304538680579 15311586913616041738 7655793456808020869 22967380370424062608 11483690185212031304 5741845092606015652 2870922546303007826 1435461273151503913 4306383819454511740 2153191909727255870 1076595954863627935 3229787864590883806 1614893932295441903 4844681796886325710 2422340898443162855 7267022695329488566 3633511347664744283 10900534042994232850 5450267021497116425 16350801064491349276 8175400532245674638 4087700266122837319 12263100798368511958 6131550399184255979 18394651197552767938 9197325598776383969 27591976796329151908 13795988398164575954 6897994199082287977 20693982597246863932 10346991298623431966 5173495649311715983 15520486947935147950 7760243473967573975 23280730421902721926 11640365210951360963 34921095632854082890 17460547816427041445 52381643449281124336 26190821724640562168 13095410862320281084 6547705431160140542 3273852715580070271 9821558146740210814 4910779073370105407 14732337220110316222 7366168610055158111 22098505830165474334 11049252915082737167 33147758745248211502 16573879372624105751 49721638117872317254 24860819058936158627 74582457176808475882 37291228588404237941 111873685765212713824 55936842882606356912 27968421441303178456 13984210720651589228 6992105360325794614 3496052680162897307 10488158040488691922 5244079020244345961 15732237060733037884 7866118530366518942 3933059265183259471 11799177795549778414 5899588897774889207 17698766693324667622 8849383346662333811 26548150039987001434 13274075019993500717 39822225059980502152 19911112529990251076 9955556264995125538 4977778132497562769 14933334397492688308 7466667198746344154 3733333599373172077 11200000798119516232 5600000399059758116 2800000199529879058 1400000099764939529 4200000299294818588 2100000149647409294 1050000074823704647 3150000224471113942 1575000112235556971 4725000336706670914 2362500168353335457 7087500505060006372 3543750252530003186 1771875126265001593 5315625378795004780 2657812689397502390 1328906344698751195 3986719034096253586 1993359517048126793 5980078551144380380 2990039275572190190 1495019637786095095 4485058913358285286 2242529456679142643 6727588370037427930 3363794185018713965 10091382555056141896 5045691277528070948 2522845638764035474 1261422819382017737 3784268458146053212 1892134229073026606 946067114536513303 2838201343609539910 1419100671804769955 4257302015414309866 2128651007707154933 6385953023121464800 3192976511560732400 1596488255780366200 798244127890183100 399122063945091550 199561031972545775 598683095917637326 299341547958818663 898024643876455990 449012321938227995 1347036965814683986 673518482907341993 2020555448722025980 1010277724361012990 505138862180506495 1515416586541519486 757708293270759743 2273124879812279230 1136562439906139615 3409687319718418846 1704843659859209423 5114530979577628270 2557265489788814135 7671796469366442406 3835898234683221203 11507694704049663610 5753847352024831805 17261542056074495416 8630771028037247708 4315385514018623854 2157692757009311927 6473078271027935782 3236539135513967891 9709617406541903674 4854808703270951837 14564426109812855512 7282213054906427756 3641106527453213878 1820553263726606939 5461659791179820818 2730829895589910409 8192489686769731228 4096244843384865614 2048122421692432807 6144367265077298422 3072183632538649211 9216550897615947634 4608275448807973817 13824826346423921452 6912413173211960726 3456206586605980363 10368619759817941090 5184309879908970545 15552929639726911636 7776464819863455818 3888232409931727909 11664697229795183728 5832348614897591864 2916174307448795932 1458087153724397966 729043576862198983 2187130730586596950 1093565365293298475 3280696095879895426 1640348047939947713 4921044143819843140 2460522071909921570 1230261035954960785 3690783107864882356 1845391553932441178 922695776966220589 2768087330898661768 1384043665449330884 692021832724665442 346010916362332721 1038032749086998164 519016374543499082 259508187271749541 778524561815248624 389262280907624312 194631140453812156 97315570226906078 48657785113453039 145973355340359118 72986677670179559 218960033010538678 109480016505269339 328440049515808018 164220024757904009 492660074273712028 246330037136856014 123165018568428007 369495055705284022 184747527852642011 554242583557926034 277121291778963017 831363875336889052 415681937668444526 207840968834222263 623522906502666790 311761453251333395 935284359754000186 467642179877000093 1402926539631000280 701463269815500140 350731634907750070 175365817453875035 526097452361625106 263048726180812553 789146178542437660 394573089271218830 197286544635609415 591859633906828246 295929816953414123 887789450860242370 443894725430121185 1331684176290363556 665842088145181778 332921044072590889 998763132217772668 499381566108886334 249690783054443167 749072349163329502 374536174581664751 1123608523744994254 561804261872497127 1685412785617491382 842706392808745691 2528119178426237074 1264059589213118537 3792178767639355612 1896089383819677806 948044691909838903 2844134075729516710 1422067037864758355 4266201113594275066 2133100556797137533 6399301670391412600 3199650835195706300 1599825417597853150 799912708798926575 2399738126396779726 1199869063198389863 3599607189595169590 1799803594797584795 5399410784392754386 2699705392196377193 8099116176589131580 4049558088294565790 2024779044147282895 6074337132441848686 3037168566220924343 9111505698662773030 4555752849331386515 13667258547994159546 6833629273997079773 20500887821991239320 10250443910995619660 5125221955497809830 2562610977748904915 7687832933246714746 3843916466623357373 11531749399870072120 5765874699935036060 2882937349967518030 1441468674983759015 4324406024951277046 2162203012475638523 6486609037426915570 3243304518713457785 9729913556140373356 4864956778070186678 2432478389035093339 7297435167105280018 3648717583552640009 10946152750657920028 5473076375328960014 2736538187664480007 8209614562993440022 4104807281496720011 12314421844490160034 6157210922245080017 18471632766735240052 9235816383367620026 4617908191683810013 13853724575051430040 6926862287525715020 3463431143762857510 1731715571881428755 5195146715644286266 2597573357822143133 7792720073466429400 3896360036733214700 1948180018366607350 974090009183303675 2922270027549911026 1461135013774955513 4383405041324866540 2191702520662433270 1095851260331216635 3287553780993649906 1643776890496824953 4931330671490474860 2465665335745237430 1232832667872618715 3698498003617856146 1849249001808928073 5547747005426784220 2773873502713392110 1386936751356696055 4160810254070088166 2080405127035044083 6241215381105132250 3120607690552566125 9361823071657698376 4680911535828849188 2340455767914424594 1170227883957212297 3510683651871636892 1755341825935818446 877670912967909223 2633012738903727670 1316506369451863835 3949519108355591506 1974759554177795753 5924278662533387260 2962139331266693630 1481069665633346815 4443208996900040446 2221604498450020223 6664813495350060670 3332406747675030335 9997220243025091006 4998610121512545503 14995830364537636510 7497915182268818255 22493745546806454766 11246872773403227383 33740618320209682150 16870309160104841075 50610927480314523226 25305463740157261613 75916391220471784840 37958195610235892420 18979097805117946210 9489548902558973105 28468646707676919316 14234323353838459658 7117161676919229829 21351485030757689488 10675742515378844744 5337871257689422372 2668935628844711186 1334467814422355593 4003403443267066780 2001701721633533390 1000850860816766695 3002552582450300086 1501276291225150043 4503828873675450130 2251914436837725065 6755743310513175196 3377871655256587598 1688935827628293799 5066807482884881398 2533403741442440699 7600211224327322098 3800105612163661049 11400316836490983148 5700158418245491574 2850079209122745787 8550237627368237362 4275118813684118681 12825356441052356044 6412678220526178022 3206339110263089011 9619017330789267034 4809508665394633517 14428525996183900552 7214262998091950276 3607131499045975138 1803565749522987569 5410697248568962708 2705348624284481354 1352674312142240677 4058022936426722032 2029011468213361016 1014505734106680508 507252867053340254 253626433526670127 760879300580010382 380439650290005191 1141318950870015574 570659475435007787 1711978426305023362 855989213152511681 2567967639457535044 1283983819728767522 641991909864383761 1925975729593151284 962987864796575642 481493932398287821 1444481797194863464 722240898597431732 361120449298715866 180560224649357933 541680673948073800 270840336974036900 135420168487018450 67710084243509225 203130252730527676 101565126365263838 50782563182631919 152347689547895758 76173844773947879 228521534321843638 114260767160921819 342782301482765458 171391150741382729 514173452224148188 257086726112074094 128543363056037047 385630089168111142 192815044584055571 578445133752166714 289222566876083357 867667700628250072 433833850314125036 216916925157062518 108458462578531259 325375387735593778 162687693867796889 488063081603390668 244031540801695334 122015770400847667 366047311202543002 183023655601271501 549070966803814504 274535483401907252 137267741700953626 68633870850476813 205901612551430440 102950806275715220 51475403137857610 25737701568928805 77213104706786416 38606552353393208 19303276176696604 9651638088348302 4825819044174151 14477457132522454 7238728566261227 21716185698783682 10858092849391841 32574278548175524 16287139274087762 8143569637043881 24430708911131644 12215354455565822 6107677227782911 18323031683348734 9161515841674367 27484547525023102 13742273762511551 41226821287534654 20613410643767327 61840231931301982 30920115965650991 92760347896952974 46380173948476487 139140521845429462 69570260922714731 208710782768144194 104355391384072097 313066174152216292 156533087076108146 78266543538054073 234799630614162220 117399815307081110 58699907653540555 176099722960621666 88049861480310833 264149584440932500 132074792220466250 66037396110233125 198112188330699376 99056094165349688 49528047082674844 24764023541337422 12382011770668711 37146035312006134 18573017656003067 55719052968009202 27859526484004601 83578579452013804 41789289726006902 20894644863003451 62683934589010354 31341967294505177 94025901883515532 47012950941757766 23506475470878883 70519426412636650 35259713206318325 105779139618954976 52889569809477488 26444784904738744 13222392452369372 6611196226184686 3305598113092343 9916794339277030 4958397169638515 .......... 112784912014 56392456007 169177368022 84588684011 253766052034 126883026017 380649078052 190324539026 95162269513 285486808540 142743404270 71371702135 214115106406 107057553203 321172659610 160586329805 481758989416 240879494708 120439747354 60219873677 180659621032 90329810516 45164905258 22582452629 67747357888 33873678944 16936839472 8468419736 4234209868 2117104934 1058552467 3175657402 1587828701 4763486104 2381743052 1190871526 595435763 1786307290 893153645 2679460936 1339730468 669865234 334932617 1004797852 502398926 251199463 753598390 376799195 1130397586 565198793 1695596380 847798190 423899095 1271697286 635848643 1907545930 953772965 2861318896 1430659448 715329724 357664862 178832431 536497294 268248647 804745942 402372971 1207118914 603559457 1810678372 905339186 452669593 1358008780 679004390 339502195 1018506586 509253293 1527759880 763879940 381939970 190969985 572909956 286454978 143227489 429682468 214841234 107420617 322261852 161130926 80565463 241696390 120848195 362544586 181272293 543816880 271908440 135954220 67977110 33988555 101965666 50982833 152948500 76474250 38237125 114711376 57355688 28677844 14338922 7169461 21508384 10754192 5377096 2688548 1344274 672137 2016412 1008206 504103 1512310 756155 2268466 1134233 3402700 1701350 850675 2552026 1276013 3828040 1914020 957010 478505 1435516 717758 358879 1076638 538319 1614958 807479 2422438 1211219 3633658 1816829 5450488 2725244 1362622 681311 2043934 1021967 3065902 1532951 4598854 2299427 6898282 3449141 10347424 5173712 2586856 1293428 646714 323357 970072 485036 242518 121259 363778 181889 545668 272834 136417 409252 204626 102313 306940 153470 76735 230206 115103 345310 172655 517966 258983 776950 388475 1165426 582713 1748140 874070 437035 1311106 655553 1966660 983330 491665 1474996 737498 368749 1106248 553124 276562 138281 414844 207422 103711 311134 155567 466702 233351 700054 350027 1050082 525041 1575124 787562 393781 1181344 590672 295336 147668 73834 36917 110752 55376 27688 13844 6922 3461 10384 5192 2596 1298 649 1948 974 487 1462 731 2194 1097 3292 1646 823 2470 1235 3706 1853 5560 2780 1390 695 2086 1043 3130 1565 4696 2348 1174 587 1762 881 2644 1322 661 1984 992 496 248 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Num steps: 2283
上面的 128 位代码甚至可以处理已知最长的序列（参见 here) with 2968 steps. But starting value can't be inputted through std::cin, one way is to put it as a constant like in this modified code，这导致输出（部分）：
7219136416377236271195 21657409249131708813586 10828704624565854406793 32486113873697563220380 16243056936848781610190 8121528468424390805095 24364585405273172415286 12182292702636586207643 36546878107909758622930 18273439053954879311465 54820317161864637934396 27410158580932318967198 13705079290466159483599 41115237871398478450798 20557618935699239225399 61672856807097717676198 30836428403548858838099 92509285210646576514298 46254642605323288257149 138763927815969864771448 69381963907984932385724 34690981953992466192862 17345490976996233096431 52036472930988699289294 26018236465494349644647 78054709396483048933942 39027354698241524466971 117082064094724573400914 58541032047362286700457 175623096142086860101372 87811548071043430050686 43905774035521715025343 131717322106565145076030 65858661053282572538015 197575983159847717614046 98787991579923858807023 296363974739771576421070 148181987369885788210535 444545962109657364631606 222272981054828682315803 666818943164486046947410 333409471582243023473705 1000228414746729070421116 500114207373364535210558 250057103686682267605279 750171311060046802815838 375085655530023401407919 1125256966590070204223758 562628483295035102111879 1687885449885105306335638 843942724942552653167819 2531828174827657959503458 1265914087413828979751729 3797742262241486939255188 1898871131120743469627594 949435565560371734813797 2848306696681115204441392 1424153348340557602220696 712076674170278801110348 356038337085139400555174 178019168542569700277587 534057505627709100832762 267028752813854550416381 801086258441563651249144 400543129220781825624572 200271564610390912812286 100135782305195456406143 300407346915586369218430 150203673457793184609215 450611020373379553827646 225305510186689776913823 675916530560069330741470 337958265280034665370735 1013874795840103996112206 506937397920051998056103 1520812193760155994168310 760406096880077997084155 2281218290640233991252466 1140609145320116995626233 3421827435960350986878700 1710913717980175493439350 855456858990087746719675 2566370576970263240159026 1283185288485131620079513 3849555865455394860238540 1924777932727697430119270 ............. 160113203 480339610 240169805 720509416 360254708 180127354 90063677 270191032 135095516 67547758 33773879 101321638 50660819 151982458 75991229 227973688 113986844 56993422 28496711 85490134 42745067 128235202 64117601 192352804 96176402 48088201 144264604 72132302 36066151 108198454 54099227 162297682 81148841 243446524 121723262 60861631 182584894 91292447 273877342 136938671 410816014 205408007 616224022 308112011 924336034 462168017 1386504052 693252026 346626013 1039878040 519939020 259969510 129984755 389954266 194977133 584931400 292465700 146232850 73116425 219349276 109674638 54837319 164511958 82255979 246767938 123383969 370151908 185075954 92537977 277613932 138806966 69403483 208210450 104105225 312315676 156157838 78078919 234236758 117118379 351355138 175677569 527032708 263516354 131758177 395274532 197637266 98818633 296455900 148227950 74113975 222341926 111170963 333512890 166756445 500269336 250134668 125067334 62533667 187601002 93800501 281401504 140700752 70350376 35175188 17587594 8793797 26381392 13190696 6595348 3297674 1648837 4946512 2473256 1236628 618314 309157 927472 463736 231868 115934 57967 173902 86951 260854 130427 391282 195641 586924 293462 146731 440194 220097 660292 330146 165073 495220 247610 123805 371416 185708 92854 46427 139282 69641 208924 104462 52231 156694 78347 235042 117521 352564 176282 88141 264424 132212 66106 33053 99160 49580 24790 12395 37186 18593 55780 27890 13945 41836 20918 10459 31378 15689 47068 23534 11767 35302 17651 52954 26477 79432 39716 19858 9929 29788 14894 7447 22342 11171 33514 16757 50272 25136 12568 6284 3142 1571 4714 2357 7072 3536 1768 884 442 221 664 332 166 83 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Num steps: 2968