Three Years Of Computing Final Report On The Palindrome Quest by John Walker May 25th, 1990 Pick a number. Reverse its digits and add the resulting number to the original number. If the result isn't a palindrome, repeat the process. Do all numbers in base 10 eventually become palindromes through this process? Nobody knows.[1] For example, start with 87. Applying this process, we obtain: 87 + 78 = 165 165 + 561 = 726 726 + 627 = 1353 1353 + 3531 = 4884, a palindrome In order for addition of a digits-reversed number to yield a palindrome, there must be no carries in the addition and hence each pair of digits must sum to 9 or less. Whether all numbers eventually become palindromic under this process is unproved, but all numbers less than 10,000 have been tested. Every one becomes a palindrome in a relatively small number of steps (of the 900 3-digit numbers, 90 are palindromes to start with and 735 of the remainder take less than 5 reversals and additions to yield a palindrome). Except, that is, for 196. This number had been carried through 50,000 reversals and additions by P. C. Leyland, yielding a number of more than 26,000 digits without producing a palindrome. Later, P. Anderton continued the process up to 70,928 digits without encountering a palindrome. On August 12, 1987, I put my Sun 3/260 to work on this problem. A program, pquest.c, performs the reversal and addition of arbitrary precision numbers and checks for a palindrome after each step. The program runs with a nice(15) priority, mopping up all available compute cycles while instantly relinquishing the CPU to normal foreground jobs. (There is no perceptible degradation in system performance when this program is running. You do have to get used to seeing your CPU meter pegged at 100% all the time, however.) The program writes checkpoints to a file every two hours and works in conjunction with a set of shell scripts that restart it from the most recent checkpoint and shut it down with a current checkpoint when the system is being shut down. This allows the process to continue day in and day out without human intervention. For almost three years the process of reversal and addition continued. Last night, at five minutes before midnight, the program printed the message: Stop point reached on pass 2415836. Number contains 1000000 digits. and exited. The built-in endpoint had been reached; after 2,415,836 reversals and additions, 196 had grown to a number of 1,000,000 digits without ever yielding a palindrome. Does it ever produce one? Still, nobody knows. From a probabilistic standpoint, as a number grows to enormous size the likelihood of producing a palindrome on the next step decreases since the odds of a digit pair summing to 10 or more approach certainty in very large numbers. But with infinite repetition of this process...perhaps. I will leave it at a million digits after three years of computing. The program that conducted the Quest is appended to this document. If you'd like to continue the Great Work yourself, please E-mail me for the million-digit result of the original computation so you don't have to repeat the first three years of work. What use is this? Well, none, really, but how useful is the idle loop on YOUR computer? I'm not planning to publish this result because after 3 years of enduring the vicissitudes of a 68020, I wouldn't be confident in the results without re-running them for verification and I'm not about to re-up for another 3 years. Besides, if I wait 2 years, I'll probably have a computer on my desk that can do it in 6 months--it's just like the phenomenon of slowboat interstellar travel: no matter when you leave, by the time you get there the destination is already populated by the descendants of people who left after you and traveled in faster ships built with later technology. All of this raises a question I've been meaning to pose for some time now. Are there useful and/or interesting tasks which can be done in the background on our workstations? In particular, are there tasks which can exploit the latent supercomputer power of the idle cycles on all the Sun workstations on the Ethernet at the office in a collaborative fashion? While these kinds of tasks have traditionally been recreational math record-busting like the 196 Palindrome Quest, I'm particularly interested in potential candidate problems more closely related to the real world such as numerical simulations of the evolution of gravitationally bound systems like globular clusters and models of galaxy formation, numerical solutions of difficult problems in quantum mechanics, and the like. I'd rather go after something like that than mount another hackneyed assault on the largest Mersenne prime. Obviously, all such endeavours are low priority in the human domain as well as the operating system process dispatch queue. Notes ----- [1] This unproven assertion is dependent on the number base chosen. Ronald Sprague has proved that the number 10110 in base 2 never forms a palindrome. References ---------- David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books: London, 1986, pp. 142-143. Source Code (pquest.c) ---------------------- /* Test number palindromic by repeated addition Designed and implemented by John Walker in August 1987. */ #include #include #define STARTNUM 196 /* Starting number of sequence */ #define DIGITS 1200000 #define STOPAT 1000000 #define FALSE 0 #define TRUE 1 #define SIGNAL /* Checkpoint on Control C */ #define NICE /* Run at low priority */ #define CKTIME 7200 /* Auto-checkpoint every 2 hours */ extern char *malloc(); #ifdef TRACE #undef SIGNAL #endif #ifdef SIGNAL #include #endif static unsigned char *dig; /* Digits array */ static int ndig; /* Number of digits currently in array */ static int passes; /* Passes over number */ static int ckreq = FALSE; /* Checkpoint requested flag */ static int termreq = FALSE; /* Termination requested flag */ static FILE *console; /* CPOINT -- Checkpoint execution at current state. Valid only if additive pass is complete. */ static void cpoint() { int i, j; FILE *op; static int ckseq = 0; char tbfr[25]; long clk; struct tm *t; sprintf(tbfr, "%d.ck%d", STARTNUM, passes); ckseq = (ckseq + 1) % 10; op = fopen(tbfr, "w"); fprintf(op, "%d\n", passes); fprintf(op, "%d\n", ndig); j = 0; for (i = ndig - 1; i >= 0; i--) { if (j >= 70) { fprintf(op, "\n"); j = 0; } fprintf(op, "%d", dig[i] & 0xF); j++; } fprintf(op, "\n"); fclose(op); time(&clk); t = localtime(&clk); fprintf(console, "\n%02d:%02d Checkpoint %s pass %d, %d digits.\n", t->tm_hour, t->tm_min, tbfr, passes, ndig); ckreq = FALSE; } #ifdef SIGNAL /* PEEK -- Checkpoint if interrupt signal received. At every checkpoint the timed checkpoint is reset. Thus a manual checkpoint will automatically reschedule the timed checkpoint to that interval after the latest checkpoint. */ static void peek() { ckreq = TRUE; #ifdef CKTIME alarm(CKTIME); /* Reset timed checkpoint */ #endif } /* POKE -- Interrupt signal received to request termination. Set to checkpoint and shut down at the end. */ static void poke() { ckreq = TRUE; termreq = TRUE; } #endif /* MAIN -- Main program */ int main(argc, argv) int argc; char *argv[]; { register unsigned char *fp, *bp; register int i, j; int carry; FILE *op; #ifdef NICE nice(15); /* Switch to background batch priority */ #endif if ((dig = (unsigned char *) malloc(sizeof(unsigned char) * DIGITS)) == NULL) { fprintf(stderr, "Insufficient memory to allocate %d digit array\n", DIGITS); exit(-1); } /* Clear digits array and initialise to original number */ passes = 0; for (i = 0; i < DIGITS; i++) dig[i] = 0; /* If a file name is specified on the call statement, restart from a checkpoint file. */ if (argc > 1) { if ((op = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "Cannot open checkpoint file.\n"); exit(-1); } fscanf(op, "%d", &passes); fscanf(op, "%d", &ndig); for (i = ndig - 1; i >= 0; i--) { while (TRUE) { j = fgetc(op); if (j == EOF) { fprintf(stderr, "Premature end of file in checkpoint file."); exit(-1); } if (j == '\n') continue; if (j < '0' || j > '9') { fprintf(stderr, "Illegal character %c in checkpoint file.", j); exit(-1); } dig[i] = j - '0'; break; } } while (TRUE) { j = fgetc(op); if (j == '\n') continue; if (j == EOF) break; fprintf(stderr, "Extra characters (%c) after end of checkpoint.\n", j); } fclose(op); fprintf(stderr, "\nRestart on pass %d, %d digits.\n", passes, ndig); } else { j = STARTNUM; ndig = 0; while (j) { dig[ndig++] = j % 10; j /= 10; } } if ((console = fopen("/dev/console", "w")) == NULL) console = stderr; #ifdef SIGNAL signal(SIGINT, poke); #endif #ifdef CKTIME signal(SIGALRM, peek); alarm(CKTIME); /* Wind the cat */ #endif /* Main loop */ while (TRUE) { /* Test existing number palindromic */ fp = dig; bp = dig + ndig - 1; i = ndig / 2; while (i > 0) { if (*fp++ != *bp--) break; i--; } if (i == 0) { printf("Number found palindromic on pass %d.\n", passes); printf("Number contains %d digits.\n", ndig); j = 0; for (i = ndig - 1; i >= 0; i--) { if (j >= 70) { printf("\n"); j = 0; } printf("%d", dig[i]); j++; } printf("\n"); op = fopen("pal.succ", "w"); fprintf(op, "%d\n", passes); fprintf(op, "%d\n", ndig); j = 0; for (i = ndig - 1; i >= 0; i--) { if (j >= 70) { fprintf(op, "\n"); j = 0; } fprintf(op, "%d", dig[i]); j++; } fprintf(op, "\n"); fclose(op); break; } #ifdef TRACE printf("Pass %d, %d digits: ", passes, ndig); j = 40; for (i = ndig - 1; i >= 0; i--) { if (j >= 70) { printf("\n"); j = 0; } printf("%d", dig[i]); j++; } printf("\n"); #endif /* Not palindromic. Perform next additive cycle. Note how we accumulate the resulting BCD number in the upper nybble of the 8 bit original number. */ fp = dig; bp = dig + ndig - 1; i = ndig; carry = 0; while (i > 0) { j = (*fp & 0xF) + (*bp-- & 0xF) + carry; *fp++ |= (j % 10) << 4; carry = j / 10; i--; } if (carry > 0) { /* Carry out of high order digit */ *fp = carry << 4; ndig++; } /* Shift the result down into the lower nybble */ fp = dig; i = ndig; while (i--) *fp++ = *fp >> 4; passes++; /* Test if digit array has overflowed. If so, checkpoint the solution. */ if (ndig >= DIGITS) { fprintf(console, "Digit array overflowed on pass %d.\n", passes); fprintf(console, "Number contains %d digits.\n", ndig); cpoint(); break; } if (ndig >= STOPAT) { fprintf(console, "Stop point reached on pass %d.\n", passes); fprintf(console, "Number contains %d digits.\n", ndig); cpoint(); break; } /* If the user has requested a checkpoint, do one. */ if (ckreq) cpoint(); /* If termination is requested, shut down. */ if (termreq) break; } return 0; }