/* Kevin Ryde, December 2024 Usage: ./a.out [-v] [start|resume] This is some C code for GNU C in a 64 bit build, using its __int128 feature, to find terms of one of A378845(n) = smallest starting x taking n steps to reach the minimum of its eventual cycle under the 3x-1 iteration A378846(n) = likewise but count x/2 halving steps only A378847(n) = likewise but count 3x-1 triple steps only The 3x-1 iteration is x -> 3x-1 if x odd, x -> x/2 if x even. The different counts of steps are "all", "half" or "triple". The method is to examine the trajectory of successive odd x, with early stop if it drops by so much that previously found terms show x cannot be >= n steps, for the next unknown n. Even x terms (in "all" and "half") are derived from odd terms. This is a low memory approach since the table of previously found terms is only a few thousand entries (of 64 bit numbers). Configuration ------------- The count choice, and hence which sequence, is a compile-time choice in the "Configuration" section below. #define COUNT_TYPE COUNT_TYPE_ALL for all steps #define COUNT_TYPE COUNT_TYPE_HALF for half steps x/2 #define COUNT_TYPE COUNT_TYPE_TRIPLE for triple steps 3x-1 MAXN there too is the maximum n which can be stored. This sizes the arrays of results and can be increased as desired. Having these as compile-time constants gives the compiler a little more opportunity to optimise. There don't seem to be relationships between the count types which would easily let them run together. Output ------ Output is b-file style, with for instance "3 7" meaning a(3) = 7, ./a.out => # A378845 = all 0 1 1 2 2 4 3 7 Optional parameter "-v" prints with a little more verbosity. GNU C __int128 -------------- traj_t is a typedef to GNU C "unsigned __int128" and holds x values during a trajectory. __int128 is only available in a 64 bit build. 128 bits is used since 64 bits soon overflows. For instance near n=858 of "all" after a few minutes (on a 3 GHz CPU at the time of writing). Save and Resume --------------- Search state is saved in a file on program interrupt (SIGINT, SIGTERM, SIGHUP), and periodically on a timer. saved-state.txt Command line option "resume" re-reads this file and resumes from that point in the search. This is good for a long run which might have to stop and start sometimes. The file format is like COUNT_TYPE = 0 n = 606 x = 47154153 0 1 1 2 2 4 3 7 ... end of terms COUNT_TYPE is the compiled configuration option. Resume checks it matches, ie. save was from a run of the same configuration. n = next target n sought (the smallest unknown). x = next candidate x to consider. Then b-file style "n a(n)" of terms found so far and 0 at unknown terms. The found terms include some which are ahead of the next unknown. They're output after earlier terms are found. Statistics at the end show processing speeds. Only odd x are checked so x per second is that many odd x. "ops" are (3x-1)/2^e operations described below. "all" and "half" have a simple upper bound a(n) <= 2*a(n-1) (see "Odd x" below) and the rates become a worst case time estimate for the next term, or some new term. Cycle Minima ------------ The known cycles are 1,2 5,14,7,20,10 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34 Their minima are 1,5,17 and is_minimum() has them hard-coded. Infinite Loop ------------- If other cycles exist or any trajectory diverges then an overflow of num_steps is detected in num_steps_of_x(). That might be after several minutes for a 32 bit "int", or nearly infinite time for a 64 bit "int". An infinite loop would be no updates to saved-state.txt, and no response to the normal SIGINT, SIGTERM, SIGHUP. This is unfriendly but a new cycle or any diverging start would be an excellent and unexpected advance in knowledge about 3x-1. Trajectory Stopping ------------------- Early trajectory stopping uses smallest[n] = a(n), or 0 if unknown yet. bounds[i] = smallest starting x taking >= i steps = Min smallest[s] for s >= i and smallest[s] != 0 bounds[] is used for i ranging 0 <= i < n, where n = first n with smallest[n] = 0, so always has one or more smallest[s] != 0 in "Min" A trajectory starting from x is only wanted if num_steps(x) >= n where n = first n with smallest[n] = 0, If some "num_steps_so_far" reaches "x_so_far" then remaining = max(0, n - num_steps_so_far) stop if x_so_far < bounds[remaining] since nothing < bounds[remaining] takes >= remaining If the desired n steps is exceeded, so num_steps_so_far > n, then the max() above holds remaining=0 and that means don't stop, since bounds[0] = 1. num_steps_of_x() runs in successive "operations" of (3x-1)/2^e operation, with x odd x = OddPart( (3x-1)/2 ) if x is a cycle minimum stop, have num_steps if x < bounds[remaining] stop, cannot reach num_steps >= n OddPart strips all factors of 2, so all x -> x/2 steps. num_steps counts 3x-1 and/or /2 steps according to the configured COUNT_TYPE. saved-state.txt includes statistics on mean number of operations in the candidate x's tried, to get a sense of how soon the bounds scheme eliminates x which is not a new term. traj_triple_over_2() has a fairly usual method of adding a right shift "x>>1", (3x-1)/2 = x + floor(x/2) for x odd This combination step is the only place x increases and traj_t overflow detection is there. Odd x ----- search_from() examines the trajectory of odd x. For "triple", all a(n) are odd since halvings don't count and any 2*x is the same number of triples as x. For "all" or "half", x = 2*a(n-1) takes n steps, since its first step is to x/2 = a(n-1). This is an upper bound a(n) <= 2*a(n-1) Even terms only ever occur as a(n) = 2*a(n-1) since any smaller even a(n) would imply a smaller a(n-1). Even terms are sought by next_double = Min 2*a(n-1) for a(n-1) known and a(n) unknown (see find_next_double()) When x = next_double + 1, which is tested as x > next_double, there's some a(n) = 2*a(n-1) now known. set_doubles() fills accordingly. Terms are not in ascending order, in general, so it's possible this a(n) is not the next unknown, but somewhere later. Things Not Done --------------- A branch-free (3x-1)/2 or x/2, according as x odd or even, measured slower than traj_step_reduced_odd() with its table lookup for /2's. Would that be partly a function of how often look at is_minimum() and bounds_is_bad() though? COUNT_TYPE_TRIPLE can have some upper bounds on unknown terms by exploring a few predecessors back from known a(n-c), for a few small c. That'd be a worst-case for progress information. */ /* ------------------------------------------------------------------------ */ /* Configuration */ /* COUNT_TYPE_ALL to count all steps 3x-1 and x/2 COUNT_TYPE_HALF to count only steps x/2 COUNT_TYPE_TRIPLE to count only steps 3x-1 */ #define COUNT_TYPE COUNT_TYPE_ALL /* MAXN sizes some arrays. Increase if encounter more than MAXN steps. */ #define MAXN 5000 /* Set WANT_ASSERT to 1 to enable self-checks (slower). Set WANT_DEBUG to 1 for some rough development prints. */ #define WANT_ASSERT 0 #define WANT_DEBUG 0 /* ------------------------------------------------------------------------ */ #if ! WANT_ASSERT #define NDEBUG #endif #include #include #include #include #include #include #include #include #include #include #include #include /* ------------------------------------------------------------------------ */ /* Generic */ #if WANT_DEBUG #define DEBUG(expr) do { expr; } while (0) #else #define DEBUG(expr) do { } while (0) #endif #ifdef __GNUC__ #define LIKELY(cond) __builtin_expect((cond) != 0, 1) #define UNLIKELY(cond) __builtin_expect((cond) != 0, 0) #define ATTRIBUTE_PRINTF __attribute__ ((format (printf,1,2))) #else #define LIKELY(cond) (cond) #define UNLIKELY(cond) (cond) #define ATTRIBUTE_PRINTF #endif /* GNU C type __int128 available on a 64 bit target. */ typedef unsigned __int128 uint128_t; #define numberof(array) (sizeof(array)/sizeof((array)[0])) #define MIN(x,y) ((x)<=(y) ? (x) : (y)) static noreturn ATTRIBUTE_PRINTF void error (const char *format, ...) { va_list ap; va_start (ap, format); vfprintf (stderr, format, ap); va_end (ap); exit(1); } static FILE * fopen_or_die (const char *filename, const char *mode) { FILE *fp = fopen(filename,mode); if (fp==NULL) error("Cannot %s %s\n", mode[0] == 'r' ? "open" : "create", filename); return (fp); } static void ferror_die (FILE *fp, const char *filename, const char *action) { if (ferror(fp)) error("Error %s %s: %s\n", action, filename, strerror(errno)); } static void fclose_or_die (FILE *fp, const char *filename) { if (fclose(fp) != 0) error("Error closing %s\n", filename); } static void rename_or_die (const char *old_filename, const char *new_filename) { if (rename(old_filename, new_filename) != 0) error("Error renaming %s to %s: %s\n", old_filename, new_filename, strerror(errno)); } static void sigaction_or_die (int signum, const struct sigaction *act, struct sigaction *oldact) { if (sigaction (signum, act, oldact) != 0) error("Cannot sigaction signum=%d: %s\n", signum, strerror(errno)); } static void setitimer_or_die (int which, const struct itimerval *new_value, struct itimerval *old_value) { if (setitimer(which, new_value, old_value) != 0) error("Cannot setitimer %d: %s\n", which, strerror(errno)); } /* CPU time consumed by this process so far, in seconds */ static double cputime (void) { struct timespec t; if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t) != 0) error("Cannot clock_gettime() CPUTIME: %s\n", strerror(errno)); return (t.tv_sec + t.tv_nsec/1e9); } /* ------------------------------------------------------------------------ */ #define COUNT_TYPE_ALL 0 #define COUNT_TYPE_HALF 1 #define COUNT_TYPE_TRIPLE 2 /* whether count half step and triple step (possibly both) */ #define COUNT_HALF (COUNT_TYPE != COUNT_TYPE_TRIPLE) #define COUNT_TRIPLE (COUNT_TYPE != COUNT_TYPE_HALF) static const struct { const char *count_type_name; const char *A_number; const uint64_t want[2000]; } info[] = { { "all", "A378845", { 1, 2, 4, 7, 3, 6, 11, 19, 21, 13, 26, 9, 18, 35, 37, 73, 25, 49, 98, 33, 66, 131, 45, 90, 175, 127, 117, 85, 149, 57, 113, 199, 209, 133, 265, 89, 177, 65, 119, 237, 87, 159, 165, 329, 231, 225, 439, 309, 293, 585, 377, 391, 273, 261, 521, 1042, 671, 695, 485, 465, 927, 597, 1111, 1233, 741, 825, 529, 1047, 353, 705, 1253, 471, 941, 977, 1945, 1241, 1297, 837, 865, 1729, 577, 1153, 385, 769, 257, 513, 1025, 343, 685, 229, 457, 153, 305, 610, 1219, 407, 813, 1621, 543, 1081, 2161, 721, 1441, 481, 961, 321, 641, 1282, 2563, 855, 1709, 3418, 1141, 2279, 761, 1521, 3039, 1015, 2029, 677, 1353, 2706, 903, 1805, 3610, 1209, 2407, 4813, 1605, 3209, 6401, 2149, 4279, 1433, 2853, 5689, 1911, 3793, 7585, 2529, 5057, 3041, 3397, 6743, 2265, 4529, 8991, 5143, 6033, 3429, 4097, 7993, 4807, 5329, 3205, 3553, 2137, 2369, 1425, 2849, 3159, 6317, 3799, 7225, 2533, 4817, 1689, 3377, 6423, 7511, 4503, 5029, 10015, 3353, 6677, 13329, 4471, 8903, 2981, 5961, 11833, 3975, 7889, 5505, 11009, 10519, 21037, 7013, 14025, 28001, 9351, 18689, 13049, 21273, 24919, 14993, 16613, 11621, 19989, 22151, 15495, 14777, 29535, 18969, 19703, 13777, 13153, 9185, 8769, 17537, 12247, 21009, 8165, 16293, 15589, 10887, 10393, 20785, 6929, 13857, 27714, 9239, 18477, 36881, 12319, 24637, 8213, 16425, 32850, 10951, 21901, 7301, 14601, 29202, 9735, 19469, 38929, 77703, 25953, 51905, 101561, 34613, 69207, 23105, 46149, 28161, 30807, 21473, 42945, 41857, 28631, 27905, 55809, 38175, 37207, 72929, 24805, 49609, 16537, 33073, 11025, 22049, 44098, 86437, 29399, 57625, 114577, 38417, 76385, 26133, 51223, 101847, 34149, 68297, 136594, 81925, 91063, 54617, 60709, 121417, 40473, 80945, 48549, 55063, 34689, 36709, 73417, 24473, 48945, 97889, 32631, 65261, 41113, 76673, 27409, 54817, 18273, 36545, 38673, 77345, 48727, 97453, 32485, 64969, 21657, 43313, 80825, 91669, 57751, 61113, 38501, 68369, 136737, 47897, 91159, 108645, 60773, 121545, 141921, 81031, 162061, 54021, 108041, 216082, 81121, 144055, 54081, 96037, 192073, 64025, 128049, 256098, 85367, 170733, 64097, 113823, 227645, 85463, 163173, 303525, 113951, 227897, 241729, 151935, 161153, 322305, 202577, 214871, 419045, 239825, 286495, 180069, 190997, 372485, 271193, 254663, 496647, 361591, 339551, 241061, 426817, 432913, 284545, 288609, 189697, 379393, 126465, 252929, 505858, 190469, 337239, 598885, 224833, 399257, 149889, 299769, 532343, 618119, 399703, 709791, 266469, 532865, 992607, 355281, 710487, 734945, 1461009, 944357, 979927, 1912165, 653285, 1274777, 783425, 868249, 561433, 578833, 374289, 385889, 771777, 1543553, 514519, 1029037, 343013, 686025, 501081, 457351, 914701, 304901, 609801, 1219602, 406535, 813069, 1626138, 542047, 1084093, 361365, 722729, 1441345, 924181, 960897, 616121, 1232241, 1284853, 821495, 856569, 1708261, 1095327, 1138841, 2277681, 4555362, 1518455, 3036909, 1015193, 2024607, 1424913, 1353591, 2707181, 1744869, 3489737, 3599301, 2334039, 2426469, 4710753, 2894913, 3199377, 2067993, 3860569, 4270689, 2573713, 2867973, 1715809, 3431617, 1143873, 2287745, 2535121, 4962769, 1690081, 3308513, 1126721, 2253441, 4411351, 1502295, 2940901, 5881801, 1960601, 3921201, 7842402, 2614135, 5228269, 1742757, 3485513, 2302617, 4297881, 4647351, 9294701, 3165329, 6196469, 3808609, 4220437, 2539073, 2813625, 5507969, 3385431, 3850593, 2263905, 4527809, 4895973, 9791945, 6037079, 6669333, 4871321, 4497297, 8703953, 5349817, 10231249, 3566545, 6820833, 2377697, 4755393, 5291521, 3170263, 3527681, 2113509, 4227017, 4703575, 9302849, 3135717, 6271433, 3757349, 7514697, 8361911, 5009799, 10019597, 4029413, 8058825, 7487041, 5372551, 4991361, 3581701, 7163401, 2387801, 4775601, 4512741, 3183735, 6156673, 5910625, 4104449, 3940417, 7880833, 2626945, 5253889, 1751297, 3502593, 6960401, 2335063, 4670125, 1556709, 3113417, 6226834, 12374047, 4151223, 8249365, 16498729, 5499577, 10999153, 3666385, 7332769, 2444257, 4888513, 1629505, 3259009, 1086337, 2172673, 724225, 1448449, 482817, 965633, 1931266, 3862531, 1287511, 2575021, 858341, 1716681, 3433362, 1144455, 2288909, 4577818, 9155631, 3051879, 6103757, 12207509, 4069173, 8138343, 16276677, 32192353, 10851125, 21461569, 7234085, 14307713, 28615425, 9645445, 19076951, 6430297, 12860593, 4286865, 8573729, 17147449, 34294897, 11431633, 22863265, 7621089, 15242177, 5080729, 10161457, 3387153, 6774305, 13548609, 27097205, 9032407, 18064813, 6021605, 12043209, 24086369, 8028807, 16057601, 32115159, 63518117, 21410135, 42521361, 14273425, 28546847, 9515617, 19031233, 6343745, 12687489, 25370113, 8458327, 16913409, 5638885, 11277769, 3759257, 7518513, 15037025, 5012343, 10024685, 20049367, 40098725, 13366245, 26732489, 53454725, 17821663, 35643319, 11881109, 23762213, 16635905, 15841479, 31682951, 22181207, 44362413, 42235833, 29574943, 28162629, 19716629, 39433257, 37550165, 26288839, 52577677, 17525893, 35051785, 11683929, 23367857, 46735714, 76314711, 31157143, 62314285, 20771429, 41542857, 39813505, 27695239, 26542337, 18463493, 36926985, 35389783, 24617991, 23593189, 47186377, 15728793, 31457585, 62915170, 43765317, 41943447, 83886893, 52974745, 55924597, 35316497, 37283065, 74566129, 24855377, 49710753, 99421506, 33140503, 66281005, 22093669, 44187337, 14729113, 29458225, 9819409, 19638817, 6546273, 13092545, 26185090, 52370179, 17456727, 34913453, 69826906, 23275637, 46551271, 93102541, 31034181, 62068361, 123343233, 41378911, 82757815, 27585941, 55171877, 110343753, 36781255, 73562503, 24520837, 49041669, 16347225, 32694449, 65388898, 129919863, 43592599, 87185189, 29061733, 58123465, 19374489, 38748977, 77497954, 153979097, 51665303, 103330605, 205305463, 68887071, 136870309, 88151425, 91246873, 58767617, 60831249, 121662497, 40821969, 81643937, 162216663, 324433325, 108858583, 216288885, 72572389, 145144777, 48381593, 96763185, 192256785, 64508791, 129017581, 43005861, 86011721, 172023441, 341789841, 114682295, 228698977, 455796901, 152465985, 303864601, 194609473, 202576401, 129739649, 257500757, 271839505, 172986199, 181226337, 115324133, 120817561, 240425113, 80545041, 160283409, 102510341, 201833793, 214786775, 136680455, 273360909, 286382337, 182240607, 364481213, 379402497, 743379807, 254562105, 505784217, 323983301, 337947409, 675432965, 225298273, 450288645, 150198849, 300397697, 191990105, 201135489, 400530263, 255986807, 480299479, 534040351, 320199653, 356026901, 227543825, 426932871, 474702535, 303391767, 316468357, 632936713, 210978905, 421957809, 842165729, 281305207, 562610413, 187536805, 375073609, 125024537, 250049073, 499756417, 166699383, 333170945, 666341889, 1330604121, 444227927, 888455853, 533537793, 592303903, 1184607805, 394869269, 789738537, 1566269441, 526492359, 1052984717, 2088359255, 1467380889, 1396203685, 979848549, 930802457, 1861604913, 624417625, 1241069943, 416278417, 832556833, 277518945, 555037889, 354735681, 709471361, 740050519, 1480101037, 493367013, 986734025, 1969375201, 1183574801, 1312916801, 2607504805, 1578099735, 1738336537, 1121139929, 1158891025, 2317782049, 772594017, 1545188033, 951069281, 1039522263, 2060250711, 1268092375, 2536184749, 845394917, 1690789833, 3317872465, 1127193223, 2211914977, 751462149, 1474609985, 2949219969, 3285403705, 1966146647, 2190269137, 1335932709, 1460179425, 2920358841, 1747685909, 3331034433, 1375193441, 2330247879, 2595874533, 1833591255, 3318149399, 6213994343, 2224245401, 4153275905, 4616525313, 2949466133, 3138195457, 2149452441, 2092130305, 4091528513, 1394753537, 2789507073, 1641155969, 1859671383, 3719342765, 2188207959, 4375467621, 1553628225, 2965390983, 3255269273, 6423768485, 3886694233, 4297186273, 2591129489, 2864790849, 5729581697, 3454839319, 3858096917, 2303226213, 4606452425, 5092961509, 3124033297, 3395307673, 2082688865, 2263538449, 4527076897, 1509025633, 3018051265, 1006017089, 2012034177, 4024068354, 1341356119, 2682712237, 894237413, 1788474825, 3576949650, 1192316551, 2384633101, 794877701, 1589755401, 3168653465, 1059836935, 2119673869, 706557957, 1413115913, 2826231826, 5652463651, 1884154551, 3768309101, 7536618197, 2512206069, 5024412135, 10014509717, 3353817431, 6699216181, 13352679623, 4466144121, 8932288241, 5479084377, 10772032645, 11909717653, 7181355097, 7939811769, 4787570065, 9115776857, 3191713377, 6383426753, 7057610465, 14115220929, 8511235671, 9410147287, 6048348625, 6273431525, 4032232417, 8064464833, 2688154945, 5376309889, 1792103297, 3584206593, 7168413186, 2389471063, 4778942125, 1592980709, 3185961417, 6371922834, 2123974279, 4247948557, 1415982853, 2831965705, 943988569, 1887977137, 629325713, 1258651425, 2361565569, 839100951, 1678201901, 3356403802, 6297508183, 2237602535, 4198338789, 8396677577, 2983470047, 5601544545, 11195570103, 3977960063, 7955920125, 14927426805, 5303946751, 9958301413, 3535964501, 6638867609, 7347891729, 4714619335, 8851823479, 3143079557, 5901215653, 11802431305, 3934143769, 7868287537, 2622762513, 5245525025, 9976999169, 19953998337, 6994033367, 13302665559, 26605331117, 9325377823, 18650755645, 6216918549, 12433837097, 24867674193, 8829940921, 16578449463, 5886627281, 11695484089, 22089763713, 7796989393, 15593978785, 5197992929, 10395985857, 19648532697, 6930657239, 13861314477, 4651162297, 9240876319, 3100774865, 6160584213, 12321168425, 4134366487, 8268732973, 2756244325, 5512488649, 1837496217, 3674992433, 7349984866, 13799792513, 4899989911, 9799979821, 3266659941, 6533319881, 12980325585, 25960651169, 8711093175, 17422186349, 18189182885, 11614790901, 23076134373, 24252243847, 48504487693, 16168162565, 32336325129, 20648517157, 21557550087, 13765678105, 27531356209, 9177118737, 18354237473, 36708474946, 39055653975, 24472316631, 45947426821, 91833178113, 30631617881, 61222118745, 69432273733, 40842157175, 46288182489, 92050494105, 54456209567, 61402906777, 38672302801, 40935271185, 25781535201, 51563070401, 96746064225, 34375380289, 64540692821, 22916920193, 45833840357, 48017120409, 30555893591, 61111787009, 117296678145, 40741191429, 81482382679, 86250447929, 54321588453, 101990230625, 36214392405, 72428784809, 135986974167, 150124119297, 96571712805, 181194274837, 64381142053, 120796183225, 42920761369, 80530788817, 28613840913, 53687192545, 107374385089, 35791461697, 71582923393, 23860974465, 47721948929, 95443897858, 190887795715, 63629265239, 127258530477, 242104608913, 84839020319, 161403072609, 188262253461, 113118693759, 226237387417, 75463431681, 150824924945, 286938795749, 100549950009, 201099899921, 223798849369, 134157211877, 149199232913, 103399267393, 170037804889, 68932844929, 113358536593, 45955229953, 75572357729, 30636819969, 52964582721, 100763143639, 118394760663, 67175429093, 134350858185, 268701716370, 89567238791, 179134477581, 72620610297, 119422985055, 238845970109, 285409395353, 177230454103, 318461293479, 118153636069, 236307272137, 78769090713, 157538181425, 165331042689, 105738264919, 210050908567, 70492176613, 140033939045, 46994784409, 93989568817, 31329856273, 62659712545, 20886570849, 41773141697, 83546283394, 149174373841, 55697522263, 99449582561, 37131681509, 74263363017, 132599443415, 49508908679, 99017817357, 176799257887, 66011878239, 117866171925, 138325630309, 276651260617, 92217086873, 184434173745, 366476207569, 122956115831, 244317471713, 170197491553, 163941487775, 113464994369, 195855154149, 217170727169, 139086755793, 276298267671, 100857772773, 201715545545, 193040646373, 386081292745, 128693764249, 257387528497, 85795842833, 171591685665, 343183371330, 114394457111, 228788914221, 457577828442, 152525942815, 305051885629, 101683961877, 203367923753, 406735847506, 136463818305, 271157231671, 155039648921, 180771487781, 361542975561, 206719531895, 241028650375, 167927067489, 160685766917, 321371533833, 642743067666, 214247689223, 428495378445, 298537008869, 285663585631, 571327171261, 190442390421, 380884780841, 127790534929, 255581069857, 85193689953, 170387379905, 338564249637 } }, { "half", "A378846", { 1, 2, 4, 3, 6, 11, 13, 9, 18, 35, 25, 47, 33, 63, 45, 81, 95, 117, 127, 85, 57, 113, 133, 89, 97, 65, 129, 87, 173, 225, 231, 293, 309, 377, 261, 273, 545, 671, 465, 485, 597, 647, 741, 529, 353, 705, 471, 941, 1029, 1241, 837, 577, 385, 257, 513, 343, 229, 153, 305, 610, 407, 813, 543, 1081, 721, 481, 321, 641, 1282, 855, 1709, 1141, 761, 1521, 1015, 677, 1353, 903, 1805, 1209, 2407, 1605, 3209, 2149, 1433, 2625, 1911, 3793, 2529, 4561, 3041, 2265, 3857, 7713, 5143, 3429, 4193, 4807, 3205, 2137, 1425, 2849, 5698, 3799, 2533, 1689, 3377, 6423, 4503, 3353, 6005, 4471, 2981, 5337, 3975, 7889, 8257, 5505, 7013, 12645, 9351, 16865, 19573, 13049, 14993, 17399, 11621, 14777, 15495, 18969, 13153, 8769, 9185, 18329, 12247, 8165, 10393, 6929, 13857, 9239, 18477, 12319, 8213, 16425, 10951, 7301, 14601, 9735, 19469, 20229, 25953, 46745, 34613, 23105, 42241, 28161, 32209, 21473, 27905, 28631, 37207, 24805, 16537, 11025, 22049, 38913, 29399, 57625, 38417, 26133, 51223, 34149, 68297, 74393, 81925, 54617, 40473, 72823, 48549, 34689, 24473, 48945, 32631, 61669, 41113, 27409, 18273, 36545, 73090, 48727, 32485, 21657, 43313, 80825, 57751, 38501, 68369, 47897, 91159, 60773, 121545, 81031, 54021, 108041, 81121, 54081, 96037, 64025, 128049, 85367, 64097, 113823, 85463, 163173, 113951, 227897, 151935, 290085, 202577, 219489, 239825, 180069, 319767, 254663, 271193, 339551, 361591, 241061, 284545, 189697, 126465, 252929, 285703, 190469, 224833, 149889, 299769, 532343, 399703, 266469, 532865, 355281, 710487, 769881, 944357, 653285, 1175137, 783425, 561433, 374289, 748497, 514519, 343013, 686025, 457351, 304901, 609801, 406535, 779777, 542047, 361365, 722729, 1386271, 924181, 616121, 1232241, 821495, 1642989, 1095327, 2190653, 1518455, 1015193, 1962977, 1353591, 1424913, 1744869, 3489737, 2334039, 4342369, 2894913, 2067993, 3860569, 2573713, 1715809, 1143873, 2287745, 1690081, 1126721, 2253441, 1502295, 2719745, 1960601, 3431577, 2614135, 1742757, 3297345, 2302617, 4297881, 3165329, 5712913, 3808609, 2539073, 5078145, 3385431, 2263905, 4527809, 9027815, 6037079, 4497297, 4871321, 5349817, 3566545, 2377697, 4755393, 3170263, 2113509, 4227017, 3135717, 5636023, 3757349, 4533089, 5009799, 6044119, 4029413, 4991361, 5372551, 3581701, 2387801, 4775601, 3183735, 3940417, 2626945, 1751297, 3502593, 2335063, 1556709, 3113417, 5960769, 4151223, 8249365, 5499577, 3666385, 2444257, 1629505, 1086337, 724225, 482817, 965633, 1931266, 1287511, 858341, 1716681, 1144455, 2288909, 4577818, 3051879, 6103757, 4069173, 8138343, 15009119, 10851125, 7234085, 14307713, 9645445, 6430297, 4286865, 8573729, 17147449, 11431633, 7621089, 5080729, 3387153, 6774305, 13548609, 9032407, 6021605, 12043209, 8028807, 16057601, 32115159, 21410135, 14273425, 9515617, 6343745, 12687489, 8458327, 5638885, 3759257, 7518513, 5012343, 10024685, 20049367, 13366245, 26732489, 17821663, 11881109, 23762213, 15841479, 16635905, 33271809, 22181207, 28162629, 29574943, 19716629, 39433257, 26288839, 17525893, 11683929, 23367857, 46735714, 31157143, 20771429, 26542337, 27695239, 18463493, 23593189, 15728793, 31457585, 56370689, 41943447, 43765317, 52974745, 35316497, 24855377, 47088663, 33140503, 22093669, 14729113, 9819409, 6546273, 13092545, 26185090, 17456727, 34913453, 23275637, 44434649, 31034181, 59246199, 41378911, 27585941, 55171877, 36781255, 24520837, 16347225, 32694449, 65388898, 43592599, 29061733, 19374489, 38748977, 74380407, 51665303, 98632289, 68887071, 131509719, 88151425, 58767617, 40821969, 78356823, 154955607, 108858583, 72572389, 48381593, 96763185, 64508791, 43005861, 86011721, 162949697, 114682295, 217266263, 152465985, 273077157, 194609473, 129739649, 257500757, 172986199, 115324133, 80545041, 153765511, 102510341, 201833793, 136680455, 273360909, 182240607, 364481213, 254562105, 485974951, 323983301, 225298273, 150198849, 287985153, 191990105, 360224609, 255986807, 480299479, 320199653, 227543825, 426932871, 303391767, 210978905, 421957809, 281305207, 187536805, 125024537, 250049073, 166699383, 321377625, 639245205, 444227927, 800306689, 533537793, 394869269, 789738537, 526492359, 1052984717, 1102329617, 1396203685, 930802457, 624417625, 416278417, 277518945, 532103521, 354735681, 709471361, 493367013, 945961815, 1774876497, 1183574801, 2367149601, 1578099735, 1121139929, 772594017, 1426603921, 951069281, 1902138561, 1268092375, 845394917, 1690789833, 1127193223, 751462149, 1474609985, 2949219969, 1966146647, 1335932709, 2621528863, 1747685909, 2062790161, 1375193441, 2750386881, 1833591255, 2224245401, 4153275905, 2949466133, 2092130305, 1394753537, 2461200537, 1641155969, 3282311937, 2188207959, 1553628225, 2965390983, 5541996441, 3886694233, 2591129489, 5182258977, 3454839319, 2303226213, 4606452425, 3124033297, 2082688865, 1509025633, 1006017089, 2012034177, 1341356119, 894237413, 1788474825, 1192316551, 794877701, 1589755401, 1059836935, 706557957, 1413115913, 2682474777, 1884154551, 3408338457, 2512206069, 5024412135, 3353817431, 6163969925, 4466144121, 8218626565, 5479084377, 10772032645, 7181355097, 4787570065, 3191713377, 6383426753, 12154369143, 8511235671, 6048348625, 4032232417, 2688154945, 1792103297, 3584206593, 2389471063, 1592980709, 3185961417, 2123974279, 1415982853, 943988569, 629325713, 1258651425, 839100951, 1678201901, 3356403802, 2237602535, 4198338789, 2983470047, 5601544545, 3977960063, 7955920125, 5303946751, 3535964501, 6638867609, 4714619335, 3143079557, 5901215653, 3934143769, 2622762513, 5245525025, 9976999169, 6994033367, 13302665559, 9325377823, 6216918549, 12433837097, 8829940921, 5886627281, 11695484089, 7796989393, 5197992929, 10395985857, 6930657239, 4651162297, 3100774865, 6160584213, 4134366487, 2756244325, 1837496217, 3674992433, 7349984866, 4899989911, 3266659941, 6533319881, 12980325585, 8711093175, 17422186349, 11614790901, 23076134373, 16168162565, 30972775733, 20648517157, 13765678105, 9177118737, 18354237473, 36708474946, 24472316631, 45947426821, 30631617881, 61222118745, 40842157175, 47217742737, 54456209567, 38672302801, 25781535201, 51563070401, 34375380289, 22916920193, 45833840357, 30555893591, 33401392737, 40741191429, 81482382679, 54321588453, 36214392405, 72428784809, 78607478231, 96571712805, 64381142053, 42920761369, 28613840913, 53687192545, 35791461697, 23860974465, 47721948929, 95443897858, 63629265239, 127258530477, 84839020319, 161403072609, 113118693759, 75463431681, 150824924945, 100549950009, 116596324961, 134157211877, 155098901089, 103399267393, 68932844929, 45955229953, 30636819969, 61273639937, 67175429093, 81698186583, 89567238791, 108930915445, 72620610297, 145241220593, 177230454103, 118153636069, 78769090713, 157538181425, 105738264919, 70492176613, 46994784409, 31329856273, 20886570849, 41773141697, 83546283394, 55697522263, 37131681509, 74263363017, 49508908679, 99017817357, 66011878239, 117866171925, 92217086873, 174844997511, 122956115831, 220337048417, 163941487775, 170197491553, 113464994369, 139086755793, 151286659159, 100857772773, 128693764249, 85795842833, 171591685665, 114394457111, 228788914221, 152525942815, 101683961877, 203367923753, 136463818305, 232559473381, 155039648921, 310079297841, 206719531895, 160685766917, 167927067489, 214247689223, 428495378445, 285663585631, 190442390421, 127790534929, 85193689953, 170387379905, 338564249637, 227183173207, 151455448805, 302910897609, 201940598407, 134627065605, 269254131209, 538508262418, 359005508279, 643328934805, 428885956537, 285923971025, 571847942049, 381231961367, 283658673209, 294483082305, 338872854549, 252141042853, 168094028569, 112062685713, 224125371425, 401627086873, 267751391249, 535502782497, 357001854999, 714003709997, 531260139673, 354173426449, 236115617633, 472231235265, 314820823511, 564151079505, 419761098015 }, }, { "triple","A378847", { 1, 3, 15, 13, 9, 37, 25, 33, 45, 57, 145, 97, 65, 87, 159, 165, 225, 273, 391, 261, 647, 465, 741, 529, 353, 471, 921, 837, 865, 577, 385, 257, 343, 229, 153, 407, 543, 721, 481, 321, 855, 1141, 761, 1015, 677, 903, 1209, 1605, 2149, 1433, 1911, 2529, 3397, 2265, 3429, 4097, 3205, 2137, 1425, 3159, 2533, 1689, 4503, 5029, 3353, 4471, 2981, 3975, 10519, 7013, 9351, 11621, 15495, 20665, 13777, 9185, 12247, 8165, 10887, 15589, 10393, 6929, 9239, 12319, 8213, 10951, 7301, 9735, 25953, 32209, 21473, 28631, 38175, 27905, 37207, 24805, 16537, 11025, 29399, 38417, 26133, 34149, 54617, 60709, 40473, 34689, 36709, 24473, 32631, 27409, 18273, 38673, 32485, 21657, 57751, 38501, 47897, 60773, 81031, 54021, 81121, 54081, 64025, 85367, 64097, 85463, 113951, 151935, 161153, 214871, 180069, 190997, 241061, 321415, 214277, 189697, 126465, 253959, 224833, 149889, 399703, 266469, 355281, 734945, 924345, 653285, 561433, 374289, 385889, 501081, 343013, 457351, 304901, 406535, 542047, 361365, 616121, 821495, 856569, 1138841, 1424913, 1015193, 1353591, 2334039, 2426469, 2067993, 2573713, 1715809, 1143873, 2535121, 1690081, 1126721, 1502295, 1960601, 2614135, 1742757, 4647351, 3165329, 2539073, 2813625, 2263905, 4871321, 6495095, 4497297, 3566545, 2377697, 3170263, 2113509, 4533089, 3135717, 4029413, 5372551, 3581701, 2387801, 3183735, 4104449, 5472599, 3940417, 2626945, 1751297, 2335063, 1556709, 4151223, 5300241, 3666385, 2444257, 1629505, 1086337, 724225, 482817, 1287511, 858341, 1144455, 3051879, 4069173, 10851125, 7234085, 9645445, 6430297, 4286865, 11431633, 7621089, 5080729, 3387153, 9032407, 6021605, 8028807, 21410135, 14273425, 9515617, 6343745, 8458327, 5638885, 3759257, 5012343, 13366245, 16635905, 11881109, 15841479, 19716629, 26288839, 17525893, 11683929, 31157143, 20771429, 27695239, 18463493, 24617991, 35389783, 23593189, 15728793, 41943447, 35316497, 37283065, 24855377, 33140503, 22093669, 14729113, 9819409, 6546273, 17456727, 23275637, 31034181, 41378911, 27585941, 36781255, 24520837, 16347225, 43592599, 29061733, 19374489, 51665303, 68887071, 58767617, 60831249, 40821969, 108858583, 72572389, 48381593, 64508791, 43005861, 114682295, 152465985, 129739649, 172986199, 115324133, 120817561, 80545041, 136680455, 182240607, 379402497, 254562105, 337947409, 225298273, 150198849, 201135489, 320199653, 227543825, 303391767, 316468357, 210978905, 281305207, 187536805, 125024537, 166699383, 444227927, 592303903, 394869269, 526492359, 1396203685, 930802457, 624417625, 416278417, 277518945, 740050519, 493367013, 1312916801, 1121139929, 1158891025, 772594017, 1039522263, 845394917, 1127193223, 751462149, 1966146647, 1335932709, 1375193441, 1833591255, 2595874533, 2224245401, 2149452441, 3138195457, 2092130305, 1394753537, 1859671383, 1553628225, 3255269273, 2591129489, 2864790849, 2303226213, 3124033297, 2082688865, 2263538449, 1509025633, 1006017089, 1341356119, 894237413, 1192316551, 794877701, 1059836935, 706557957, 1884154551, 2512206069, 3353817431, 4466144121, 7181355097, 4787570065, 3191713377, 7057610465, 6048348625, 4032232417, 2688154945, 1792103297, 2389471063, 1592980709, 2123974279, 1415982853, 943988569, 629325713, 839100951, 2237602535, 2983470047, 3977960063, 5303946751, 3535964501, 4714619335, 3143079557, 3934143769, 2622762513, 6994033367, 9325377823, 6216918549, 8829940921, 5886627281, 7796989393, 5197992929, 6930657239, 4651162297, 3100774865, 4134366487, 2756244325, 1837496217, 4899989911, 3266659941, 8711093175, 11614790901, 24252243847, 16168162565, 13765678105, 9177118737, 24472316631, 30631617881, 40842157175, 46288182489, 38672302801, 25781535201, 34375380289, 22916920193, 30555893591, 40741191429, 54321588453, 36214392405, 96571712805, 64381142053, 42920761369, 28613840913, 35791461697, 23860974465, 63629265239, 84839020319, 113118693759, 75463431681, 100549950009, 103399267393, 68932844929, 45955229953, 30636819969, 52964582721, 67175429093, 72620610297, 119422985055, 129103307193, 118153636069, 78769090713, 105738264919, 70492176613, 46994784409, 31329856273, 20886570849, 55697522263, 37131681509, 49508908679, 66011878239, 138325630309, 92217086873, 113464994369, 151286659159, 100857772773, 268954060727, 193040646373, 128693764249, 85795842833, 114394457111, 152525942815, 101683961877, 136463818305, 167927067489, 241028650375, 160685766917, 214247689223, 264746835009, 190442390421, 127790534929, 85193689953, 227183173207, 151455448805, 201940598407, 134627065605, 359005508279, 285923971025, 294483082305, 425488009813, 283658673209, 378211564279, 252141042853, 168094028569, 112062685713, 298833828567, 398445104757, 531260139673, 354173426449, 236115617633, 314820823511, 419761098015 } }, }; /* ------------------------------------------------------------------------ */ static int option_verbose = 0; static int option_maxn = INT_MAX; /* traj_t holds x values within a trajectory (but just uint64_t for start of trajectory) */ typedef uint128_t traj_t; #define TRAJ_BITS ((int) (CHAR_BIT*sizeof(traj_t))) /* Return a string which is the decimal digits of x. Explicit conversion since __int128 not in printf() etc. */ char * traj_decimal_str (traj_t x) { /* 3 decimals per byte is at least enough, plus \0 terminator */ static char buf[3*sizeof(traj_t) + 1]; int i = sizeof(buf)-1; do { if (--i < 0) error("traj_decimal_str() buffer too small\n"); int digit = x % 10; x /= 10; buf[i] = digit + '0'; } while (x); return (buf + i); } /* for(n=0,2^12-1, if(n%32==0,print1("\n ")); print1(if(n==0,0,valuation(n,2)),",")); */ #define COUNT_LOW_ZEROS_TABLE_MASK \ (numberof(count_low_zeros_table) - 1) #define COUNT_LOW_ZEROS_TABLE_BITS 12 static const uint8_t count_low_zeros_table[] = { 0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 9,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 10,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 9,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 11,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 9,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 10,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 9,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, 5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0, }; static inline uint64_t traj_high (traj_t x) { return (TRAJ_BITS > 64 ? x >> 64 : 0); } static inline uint64_t traj_low (traj_t x) { return (x); } /* Change x at *xp to (3*x-1)/2. Must have x odd. This is a 3x-1 step and following x/2 step (since 3x-1 even). Return the number of steps to count under the configured COUNT_TYPE. */ static inline int traj_triple_over_2 (traj_t *xp) { /* (3*x-1)/2 = x + (x-1)/2 = x + floor(x/2) since x odd. Overflow detected by sum dropping below addend, which GCC recognises as the carry flag. */ traj_t x = *xp; assert (x & 1); traj_t add = x >> 1; x += add; (*xp) = x; if (UNLIKELY (x < add)) error("traj_t overflow\n"); return (COUNT_TRIPLE + COUNT_HALF); } /* Change x at *xp to remove all factors of 2, which is all the successive halving steps x/2 which can be applied (0 or more). Return the number of steps to count under the configured COUNT_TYPE. */ static inline int traj_halvings (traj_t *xp) { traj_t x = *xp; assert (x != 0); int num_steps = 0; size_t low; while (UNLIKELY( (low = x&COUNT_LOW_ZEROS_TABLE_MASK) == 0 )) { x >>= COUNT_LOW_ZEROS_TABLE_BITS; if (COUNT_HALF) num_steps += COUNT_LOW_ZEROS_TABLE_BITS; } assert (0 <= low && low < numberof(count_low_zeros_table)); int shift = count_low_zeros_table[low]; /* "& 0x3F" tells GCC that the shift is <= 63 bits so don't need to allow for a shift of 64 or more bits moving the high 64 bits down to become the low 64. shift is actually <= COUNT_LOW_ZEROS_TABLE_BITS - 1. */ x >>= (shift & 0x3F); if (COUNT_HALF) num_steps += shift; *xp = x; return (num_steps); } /* Change x at *xp to (3x-1)/2^e for the maximum e which leaves an integer, ie. all halving steps. x must be odd and the new x is odd too. Return the number of steps to count under the configured COUNT_TYPE. */ static inline int traj_step_reduced_odd (traj_t *xp) { int num_steps = traj_triple_over_2(xp); return (num_steps + traj_halvings(xp)); } /* ------------------------------------------------------------------------ */ /* smallest[steps] = a(steps) = smallest starting x which takes "steps" many steps to reach 1 or 5 or 17. Or 0 if steps not seen yet. */ static uint64_t smallest[MAXN+1]; static uint64_t bounds[MAXN+1]; /* bounds[i] = Min smallest[i..end] with unknown entries (smallest[t]=0) reckoned as UINT64_MAX. */ static void calculate_bounds (void) { uint64_t b = UINT64_MAX; int i; for (i = numberof(smallest)-1; i >= 0; i--) { if (smallest[i]) b = MIN(b,smallest[i]); assert (0 <= i && i < numberof(bounds)); bounds[i] = b; } assert(bounds[0] == 1); } /* Set smallest[n] = x and update bounds[]. */ static void set_smallest (int n, uint64_t x) { DEBUG(printf("set_smallest() n=%d is x=%"PRIu64"\n",n,x)); if (n >= numberof(smallest)) error ("oops, n=%d exceeds MAXN, increase MAXN and re-compile\n", n); if (smallest[n] != 0) error ("oops, n=%d smallest[] already set\n", n); smallest[n] = x; calculate_bounds(); } /* find_next_double() returns next_double = Min 2*smallest[i-1] where smallest[i-1]!=0 (known) and smallest[i]==0 (unknown). When the search x reaches next_double, have determined a new term somewhere smallest[i] = 2*smallest[i-1]. For COUNT_TYPE_TRIPLE, return a dummy UINT64_MAX which has the effect of no next_double check in search_from(). */ static uint64_t find_next_double (int *wherep) { uint64_t next_double = UINT64_MAX; int where = 0; if (COUNT_TYPE != COUNT_TYPE_TRIPLE) { size_t n; for (n=1; n < numberof(smallest); n++) { if (smallest[n]==0 && smallest[n-1] != 0) { uint64_t b = 2*smallest[n-1]; if (b < next_double) { where = n; next_double = b; } } } } if (wherep) *wherep = where; return (next_double); } /* For COUNT_TYPE_ALL and COUNT_TYPE_HALF, fill any smallest[n] = 2*smallest[n-1] now known to be smallest because have searched to x >= 2*smallest[n-1]. For COUNT_TYPE_TRIPLE, there is no such evens setting, so do nothing. In all cases return new find_next_double(). */ static uint64_t set_doubles (uint64_t x) { if (COUNT_TYPE != COUNT_TYPE_TRIPLE) { /* double filled immediately after x passes */ assert (x%2 == 1); assert (x == find_next_double(NULL) + 1); size_t n; for (n=1; n < numberof(smallest); n++) { if (smallest[n] == 0 && smallest[n-1] != 0) { uint64_t b = 2*smallest[n-1]; if (b <= x) set_smallest(n,b); } } } return (find_next_double(NULL)); } /* Return the smallest n for which smallest[n] = 0, meaning that a(n) is unknown. */ static int smallest_unknown_n (void) { size_t n; for (n=0; n < numberof(smallest); n++) if (smallest[n]==0) break; return(n); } /* ------------------------------------------------------------------------ */ /* Save State */ static const char saved_state_filename[] = "saved-state.txt"; static const char temp_filename[] = "saved-state.txt.tempfile"; static uint64_t last_num_x = 0; static uint64_t last_num_ops = 0; static double last_cputime; /* Taken any whole hours away from *seconds and return them. *seconds < 0 is taken to mean no such time and no change. */ static int seconds_take_hours (double *seconds) { if (*seconds < 0) { return (-1); } else { int hours = *seconds / 3600; *seconds -= hours * 3600.0; return (hours); } } static void save (int n, uint64_t x) { double end_time = cputime(); /* Write first to temp_filename and then rename, so atomic replacement. */ FILE *fp = fopen_or_die (temp_filename, "w"); fprintf(fp, "COUNT_TYPE = %d\n", COUNT_TYPE); fprintf(fp, "n = %d\n", n); fprintf(fp, "x = %"PRIu64"\n", x); int i, max_i; for (max_i = numberof(smallest)-1; max_i >= 1; max_i--) if (smallest[max_i]) break; for (i = 0; i <= max_i; i++) fprintf(fp, "%d %"PRIu64"\n", i, smallest[i]); fprintf(fp, "end of terms\n"); /* extra info */ fprintf(fp, "\n-------------\n"); fprintf(fp, "running %s = %s\n", info[COUNT_TYPE].A_number, info[COUNT_TYPE].count_type_name); double elapsed_time = end_time - last_cputime; fprintf(fp, "last chunk %.1f seconds CPU time\n", elapsed_time); fprintf(fp, "tried %"PRIu64" x by %"PRIu64" ops, mean %.2lf per x\n", last_num_x, last_num_ops, (last_num_x > 0 ? (double) last_num_ops / last_num_x : -1.0)); double x_per_second = (elapsed_time >= 1 ? last_num_x / elapsed_time : -1.0); double steps_per_second = (elapsed_time >= 1 ? last_num_ops / elapsed_time : -1.0); fprintf(fp, "%.2lf million x/second, %.2lf million ops/second\n", x_per_second/1e6, steps_per_second/1e6); if (COUNT_TYPE != COUNT_TYPE_TRIPLE) { { uint64_t next_x = (n > 0 ? 2*smallest[n-1] : 1); int64_t next_num_x = next_x - x; double next_seconds = (x_per_second >= 1 ? next_num_x / (2*x_per_second) : -1.0); int next_hours = seconds_take_hours(&next_seconds); fprintf(fp, "next n=%d by double would be x=%"PRIu64"\n", n, next_x); fprintf(fp, " is %"PRId64" away, estimate %d hours %.0lf seconds\n", next_num_x, next_hours, next_seconds); } int next_n; uint64_t next_x = find_next_double(&next_n); if (next_n != n) { int64_t next_num_x = next_x - x; double next_seconds = (x_per_second >= 1 ? next_num_x / (2*x_per_second) : -1.0); int next_hours = seconds_take_hours(&next_seconds); fprintf(fp, "or next x=%"PRIu64" to know n=%d\n", next_x, next_n); fprintf(fp, " is %"PRId64" away, estimate %d hours %.0lf seconds\n", next_num_x, next_hours, next_seconds); } } /* -------- */ ferror_die (fp, temp_filename, "writing"); fclose_or_die (fp, temp_filename); rename_or_die (temp_filename, saved_state_filename); if (option_verbose >= 2) printf("save to %s x=%"PRIu64"\n", saved_state_filename, x); last_cputime = cputime(); last_num_x = 0; last_num_ops = 0; } static volatile sig_atomic_t flag_interrupt = 0; static volatile sig_atomic_t flag_terminate = 0; void sig_handler_save_state (int signum) { if (option_verbose >= 2) printf("signal %d received for save state\n", signum); flag_interrupt = 1; } void sig_handler_terminate (int signum) { if (option_verbose) printf("signal %d received for terminate\n", signum); flag_interrupt = 1; flag_terminate = 1; } /* Initialise handlers for saving on SIGINT, SIGHUP, SIGTERM, and on a timer. */ void init_save () { struct sigaction s; s.sa_handler = sig_handler_terminate; sigfillset(&s.sa_mask); s.sa_flags = SA_RESTART; sigaction_or_die(SIGINT, &s, NULL); sigaction_or_die(SIGHUP, &s, NULL); sigaction_or_die(SIGTERM, &s, NULL); s.sa_handler = sig_handler_save_state; sigaction_or_die(SIGALRM, &s, NULL); struct itimerval t; t.it_interval.tv_sec = 5*60; /* 5 minutes */ t.it_interval.tv_usec = 0; t.it_value = t.it_interval; setitimer_or_die(ITIMER_REAL, &t, NULL); last_cputime = cputime(); } /* ------------------------------------------------------------------------ */ /* Sample Data */ /* info[COUNT_TYPE].want[] is padded out with 0s to a fixed length. Return the number of entries before those final 0s, for the configured COUNT_TYPE. */ static size_t want_data_length (void) { const uint64_t *want = info[COUNT_TYPE].want; size_t len = 0; while (want[len] != 0) len++; return (len); } /* Check a(n)=x against info[COUNT_TYPE].want[n] */ static void check_smallest (int n, uint64_t x, const char *where) { if (n < 0) error("oops, check_smallest() is for n>=0\n"); const char *A_number = info[COUNT_TYPE].A_number; const uint64_t *want = info[COUNT_TYPE].want; size_t len = want_data_length(); if (n >= len) { if (option_verbose) printf(" (beyond %s sample data)\n", A_number); return; } if (x == want[n]) { if (option_verbose) printf(" (%sgood vs %s sample data)\n", where, A_number); return; } error("oops %s %sn=%d, got %"PRIu64" want %"PRIu64"\n", A_number, where, n, x, want[n]); } /* ------------------------------------------------------------------------ */ /* Search */ /* Return 1 if x is a 5 bit number, so <= 31. */ static inline int traj_is_le_5_bits (traj_t x) { return ((traj_high(x) | (traj_low(x) & (UINT64_MAX<<5))) == 0); } /* Return 1 if x = 1 or 5 or 17. */ static inline int is_minimum (traj_t x) { uint64_t flags = (((uint64_t)1 << 1) + ((uint64_t)1 << 5) + ((uint64_t)1 << 17)); return (UNLIKELY(traj_is_le_5_bits(x)) && UNLIKELY(flags & ((uint64_t)1 << x))); } /* num_steps_of_x_whole() returns the number of steps for x to reach the minimum of its cycle, with steps counted according to the configured COUNT_TYPE. This goes through the whole trajectory without the possible early stop of num_steps_of_x(). */ static int num_steps_of_x_whole (traj_t x) { assert (x >= 1); int num_steps = traj_halvings(&x); while (! is_minimum(x)) { num_steps += traj_step_reduced_odd (&x); if (UNLIKELY (num_steps < 0)) error ("num_steps overflow at x=%s\n", traj_decimal_str(x)); } return (num_steps); } /* bounds_is_bad() takes n = number of steps of next unknown, and x has taken num_steps so far. Return 1 if bounds[] shows that x is too small to reach n steps, and so its starting point cannot be a new smallest[] entry. */ static inline int bounds_is_bad (int n, traj_t x, int num_steps) { int remaining = n - num_steps; if (UNLIKELY(remaining < 0)) remaining = 0; assert (0 <= remaining && remaining < n); assert (bounds[remaining] != UINT64_MAX); return (x < bounds[remaining]); } /* num_steps_of_x() returns the number of steps for x to reach the minimum of its cycle, with steps counted according to the configured COUNT_TYPE. Or may return -1 if detect this x wont be >= n steps. x must be odd. */ static inline int num_steps_of_x (int n, traj_t x) { int num_steps = 0; assert (0 <= n && n < numberof(bounds)); assert (x%2 == 1); for (;;) { DEBUG(printf(" at x=%s num_steps %d\n", traj_decimal_str(x), num_steps)); if (UNLIKELY (is_minimum(x))) break; num_steps += traj_step_reduced_odd(&x); if (UNLIKELY (num_steps < 0)) error ("num_steps overflow at x=%s\n", traj_decimal_str(x)); last_num_ops++; if (UNLIKELY(bounds_is_bad(n,x,num_steps))) return (-1); } return (num_steps); } static void check_configuration (void) { if (! (COUNT_TYPE == COUNT_TYPE_ALL || COUNT_TYPE == COUNT_TYPE_HALF || COUNT_TYPE == COUNT_TYPE_TRIPLE)) error("Bad COUNT_TYPE\n"); if (numberof(count_low_zeros_table) != (size_t)1 << COUNT_LOW_ZEROS_TABLE_BITS) error("Oops, COUNT_LOW_ZEROS_TABLE_BITS doesn't match table size\n"); } void show_configuration (void) { static int done = 0; if (done) return; done = 1; if (option_verbose || WANT_ASSERT) printf("# assert()s %s\n", WANT_ASSERT ? "enabled" : "disabled"); if (option_verbose) { #ifdef __GNUC__ printf("# Have __GNUC__\n"); #else printf("# Not __GNUC__\n"); #endif printf("# traj_t is %zu bytes = %d bits\n", sizeof(traj_t), TRAJ_BITS); printf("# COUNT_LOW_ZEROS_TABLE_BITS = %d, table size %zu\n", COUNT_LOW_ZEROS_TABLE_BITS, sizeof(count_low_zeros_table)); } } void output (int n, uint64_t x) { printf("%d %"PRIu64"\n", n, x); int num_steps = num_steps_of_x_whole(x); if (num_steps != n) error("oops, x=%"PRIu64" n=%d but steps %d\n", x,n,num_steps); check_smallest (n,x, ""); ferror_die (stdout, "stdout", "writing"); } /* a(n) has not yet been output. If smallest[n] != 0 then output it now, and any further smallest[n+1] != 0 etc. Return new n which has not yet been output. */ static int output_some (int n) { for (;;) { if (UNLIKELY (n >= numberof(smallest))) error ("oops, n exceeds MAXN, increase MAXN and re-compile\n"); if (smallest[n] == 0) break; output (n, smallest[n]); if (UNLIKELY (n >= option_maxn)) { printf("# stop for option_maxn=%d\n", option_maxn); exit(0); } n++; } assert (n == smallest_unknown_n()); return (n); } /* Look for a(n) and onwards, with first candidate x. Must have x odd. */ void search_from (int n, uint64_t x) { if (option_verbose) printf("# search from x=%"PRIu64"\n", x); if (x%2 != 1) error("oops, search_from() is for x odd\n"); uint64_t next_double_x = find_next_double(NULL); for ( ; ; x += 2) { if (UNLIKELY(flag_interrupt)) { flag_interrupt = 0; save (n,x); if (flag_terminate) return; } DEBUG(printf("try n=%d %d x=%"PRIu64", next_double_x %"PRIu64"\n", n, smallest_unknown_n(),x,next_double_x)); assert (n == smallest_unknown_n()); if (COUNT_HALF && UNLIKELY(x > next_double_x)) { next_double_x = set_doubles(x); n = output_some(n); } assert (x < next_double_x); last_num_x++; int num_steps = num_steps_of_x(n,x); DEBUG(printf(" x=%"PRIu64" num steps %d (by whole %d)\n", x, num_steps, num_steps_of_x_whole(x))); if (LIKELY (num_steps < 0)) { assert (num_steps_of_x_whole(x) < n); continue; } assert (num_steps_of_x_whole(x) == num_steps); if (UNLIKELY(num_steps >= numberof(smallest))) error("oops, num_steps exceeds MAXN, increase MAXN and re-compile\n"); if (UNLIKELY(smallest[num_steps] == 0)) { set_smallest(num_steps, x); next_double_x = find_next_double(NULL); n = output_some (n); } } } void resume (void) { if (option_verbose) printf("resume from %s\n", saved_state_filename); FILE *fp = fopen_or_die (saved_state_filename, "r"); int count_type, n; uint64_t x; if (fscanf(fp, "COUNT_TYPE = %d\nn = %d\nx = %"SCNu64"\n", &count_type, &n, &x) != 3) error("%s format unrecognised\n", saved_state_filename); int i; uint64_t prev; while (fscanf(fp, "%d %"SCNu64"\n", &i, &prev) == 2) { if (option_verbose) printf("resume a(%d) = %"PRIu64"\n", i, prev); if (prev) check_smallest (i,prev, "resume data "); set_smallest (i,prev); } if (! (fscanf(fp, "end of terms%n\n", &i) == 0 && i==12)) /* 12 characters parsed */ error("%s marker \"end of terms\" not found\n", saved_state_filename); int unknown_n = smallest_unknown_n(); if (n != unknown_n) error ("%s has n=%d but smallest unknown actually %d\n", saved_state_filename, n, unknown_n); ferror_die (fp, saved_state_filename, "reading"); fclose_or_die (fp, saved_state_filename); search_from (n,x); } int main (int argc, char *argv[]) { DEBUG (option_verbose = 1); setbuf(stdout,NULL); init_save(); int option_resume = 0; int i, endpos; for (i = 1; i < argc; i++) { const char *arg = argv[i]; if (strcmp(arg,"-v")==0) { option_verbose++; } else if (strcmp(arg,"start")==0) { option_resume = 0; } else if (strcmp(arg,"resume")==0) { option_resume = 1; } else if (sscanf(arg, "maxn=%d%n", &option_maxn, &endpos) == 1 && endpos == strlen(arg)) { } else { error("Unrecognised command line option: %s\n", arg); } } show_configuration(); check_configuration(); if (option_resume) { resume(); } else { const char *A_number = info[COUNT_TYPE].A_number; printf("# %s = %s\n", A_number, info[COUNT_TYPE].count_type_name); search_from (0,1); } return(0); }