The “196 algorithm
” is the process of starting with a positive integer and iteratively:
- reversing its digits,
- adding the reversed number to the previous number, and
- checking for a palindrome (the digits in the sum read the same left-to-right as right-to-left).
Most numbers lead to palindromes fairly quickly, like 235 (235 + 532 = 767), but some take a while (89 takes 24 steps). The process is named after 196 because that is the smallest positive integer not known to lead to a palindrome. The current record
is 375 million digits! By that standard, my achievement of calculating 1000 iterations is positively paltry. But, here ‘tis nonetheless, in all of its 411-digit glory:
(Scroll to the end of this post to see what this number is in words.)
One characteristic of this process is that it’s dependent on the base in which the number is expressed--using another base will give different results. In binary (base 2, digits 0 and 1), it turns out that twenty-two (10110) is the smallest number non known to lead to a palindrome.
What about negative numbers? By using a negative base, all integers can be represented without using a negative sign. For example, in base -10 (negadecimal), the places are not ones, tens, hundreds, thousands, etc., but ones, negative tens, hundreds, negative thousands, etc. So the number 29 in negadecimal is equal to -11 in decimal (2 × -10 + 9 × 1 = -20 + 9 = -11). Using this as starting point:
- 29 negadecimal = -11 decimal
- Reversing, 92 negadecimal = -88 decimal (9 × -10 + 2 × 1)
- Adding gives 1901 negadecimal or -99 decimal
- Reverse (1091 negadecimal, -1089 decimal)
- Add (-1188 decimal, 2992 negadecimal, palindrome!)
In base -10, 29 leads to a palindrome in two iterations.
And why stop there? How about complex numbers? Using certain complex bases allows one to express any complex number with integer real and imaginary parts (Gaussian integer
) as a single unsigned string of digits. For example, base -1+i, (where i2
= -1), works with the digits 0 and 1, like binary. The decimal string “6” can also be expressed in binary as “110.” Interpreting this in base -1+i gives the complex number -1+i. Reversing the string to "011" gives 0+i. Adding yields -1+0i, or "11101." Continuing this process doesn’t seem to lead to a palindrome. After 100 iterations, the binary string is:
which converts to about -3.2119823593426 × 1022
+ 1.10520083032793 × 1023
More fun can be had by using others bases or by subtracting instead of adding. I'll talk more about that another time.
Oh, and here’s the (American) English version of that 411-digit number from above, courtesy of the “Name of a Number
Three hundred fifty three cenquintrigintillion, four hundred sixty six cenquattuortrigintillion, four hundred forty three centretrigintillion, nine hundred twenty four cenduotrigintillion, one hundred thirty six cenuntrigintillion, eight hundred ninety seven centrigintillion, eight hundred fifty eight cennovemvigintillion, three hundred seventy seven cenoctovigintillion, one hundred forty four censeptenvigintillion, twenty nine censexvigintillion, one hundred twenty one cenquinvigintillion, one hundred forty three cenquattuorvigintillion, six hundred twenty eight centrevigintillion, five hundred ninety cenduovigintillion, nine hundred eighty cenunvigintillion, eight hundred thirty four cenvigintillion, one hundred forty cennovemdecillion, eight hundred thirty four cenoctodecillion, four hundred two censeptendecillion, eighty six censexdecillion, one hundred forty five cenquindecillion, forty cenquattuordecillion, five hundred ninety nine centredecillion, two hundred ninety one cenduodecillion, eight hundred thirty two cenundecillion, eight hundred forty five cendecillion, seven hundred nineteen cennovemtillion, thirty four cenoctotillion, nine hundred fifty six censeptentillion, three hundred eighty seven censextillion, one hundred sixty eight cenquintillion, seven hundred ninety five cenquattuortillion, eight hundred centretillion, four hundred sixty three cenduotillion, nine hundred seventy one cenuntillion, five hundred forty five centillion, nine hundred fourteen novemnonagintillion, five hundred forty eight octononagintillion, three hundred twenty six septennonagintillion, six hundred seventy six sexnonagintillion, four hundred twenty eight quinnonagintillion, three hundred seventy eight quattuornonagintillion, twenty eight trenonagintillion, eight hundred fourteen duononagintillion, seven hundred ten unnonagintillion, six hundred eighty three nonagintillion, one hundred eight novemoctogintillion, five hundred five octooctogintillion, four hundred ninety six septenoctogintillion, four hundred twelve sexoctogintillion, seven hundred thirty three quinoctogintillion, eight hundred eighty three quattuoroctogintillion, six hundred fifty two treoctogintillion, five hundred ninety nine duooctogintillion, three hundred twenty unoctogintillion, eighty two octogintillion, three hundred seventy four novemseptuagintillion, nine hundred thirty four octoseptuagintillion, six hundred twenty septenseptuagintillion, five hundred fifty four sexseptuagintillion, two hundred forty quinseptuagintillion, nine hundred twelve quattuorseptuagintillion, five hundred fifteen treseptuagintillion, seven hundred ninety duoseptuagintillion, one hundred twenty unseptuagintillion, sixteen septuagintillion, six hundred eighty seven novemsexagintillion, six hundred ninety two octosexagintillion, three hundred fifty two septensexagintillion, one hundred ninety seven sexsexagintillion, seven hundred seventy six quinsexagintillion, six hundred twenty one quattuorsexagintillion, ten tresexagintillion, one hundred seven duosexagintillion, four hundred fifteen unsexagintillion, two hundred twenty sexagintillion, one hundred thirty two novemquinquagintillion, five hundred forty four octoquinquagintillion, twenty six septenquinquagintillion, four hundred thirty nine sexquinquagintillion, five hundred eighty two quinquinquagintillion, two hundred eighty nine quattuorquinquagintillion, nine hundred fourteen trequinquagintillion, six duoquinquagintillion, two hundred forty six unquinquagintillion, four hundred seventy seven quinquagintillion, four hundred thirty seven novemquadragintillion, three hundred thirteen octoquadragintillion, six hundred five septenquadragintillion, four hundred ninety four sexquadragintillion, nine hundred quinquadragintillion, three hundred eighty seven quattuorquadragintillion, one hundred seventeen trequadragintillion, three hundred eighteen duoquadragintillion, seven hundred thirty unquadragintillion, eight hundred eighty three quadragintillion, eight hundred twenty four novemtrigintillion, six hundred seventy five octotrigintillion, five hundred twenty four septentrigintillion, eight hundred thirty six sextrigintillion, four hundred nine quintrigintillion, six hundred fifty five quattuortrigintillion, sixty nine tretrigintillion, four hundred seventy four duotrigintillion, eight untrigintillion, five hundred eighty six trigintillion, nine hundred seventy novemvigintillion, six hundred ninety three octovigintillion, five hundred fifty nine septenvigintillion, four hundred forty one sexvigintillion, eight hundred seventeen quinvigintillion, four hundred forty nine quattuorvigintillion, three hundred thirty eight trevigintillion, eighty two duovigintillion, nine hundred ninety five unvigintillion, one hundred fifty vigintillion, four hundred forty two novemdecillion, five hundred eighty one octodecillion, one hundred ninety four septendecillion, five hundred thirty seven sexdecillion, nine hundred forty two quindecillion, three hundred twenty nine quattuordecillion, seventy nine tredecillion, one hundred five duodecillion, eight hundred twenty six undecillion, four hundred forty one decillion, twelve nonillion, thirty octillion, three hundred forty two septillion, seven hundred seventy two sextillion, eight hundred fifty eight quintillion, seven hundred eighty eight quadrillion, seven hundred forty trillion, four hundred twenty nine billion, three hundred thirty four million, six hundred sixty four thousand, four hundred fifty two.