/* Kevin Ryde, December 2023 Usage: ./a.out [-v] maxn Find terms of A364779 and A364780 up to n = "maxn", being A364779(n) = largest number which has sum of digits n in fractional base 4/3 A364780(n) = number of numbers >=0 which have sum of digit n in fractional base 4/3 Output is a comma separated list of terms, produced at the end of all searching. The strategy is to step through all numbers with sum of digits <= maxn and count and note the largest of each sum. This is only feasible up to maybe maxn = 150. Command Line ------------ Optional parameter "-v" prints results with greater verbosity, or "-v -v" for even more verbosity. Command-line parameter "bfiles" writes b-files b364779.txt and b364780.txt in addition to printing to stdout, ./a.out bfiles 80 Value Type ---------- The #define VALUE_BITS selects the number of bits for values considered. The conditionals choose a big enough value_t type based on UINT_WIDTH etc from limits.h. The default is 64 bits which is limited to n=107. For GNU C, VALUE_BITS 128 uses "__int128" which is available on a 64-bit system. 128 bits is not the default so as not to be compiler and machine dependent. Set it to try maxn above 107. Save and Resume --------------- To help long runs, the state of the calculation is saved at 5 minute intervals and on SIGINT, SIGTERM, SIGHUP termination. saved-state.data binary data file progress.txt summary text file The run can be resumed from saved-state.data by ./a.out resume saved-state.data is the global "struct state" variable. Its format depends on the machine data type sizes, alignments, endianness, etc. Implementation Notes -------------------- The search is made over candidate numbers k with sum of digits <= maxn and ending with a 0 digit, k = ...0 final 0 digit in base 4/3, meaning k is a multiple of 4 These are extended to all k at the end of searching, k = ..0 -> k+1 = ..1, sum of digits +1 -> k+2 = ..2, sum of digits +2 -> k+3 = ..3, sum of digits +3 k = ..0 values are traversed by a depth-first search of digit prefixes. A new second-least significant digit is inserted by k_new = (k+d) * 4/3 = ...d0 new digit d If k != 0 mod 3, then d increases it to a multiple of 3 ready to multiply by 4/3 (and so k_new is an integer). The unique d for this case, and resulting k_new, are q = floor((k+2)/3) so q=ceil(k/3) r = (k+2) mod 3 = 0 or 1 d = 2 - r k_new = 4*q If k == 0 mod 3, then this calculation has r=2 and there are two choices for digit d. k_new = 4*q as above is d=0, and d=3 is possible too, k_new = ..00 d=0 k_new' = ..30 = k_new + 4 d=3 k_new has sum_of_digits unchanged so always continues. k_new' has sum_of_digits + 3 and if that's <= maxn then k_new' is pushed on the stack[] array as pending work. d = 1 or 2 may find its sum_of_digits + d > maxn, and in that case stop looking at it and pop a saved k from the stack[] instead. Overflow detection is at k & VALUE_HIGHBIT before calculating k_new. The biggest new quantity is k_new + 4, plus later low digit +3, and that is < 2*k. If the high bit of k is 0 then no overflow. */ /* Set WANT_ASSERT to 1 to enable self-checks (slow). Set WANT_DEBUG to 1 for some rough development prints. */ #define WANT_ASSERT 0 #define WANT_DEBUG 0 #if ! WANT_ASSERT #define NDEBUG #endif /* for UINT_WIDTH etc from limits.h */ #define __STDC_WANT_IEC_60559_BFP_EXT__ #include <assert.h> #include <ctype.h> #include <errno.h> #include <inttypes.h> #include <limits.h> #include <signal.h> #include <stdarg.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdnoreturn.h> #include <time.h> #include <sys/time.h> /* ------------------------------------------------------------------------ */ /* 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 #define MIN(x,y) ((x)<=(y) ? (x) : (y)) #define MAX(x,y) ((x)>=(y) ? (x) : (y)) #define numberof(array) (sizeof(array)/sizeof((array)[0])) noreturn ATTRIBUTE_PRINTF void error (const char *format, ...) { va_list ap; va_start (ap, format); vfprintf (stderr, format, ap); va_end (ap); exit(1); } 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); } void ferror_die (FILE *fp, const char *filename, const char *action) { if (ferror(fp)) error("Error %s %s\n", action, filename); } void fwrite_or_die (const void *ptr, size_t size, size_t num, FILE *fp, const char *filename) { if (fwrite(ptr,size,num,fp) != num) error("Error writing %s, size %zu num %zu bytes: %s", filename, num, size, strerror(errno)); } void fcopy_contents(FILE *dst, FILE *src) { int c; rewind(src); while ((c=fgetc(src)) != EOF) fputc(c,dst); } void fread_or_die (void *ptr, size_t size, size_t num, FILE *fp, const char *filename) { size_t got = fread(ptr,size,num,fp); ferror_die(fp, filename, "reading"); if (got != num) error("File %s too short\n", filename); } void fexpect_eof_or_die (FILE *fp, const char *filename) { int c = fgetc(fp); ferror_die(fp, filename, "testing EOF"); if (c != EOF) error("File too long %s\n", filename); } void fclose_or_die (FILE *fp, const char *filename) { if (fclose(fp) != 0) error("Error closing %s\n", filename); } void fflush_or_die (FILE *fp, const char *filename) { if (fflush(fp) != 0) error("Error writing %s: %s", filename, strerror(errno)); } 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)); } 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)); } 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)); } void clock_gettime_or_die (clockid_t id, struct timespec *t, const char *name) { if (clock_gettime(id, t) != 0) error("Cannot clock_gettime() %s: %s\n", name, strerror(errno)); } double clock_gettime_double_sec_or_die (clockid_t id, const char *name) { struct timespec t; clock_gettime_or_die (id, &t, name); return ((double) t.tv_sec + t.tv_nsec / 1e9); } /* elapsed_cputime() returns the amount of CPU time in seconds used since the last call to elapsed_cputime(), or since program start for the first call. */ double elapsed_cputime (void) { static double prev_t = 0.0; double t = clock_gettime_double_sec_or_die (CLOCK_PROCESS_CPUTIME_ID, "CPUTIME"); double elapsed = t - prev_t; prev_t = t; return (elapsed); } /* ------------------------------------------------------------------------ */ /* desired size for value_t type */ #define VALUE_BITS 64 #if VALUE_BITS <= UINT_WIDTH typedef unsigned value_t; const char value_t_name[] = "unsigned"; #elif VALUE_BITS <= ULONG_WIDTH typedef unsigned long value_t; const char value_t_name[] = "unsigned long"; #elif VALUE_BITS <= ULLONG_WIDTH typedef unsigned long long value_t; const char value_t_name[] = "unsigned long long"; #elif defined(__SIZEOF_INT128__) && VALUE_BITS <= 128 /* GNU C extension __int128 */ typedef unsigned __int128 value_t; const char value_t_name[] = "unsigned __int128"; #else #error No data type for VALUE_BITS #endif #define VALUE_MAX (~ (value_t) 0) #define VALUE_HIGHBIT (VALUE_MAX ^ (VALUE_MAX >> 1)) struct result { value_t largest; uint64_t count; }; struct stack { value_t k; int sum_of_digits; }; struct state { struct result result[500]; /* big enough to hold maxn+3 */ struct stack stack[1000]; value_t saved_k; int sp_pos; double cputime; int maxn; }; static struct state state; /* command line options */ int option_verbose = 0; int option_bfiles = 0; static const struct stack *stack_last_entry = state.stack + numberof(state.stack) - 1; /* Return the sum of digits of k in base 4/3 (A244041). */ int value_base43_sum_of_digits (value_t k) { int sum_of_digits = 0; while (k) { sum_of_digits += k%4; k = (k/4) * 3; } return (sum_of_digits); } /* Return a string which is the decimal digits of k. Explicit conversion since __int128 not in printf() etc. */ char * value_decimal_str (value_t k) { /* 3 decimal digits per byte of k, plus '\0' terminator */ static char buf[3*sizeof(k) + 1]; int i = sizeof(buf)-1; do { if (--i < 0) error("value_decimal_str() buffer too small\n"); int digit = k % 10; k /= 10; buf[i] = digit + '0'; } while (k); return (buf + i); } /* str is a '\0'-terminated character string of decimal digits. Return their value, or error exit if bad string. */ value_t value_from_decimal_str (const char *str) { /* Not using sscanf() as it doesn't report overflow, and doesn't have __int128. */ value_t k = 0; int c; while ((c = *str++)) { if (! isdigit(c)) error("value_from_decimal_str() invalid digit %d \"%c\"\n", c,c); c -= '0'; assert (0 <= c && c <= 9); k = 10*k + c; } return (k); } /* Return a string which is the base 4/3 digits of k. */ char * value_base43_str (value_t k) { /* 20 digits per byte of k since log_{4/3} 256 < 20 */ static char buf[20*sizeof(k) + 1]; int i = sizeof(buf)-1; do { if (--i < 0) error("value_base43_str() buffer too small\n"); int digit = k % 4; k = (k-digit)/4 * 3; buf[i] = digit + '0'; } while (k); return (buf + i); } /* Number of bits required to represent k, smallest L with k < 2^L. */ int value_bitlength (value_t k) { int ret = 0; while (k) { k >>= 1; ret++; } return (ret); } /* ------------------------------------------------------------------------ */ /* Final Mult4 Steps result[] has counts and largest of k = ..0. Count and consider largest for each of k+1,2,3 too. At sum of digits n, add count[n-p] and consider largest[n-p] + p, for p=1..3. state_result_mult4() just returns the all-endings result. This is for intermediate display in the search, and no change to state.result[]. mult4_propagate() modifies all state.result[] to make final all-endings results. */ struct result state_result_mult4 (int n) { int p; struct result r = state.result[n]; for (p = 1; p <= 3; p++) { if (n-p < 0) break; r.count += state.result[n-p].count; r.largest = MAX(r.largest, state.result[n-p].largest + p); } return (r); } void mult4_propagate (void) { int n; for (n = state.maxn; n > 0; n--) state.result[n] = state_result_mult4(n); } /* ------------------------------------------------------------------------ */ /* Some initial values, as a consistency check. */ const char * const want_largest[] = { /* "largest" values exceed 64 bits, so as strings and convert if/when needed to __int128 */ "0", /* n=0 */ "1", "2", "4", "5", "8", "16", "17", "32", "44", "80", /* n=10 */ "256", "257", "344", "460", "464", "620", "1472", "1964", "2620", "2624", /* n=20 */ "3500", "6224", "8300", "11068", "11072", "26240", "34988", "46652", "262144", "262145", /* n=30 */ "349528", "349529", "466040", "621392", "828524", "1104700", "1532816", "3633344", "6459280", "6459281", /* n=40 */ "11483168", "19616912", "34874512", "34874513", "61999136", "110220688", "110220689", "146960920", "146960921", "261263872", /* n=50 */ "261263873", "825724928", "1100966572", "1100966573", "1527638096", "3479625728", "8248001728", "8248001729", "10997335640", "34756735232", /* n=60 */ "46342313644", "46342313645", "61789751528", "146464596224", "347175339200", "617200603024", "617200603025", "822934137368", "1097245516492", "1097245516496", /* n=70 */ "1462994021996", "2600878261328", "4623783575696", "8220059690128", "8220059690129", "19484585932160", "25979447909548", "25979447909549", "34639263879424", "46185570378896", /* n=80 */ "82107884751232", "82109581509824", "194630119325696", "259506825767596", "640123758297088", "640123758297089", "1137997792528160", "1517330390037548", "2023107186716732", "2697476248955648", /* n=90 */ "3596634998607532", "6394017775302272", "8525357033736364", "25891577811484672", "25891577811484673", "34522103748646232", "61372628886482192", "81830171848642924", "145479522589263296", "817399347771772928", /* n=100 */ "1089865797029030572", "1089865797029030573", "1937539194718276576", "1937539194718276577", "2583385592957702104", "3444514123943602816", "4592685498591470480", "10886365626290892992", "14515154168387857324", "14515154168387857325", /* n=110 */ "25804718521578413024", "34406291362104550700", "61166740199296979024", "108740871465416851600", "108740871465416851601", "144987828620555802136", "144987828620555802137", "458221703908425886720", "458222743151581758656", "610963657535442344876", /* n=120 */ "1930946868260163460352", "2574595824346884613804", "2574595824346884613805", "25716919973235395526656", "45718968841307369825168", "60958625121743159766892", "60958625121743159766893", "81278166828990879689192", "256879144545946483955968", "256879144545946483955969", /* n=130 */ "342505526061261978607960", "342505526061261978607961", "456674034748349304810640", "608898712997799073080832", "1443315467846634839895296", "1924420623795513119860396", "4561589626774549617446912", "6082119502366066156595884", "6082119502366066156595885", "8109492669821421542127848", /* n=140 */ "14416875857460304963782848", "19222501143280406618377132", "21358239202431873710342144", "67502583158303205800587520", "160006123041903895231022272", "160006123041903895231022273", "284455329852273591521817376", "284455329852273591521817377", "505698364181819718261008672", "674264485575759624348011564" /* n=150 */ }; void check_want_largest (int n, value_t k) { if (n < numberof(want_largest)) { value_t want = value_from_decimal_str(want_largest[n]); if (k != want) { fprintf(stderr, " oops, n=%d largest want %s", n, want_largest[n]); fprintf(stderr, " got largest %s\n", value_decimal_str(k)); exit(1); } } } const uint64_t want_count[] = { 1, /* n=0 */ 1, 1, 2, 1, 2, 4, 3, 5, 6, 7, /* n=10 */ 14, 13, 15, 19, 19, 30, 39, 45, 56, 65, /* n=20 */ 75, 95, 124, 140, 174, 216, 268, 338, 417, 501, /* n=30 */ 627, 780, 974, 1203, 1454, 1825, 2266, 2769, 3427, 4268, /* n=40 */ 5188, 6433, 7930, 9671, 12000, 14738, 18265, 22642, 27961, 34528, /* n=50 */ 42523, 52325, 64425, 79717, 98306, 121591, 150079, 184972, 228108, 281039, /* n=60 */ 346977, 428571, 528790, 652462, 804149, 992143, 1224502, 1509733, 1863870, 2298988, /* n=70 */ 2836503, 3500608, 4318055, 5327837, 6571192, 8108858, 10004625, 12341914, 15232717, 18787215, /* n=80 */ 23180257, 28601426, 35279642, 43531204, 53707261, 66254522, 81753503, 100867178, 124433791, 153533887, /* n=90 */ 189401566, 233673115, 288317273, 355688400, 438845986, 541436816, 667946966, 824111073, 1016752325, 1254405621, /* n=100 */ 1547659925, 1909414996, 2355727690, 2906337436, 3585685029, 4423942074, 5457946483, 6733835531, 8307944052, 10249702264, /* n=110 */ 12645781723, 15601713283, 19248612044, 23748165767, 29299308382, 36147957130, 44597618936, 55022515028, 67883999433, 83752194434, /* n=120 */ 103329349956, 127483079676, 157282052049, 194047333205, 239406485313, 295367554923, 364411149545, 449592387787, 554685236886, 684343924488, /* n=130 */ 844311019117, 1041671222446, 1285162629861, 1585571911674, 1956202709928, 2413467192366, 2977621359920, 3673648543344, 4532366946844, 5591817012565, /* n=140 */ 6898914002400, 8511549373511, 10501142189448, 12955805788563, 15984251422979, 19720594207726, 24330320965208, 30017581945968, 37034252309149, 45691085253023 /* n=150 */ }; void check_want_count (int n, uint64_t count) { if (n < numberof(want_count)) { uint64_t want = want_count[n]; if (count != want) error(" oops, sum=%d expected count %"PRIu64"\n", n, want); } } int check_state (void) { int bad = 0; int n; for (n=0; n <= MIN(state.maxn, numberof(want_count)-1); n++) { struct result r = state_result_mult4(n); if (r.count > want_count[n]) { fprintf(stderr, "oops, n=%d intermediate result count too big", n); bad = 1; } } for (n=0; n <= MIN(state.maxn, numberof(want_largest)-1); n++) { struct result r = state_result_mult4(n); if (r.largest > value_from_decimal_str(want_largest[n])) { fprintf(stderr, "oops, n=%d intermediate result largest too big", n); bad = 1; } } for (n=0; n <= state.maxn; n++) { if (state.result[n].largest && value_base43_sum_of_digits(state.result[n].largest) != n) { fprintf(stderr, "oops, n=%d largest wrong sum of digits", n); bad = 1; } } for (n=0; n < state.sp_pos; n++) { if (value_base43_sum_of_digits(state.stack[n].k) != state.stack[n].sum_of_digits) { fprintf(stderr, "oops, stack[%d] wrong sum of digits", n); bad = 1; } } if (bad) exit(1); return(1); } /* ------------------------------------------------------------------------ */ /* Save and Restore */ const char saved_state_filename[] = "saved-state.data"; const char temp_filename[] = "saved-state.data.tempfile"; const char progress_filename[] = "progress.txt"; static volatile sig_atomic_t flag_interrupt = 0; static volatile sig_atomic_t flag_terminate = 0; /* progress_percent() returns estimated progress in the calculation. This is how far result[n].count is through want_count[n], for the biggest n which want_count[] knows, and with result[n].count entries "all ending" state_result_mult4() per the final results. */ struct progress { int n; uint64_t count_upto; uint64_t count_final; double count_percent; /* count_upto within count_final */ double prev_percent; /* what it was on last call */ double elapsed_percent; /* difference now - prev */ }; struct progress progress_percent (void) { static struct progress p; p.n = MIN(state.maxn, numberof(want_count)-1); struct result r = state_result_mult4(p.n); p.count_upto = r.count; p.count_final = want_count[p.n]; p.prev_percent = p.count_percent; p.count_percent = 100.0 * p.count_upto / MAX(1, p.count_final); p.elapsed_percent = p.count_percent - p.prev_percent; return (p); } void save_state (value_t k, struct stack *sp) { flag_interrupt = 0; state.saved_k = k; state.sp_pos = sp - state.stack; double t_elapsed = elapsed_cputime(); state.cputime += t_elapsed; check_state(); /* Write first to temp_filename and then rename, so atomic replacement of file. */ FILE *fp = fopen_or_die (temp_filename, "wb"); fwrite_or_die (&state, sizeof(state), 1, fp, temp_filename); fclose_or_die (fp, temp_filename); rename_or_die (temp_filename, saved_state_filename); /* Progress */ struct progress p = progress_percent(); fp = fopen_or_die (temp_filename, "w+"); fprintf(fp, "k = %s (base 4/3)\n", value_base43_str(k)); fprintf(fp, "stack holding %d\n", state.sp_pos); fprintf(fp, "\n"); value_t largest = state.result[state.maxn].largest; fprintf(fp, "largest[%d] = %d bits, %zu base 4/3 digits\n", state.maxn, value_bitlength(largest), strlen(value_base43_str(largest))); fprintf(fp, " %s\n", value_decimal_str(largest)); fprintf(fp, " %s\n", value_base43_str(largest)); fprintf(fp, "\n"); fprintf(fp, "total CPU time %.4lf hours\n", state.cputime / 3600.); fprintf(fp, "upto %"PRIu64" of %"PRIu64" is %.3f%% (at n=%d)\n", p.count_upto, p.count_final, p.count_percent, p.n); fprintf(fp, "last chunk %.1lf seconds, %.6lf%%\n", t_elapsed, p.elapsed_percent); fflush_or_die (fp, temp_filename); if (option_verbose) { fcopy_contents(stdout,fp); printf("\n"); } fclose_or_die (fp, temp_filename); rename_or_die (temp_filename, progress_filename); if (flag_terminate) exit(0); } void restore_state (void) { const char *filename = saved_state_filename; if (option_verbose) printf("resume from %s\n", filename); FILE *fp = fopen_or_die (filename, "r"); fread_or_die (&state, sizeof(state), 1, fp, filename); fexpect_eof_or_die (fp, filename); fclose_or_die (fp, filename); } void sig_handler_save_state (int signum) { if (option_verbose) 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 () { elapsed_cputime(); /* dummy first elapsed */ progress_percent(); 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); } /* ------------------------------------------------------------------------ */ void init_state (void) { /* state.maxn has been set, fill the rest */ /* k=0 */ state.result[0].largest = 0; state.result[0].count = 1; state.saved_k = 4; /* "30" in base 4/3 */ state.sp_pos = 0; } void search (void) { if (option_verbose) { printf ("search maxn=%d, using value_t %zu bytes\n", state.maxn, sizeof(value_t)); #if ! WANT_ASSERT printf("assert()s not enabled\n"); #endif } assert (printf("assert()s enabled\n")); if (state.maxn + 3 >= numberof(state.result)) error ("maxn %d too big for result[] array", state.maxn); /* sp is the next unused place in stack[] */ struct stack *sp = state.stack + state.sp_pos; value_t k = state.saved_k; int sum_of_digits = value_base43_sum_of_digits(k); for (;;) { DEBUG(printf("at k=%s \"%s\" sum=%d\n", value_decimal_str(k), value_base43_str(k), sum_of_digits)); assert (0 <= sum_of_digits && sum_of_digits <= state.maxn); assert (value_base43_sum_of_digits(k) == sum_of_digits); assert (k % 4 == 0); assert (check_state()); if (UNLIKELY(flag_interrupt)) { flag_interrupt = 0; save_state(k,sp); if (flag_terminate) exit(0); } { /* count and consider for largest */ struct result *rp = state.result + sum_of_digits; rp->count++; if (UNLIKELY(k > rp->largest)) { rp->largest = k; if (option_verbose >= 2) printf("new larger sum=%d k=%s\n", sum_of_digits, value_decimal_str(k)); } } if (UNLIKELY(k & VALUE_HIGHBIT)) error("overflow value_t (%zu bytes)", sizeof(value_t)); assert ((k & 2) == 0); k |= 2; /* k+=2 */ value_t q = k / 3; unsigned r = k % 3; k = q << 2; if (UNLIKELY(r==2)) { /* continue with new digit 0 (unchanged sum of digits); and push new digit 3 on stack[] */ int other_sum_of_digits = sum_of_digits + 3; if (LIKELY(other_sum_of_digits <= state.maxn)) { sp->k = k + 4; /* k = "..00" + 4 = "..30" */ sp->sum_of_digits = other_sum_of_digits; if (UNLIKELY(sp == stack_last_entry)) error("stack[] array too small"); sp++; } } else { /* descend to digit 1 or 2 according as r=1,0 */ unsigned digit = 2 - r; sum_of_digits += digit; if (UNLIKELY(sum_of_digits > state.maxn)) { /* exceed maxn, pop stack to a previously saved k */ if (UNLIKELY(sp == state.stack)) break; k = (sp-1)->k; sum_of_digits = (sp-1)->sum_of_digits; sp--; } } } } void output (void) { int n; if (option_verbose) { uint64_t total_count = 0; for (n=0; n <= state.maxn; n++) { printf("n=%d count %"PRIu64" largest %s\n", n, state.result[n].count, value_decimal_str(state.result[n].largest)); printf(" %s\n", value_base43_str(state.result[n].largest)); total_count += state.result[n].count; } printf("total count %"PRIu64"\n", total_count); } else { printf("A364780 count = "); for (n=0; n <= state.maxn; n++) printf("%"PRIu64"%s", state.result[n].count, n == state.maxn ? "" : ","); printf("\n"); printf("A364779 largest = "); for (n=0; n <= state.maxn; n++) printf("%s%s", value_decimal_str(state.result[n].largest), n == state.maxn ? "" : ","); printf("\n"); } if (option_bfiles) { { const char filename[] = "b364779.txt"; FILE *fp = fopen_or_die (filename,"w"); int n; for (n=0; n <= state.maxn; n++) fprintf (fp, "%d %s\n", n, value_decimal_str(state.result[n].largest)); fclose_or_die(fp,filename); } { const char filename[] = "b364780.txt"; FILE *fp = fopen_or_die (filename,"w"); int n; for (n=0; n <= state.maxn; n++) fprintf (fp, "%d %"PRIu64"\n", n, state.result[n].count); fclose_or_die(fp,filename); } } for (n=0; n <= state.maxn; n++) { check_want_largest(n, state.result[n].largest); check_want_count (n, state.result[n].count); int got_sum_of_digits = value_base43_sum_of_digits(state.result[n].largest); if (got_sum_of_digits != n) error(" oops, sum of digits %d != %d = n\n", got_sum_of_digits, n); } } int main (int argc, char *argv[]) { int i, endpos; int option_resume = 0; setbuf(stdout,NULL); state.maxn = 20; /* default */ 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 (strcmp(arg,"bfiles")==0) { option_bfiles = 1; } else if (sscanf(arg, "%u%n", &state.maxn, &endpos) == 1 && endpos == strlen(arg)) { } else { error("Unrecognised command line option: %s\n", arg); } } if (option_verbose) { printf("value_t type \"%s\", size %zu bytes\n", value_t_name, sizeof(value_t)); printf("sizes: struct result %zu, struct stack %zu\n", sizeof(struct result), sizeof(struct stack)); } if (option_resume) restore_state(); else init_state(); init_save(); search(); mult4_propagate(); output(); ferror_die(stdout,"stdout","writing"); return(0); }