Well, the Ruby script will always be faster, now that it's written :)
But the paper napkin route has some interesting optimizations. Here are some observations:
1. Given a starting upper bound, you can instantly "normalize it" by insisting that it be a mirror of itself. For your example, examining 14678 is the same as examining 14641.
2. We need to account for all the palindromes at N digits plus all the palindromes at N-1 digits, etc. So on the paper napkin, if you start by writing out "14641" then you can, next to it, write out 9999, 999, 99, and 9. For the other "N-digit" values that make up the targeted range.
3. The sum at any range can be determined by examining the "head" of the palindrome: the part that leads to and includes the pivot in the center, if any. We want to know how many times we can decrement this value before it becomes an illegal palindrome head. Since the head we're examining is the most significant half of the value, numerically, we are guaranteed that any decremented value of the head will yield a counterpart on the tail that is within legal range for the bounds we're given. The only thing that can make the decremented value "illegal" is if it begins with zero. That's because we're not allowing numbers like "00300". To us, that would be "300" - not a palindrome.
4. To obtain the count of all N-digit palindromes not exceeding a given number, simply subtract one from the first digit of the head, and add one to the resulting "number. This accounts for the "lost" zero.
Now, as you see, the math becomes pretty darned predictable after the "starting case." In fact, a shorthand for all the "9" cases is this: how many digits in this case? If odd, add 1 to N. The count is 9 * 10^(N/2 - 1). So, for "999999" we have N=6, count = 9 * 10 ^ (3-1) => 900. It's harder looking in math than it is on the napkin. On the napkin just start at the first 9 and add zeroes for each 9 after until you get to the "pivot." 9 x 10 x 10 => 900. What about for 999999999? Should be 9 x 10 x 10 x 10 x 10 => 90000.
Exercise for the reader: can you take the highly predictable math for the "9s" cases and turn them into an equation? Reduce this napkin algorithm to two cases: the "special case" starting palindrome at N digits, and a memorized math trick for all the other digit cases of all-9s.
by Daniel Jalkut — Dec 05
But the paper napkin route has some interesting optimizations. Here are some observations:
1. Given a starting upper bound, you can instantly "normalize it" by insisting that it be a mirror of itself. For your example, examining 14678 is the same as examining 14641.
2. We need to account for all the palindromes at N digits plus all the palindromes at N-1 digits, etc. So on the paper napkin, if you start by writing out "14641" then you can, next to it, write out 9999, 999, 99, and 9. For the other "N-digit" values that make up the targeted range.
3. The sum at any range can be determined by examining the "head" of the palindrome: the part that leads to and includes the pivot in the center, if any. We want to know how many times we can decrement this value before it becomes an illegal palindrome head. Since the head we're examining is the most significant half of the value, numerically, we are guaranteed that any decremented value of the head will yield a counterpart on the tail that is within legal range for the bounds we're given. The only thing that can make the decremented value "illegal" is if it begins with zero. That's because we're not allowing numbers like "00300". To us, that would be "300" - not a palindrome.
4. To obtain the count of all N-digit palindromes not exceeding a given number, simply subtract one from the first digit of the head, and add one to the resulting "number. This accounts for the "lost" zero.
5. Putting this to work on our example:
14641. Head = 146. Count = 046 + 1 => 47.
9999. Head = 99. Count = 89 + 1 => 90.
999. Head = 99. Count = 89 + 1 => 90.
99. Head = 9. Count = 8 + 1 => 9.
9. Head = 9. Count = 8 + 1 => 9.
Total = 47 + 90 + 90 + 9 + 9 => 245.
Now, as you see, the math becomes pretty darned predictable after the "starting case." In fact, a shorthand for all the "9" cases is this: how many digits in this case? If odd, add 1 to N. The count is 9 * 10^(N/2 - 1). So, for "999999" we have N=6, count = 9 * 10 ^ (3-1) => 900. It's harder looking in math than it is on the napkin. On the napkin just start at the first 9 and add zeroes for each 9 after until you get to the "pivot." 9 x 10 x 10 => 900. What about for 999999999? Should be 9 x 10 x 10 x 10 x 10 => 90000.
Exercise for the reader: can you take the highly predictable math for the "9s" cases and turn them into an equation? Reduce this napkin algorithm to two cases: the "special case" starting palindrome at N digits, and a memorized math trick for all the other digit cases of all-9s.