/* Generate optimal addition chains classed by number of nonstar steps We do this by searching the tree of addition chains depth-first, limited to a specified depth. (We know we need 17 to hit the first value of n where the optimal 1-nonstar chain beats the optimal star chain.) To speed up the search, we prune nodes that have not progressed far enough. We use Clifft's improved thresholds, see http://additionchains.com/; but we only apply the thresholds to star-chains that have been found, since we always want the optimal star chain even if there are shorter unstarred chains. We further make the tree of nodes explicit (rather than just implicit via the stack) to try to get some speed advantage from the fact that the larger siblings of a node are the unstar moves from that node, so we can just do a merge of them with the sequence (ancestors+self) to get all children; add them as a linked list. This approach saves a great deal of time in copying memory around. */ #include #include #include #include #include #include #define MAX_LENGTH 18 #define REPORT_FREQ 1000000000ULL #define MAX_VAL (1 << MAX_LENGTH) int diglen(int* num, int digits) { while (digits > 0 && num[digits-1] == 0) --digits; return digits; } int digsum(int* num, int digits) { int sum = 0; while (digits > 0) { sum += num[digits-1]; --digits; } return sum; } void add_one(int* num, int base) { int pos = 0; while (true) { if (++(num[pos]) == base) num[pos++] = 0; else return; }} typedef uint32_t Int; Int starval[MAX_VAL+1] = {MAX_LENGTH}; typedef struct { Int threshold, reason; } PruneLevel; PruneLevel pruneLevel[MAX_LENGTH]; void recompute_prune_levels() { pruneLevel[0].threshold = 1; pruneLevel[1].threshold = 1; for (int i = 2; i < MAX_LENGTH; ++i) pruneLevel[i].threshold = MAX_VAL + 1; for (Int n = 5; n <= MAX_VAL; ++n) { Int oddpart = n; int twos = 0; while (oddpart % 2 == 0) { ++twos; oddpart /= 2; } int r = starval[n]; if (MAX_LENGTH < r) r = MAX_LENGTH; for (int s = 1; s < r-1; ++s) { int i = r - s; Int thisLim = oddpart; Int smallfac, bigfac; if (s < twos) thisLim <<= (twos-s); else { int excess = s - twos; switch (excess) { case 0: break; case 1: thisLim = thisLim/2 + 1; break; case 2: if (thisLim % 3 == 0) thisLim /= 3; else thisLim = thisLim/3 + 1; break; default: smallfac = (1 << (excess-2)) + 1; if (oddpart % smallfac == 0) thisLim = (oddpart/smallfac)/2 + 1; else { bigfac = (1 << (excess-1)) + 1; if (oddpart % bigfac == 0) thisLim = oddpart/bigfac; else thisLim = oddpart/bigfac + 1; }}} if (thisLim < pruneLevel[i].threshold) { pruneLevel[i].threshold = thisLim; pruneLevel[i].reason = n; }}}} void print_prune_levels() { printf(" ::Pruning thresholds:"); for (int i = 1; i < MAX_LENGTH; ++i) { printf(" %d:%d[%d]", i, pruneLevel[i].threshold, pruneLevel[i].reason); } printf("\n"); fflush(stdout); } typedef struct NodeStruct Node; struct NodeStruct { Int current; // a number in the chain Node* parent; // the previous node in the chain Node* child; // the next larger number in the chain currently processing Node* sib; // the next larger sibling of this node int length; // the length of the chain to here int unstars; // how many unstar steps have occurred to here int refcnt; // in case we store this on a best list or something }; void print_set(Node* n) { printf("{%d", n->current); for (Node* p = n->parent; p != NULL; p = p->parent) { printf(",%d", p->current); } printf("}"); } #define UNSTAR_LIMIT (MAX_LENGTH-3) #define BEST_LIMIT 8 Node* best[(1+MAX_VAL)][UNSTAR_LIMIT][BEST_LIMIT] = {NULL}; int lbest[(1+MAX_VAL)][UNSTAR_LIMIT] = {0}; int nbest[(1+MAX_VAL)][UNSTAR_LIMIT] = {0}; Node* head = NULL; unsigned long long treeSize = 0; Node* avail = NULL; unsigned long long int nodeCount = 0; unsigned long long int pruneCount = 0; /* Put the node on the avail list, reducing reference counts on the connected nodes and releasing them if need be */ void release(Node *n) { if (n->child != NULL && --(n->child->refcnt) == 0) release(n->child); if (n->sib != NULL && --(n->sib->refcnt) == 0) release(n->sib); if (n->parent != NULL && --(n->parent->refcnt) == 0) release(n->parent); n->sib = avail; avail = n; --treeSize; } int main() { printf("Optimizing programs of length up to %d, values up to %d\n", MAX_LENGTH, MAX_VAL); printf("Size of node is %lu\n", sizeof(Node)); starval[1] = 0; starval[2] = 1; starval[3] = 2; starval[4] = 2; int digits[MAX_LENGTH+1] = {0}; digits[2] = 1; digits[0] = 1; for (Int n = 5; n <= MAX_VAL; ++n) { int est = diglen(digits, MAX_LENGTH+1) + digsum(digits, MAX_LENGTH+1) - 2; if (est < MAX_LENGTH) starval[n] = est; else starval[n] = MAX_LENGTH; add_one(digits, 2); } recompute_prune_levels(); print_prune_levels(); /* Create the initial states */ Node* root = (Node*)(malloc(sizeof(Node))); root->current = 1; root->parent = NULL; root->child = NULL; root->sib = NULL; root->length = 0; root->unstars = 0; root->refcnt = 1; treeSize = 1; head = root; best[1][0][0] = root; lbest[1][0] = 0; nbest[1][0] = 1; while (head != NULL) { int newlength = head->length + 1; Node* newchild = NULL; Node* curchild = NULL; /* Need to merge the list of current+earlier with the (later) sibs to create the children */ Node* starops = root; Int nextstar = head->current + starops->current; Node* sibs = head->sib; while (starops != NULL || sibs != NULL) { ++nodeCount; Int nx = nextstar; int nxunstars = head->unstars; if (sibs == NULL || nextstar <= sibs->current) { /* star move to nextstar */ /* Was it a tie with a sib that we need to skip over? */ if (sibs != NULL && nextstar == sibs->current) sibs = sibs->sib; starops = starops->child; if (starops == NULL) nextstar = MAX_VAL + 1; else nextstar = head->current + starops->current; } else { /* unstar move to sibling */ nx = sibs->current; nxunstars = head->unstars+1; sibs = sibs->sib; } if (nodeCount % REPORT_FREQ == 0) { printf("The %llu*%lluth chain reached %d in %d steps. Chain: ", nodeCount/REPORT_FREQ, REPORT_FREQ, nx, newlength); print_set(head); printf("\n Pruned %llu branches, tree has %d nodes.\n", pruneCount, treeSize); fflush(stdout); } bool worthy = true; for (int astarry = 0; astarry <= nxunstars; ++astarry) { if (nbest[nx][astarry] == 0) continue; if (newlength > lbest[nx][astarry]) { worthy = false; break; }} if (worthy) { // will be stored on its list if (nbest[nx][nxunstars] == 0 || newlength < lbest[nx][nxunstars]) { /* clear out any now-obsolete lists */ for (int asunstarry = nxunstars; asunstarry < UNSTAR_LIMIT; ++asunstarry) { if (nbest[nx][asunstarry] == 0) continue; if (lbest[nx][asunstarry] <= newlength) break; /* OK, we have obsolete nodes. Release them */ for (int i = 0; i < nbest[nx][asunstarry] && i < BEST_LIMIT; ++i) { if (--(best[nx][asunstarry][i]->refcnt) == 0) { release(best[nx][asunstarry][i]); }} nbest[nx][asunstarry] = 0; } /* See if we have to update the prune levels */ if (nxunstars == 0 && newlength < starval[nx]) { starval[nx] = newlength; for (int pli = 2; pli < MAX_LENGTH; ++pli) { if (nx == pruneLevel[pli].reason) { recompute_prune_levels(); print_prune_levels(); break; }}}} /* OK, we have cleared the way; now simply need to add to its list */ if (nbest[nx][nxunstars] < BEST_LIMIT) { lbest[nx][nxunstars] = newlength; best[nx][nxunstars][nbest[nx][nxunstars]] = head; ++(head->refcnt); } ++(nbest[nx][nxunstars]); } /* See if we will be extending this new chain */ if (newlength == MAX_LENGTH) continue; if (nx < pruneLevel[newlength].threshold) { ++pruneCount; continue; } /* Yes */ Node* newnode = avail; if (newnode == NULL) newnode = (Node*)(malloc(sizeof(Node))); else avail = newnode->sib; newnode->current = nx; newnode->parent = head; ++(head->refcnt); newnode->child = NULL; newnode->sib = NULL; newnode->length = newlength; newnode->unstars = nxunstars; newnode->refcnt = 0; /* Insert it into the tree: */ if (newchild == NULL) { newchild = newnode; curchild = newnode; } else { curchild->sib = newnode; ++(newnode->refcnt); curchild = newnode; } ++treeSize; } /* OK, we have processed all descendants of the head */ /* If we created any descendants, initialize the head's child pointer and move the head there */ if (newchild != NULL) { head->child = newchild; ++(newchild->refcnt); head = newchild; } else { /* The head state is a dead end. Advance the parent's child pointer and move the head there if anything left, otherwise revert to the parent's next sib, etc. */ while (true) { Node* p = head->parent; p->child = head->sib; if (p->child != NULL) ++(p->child->refcnt); if (--(head->refcnt) == 0) release(head); head = p->child; if (head != NULL) break; else { head = p; if (head == root) { head = NULL; break; }}}}} /* OK, made it through all chains */ printf("Completed after %llu chains, pruned %llu.\n\n", nodeCount, pruneCount); /* Calculate a values and dump everything */ int l[MAX_VAL+1]; int numchains[MAX_VAL+1]; int numstarchains[MAX_VAL+1]; int numnonstar[MAX_VAL+1]; l[1] = 0; numchains[1] = 1; numstarchains[1] = 1; numnonstar[1] = 0; for (Int n = 2; n <= MAX_VAL; ++n) { l[n] = MAX_LENGTH + 1; for (int unstars = UNSTAR_LIMIT - 1; unstars >= 0; --unstars) { if (nbest[n][unstars] == 0) continue; if (lbest[n][unstars] < l[n]) { l[n] = lbest[n][unstars]; }} numchains[n] = 0; numstarchains[n] = 0; numnonstar[n] = 0; if (l[n] <= MAX_LENGTH) { printf("%d: %d via", n, l[n]); for (int unstars = UNSTAR_LIMIT - 1; unstars >= 0; --unstars) { if (nbest[n][unstars] == 0) continue; if (lbest[n][unstars] != l[n]) { printf("[%d*@%d=%d ", unstars, lbest[n][unstars], nbest[n][unstars]); } else { printf(" %d*%d ", unstars, nbest[n][unstars]); numchains[n] += nbest[n][unstars]; if (unstars == 0) numstarchains[n] += nbest[n][unstars]; else numnonstar[n] += nbest[n][unstars]; } for (int i = 0; i < nbest[n][unstars] && i < BEST_LIMIT; ++i) { print_set(best[n][unstars][i]); printf(" "); }} printf("\n"); }} printf("\n# b-file for A003313\n1 0\n"); for (Int n = 2; n <= MAX_VAL && l[n] <= MAX_LENGTH; ++n) { printf("%d %d\n", n, l[n]); } printf("# End of b-file\n\n"); printf("\n# b-file for A079300\n1 1\n"); for (Int n = 2; n <= MAX_VAL && l[n] <= MAX_LENGTH; ++n) { printf("%d %d\n", n, numchains[n]); } printf("# End of b-file\n\n"); printf("\n# b-file for A0079301\n1 1\n"); for (Int n = 2; n <= MAX_VAL && l[n] <= MAX_LENGTH; ++n) { printf("%d %d\n", n, numstarchains[n]); } printf("# End of b-file\n\n"); printf("\n# b-file for A0079302\n1 0\n"); for (Int n = 2; n <= MAX_VAL && l[n] <= MAX_LENGTH; ++n) { printf("%d %d\n", n, numnonstar[n]); } printf("# End of b-file\n\n"); return 0; }