## Numeric Palindrome Finder in Ruby

Somebody recently asked me how many palindromes there are between 1 and 10,000. Just for fun, here's a Ruby script to find the answer.*Update:*Well, apparently I was too tired when I did this and I missed the obvious solution: just reverse the string and compare (thanks to Lee N and Jim Freeze). Doh! I'm taking down the original code because it's just silly now. :)

`puts (0..10000).find_all{|n| n.to_s == n.to_s.reverse}.size`

or

`x ="0"; puts x if x == x.reverse until x.succ! == "10000"`

Numeric Palindrome Finder in Ruby

Posted Dec 5, 2005 — 21 comments below

Posted Dec 5, 2005 — 21 comments below

## Carl — Dec 05, 05 587

So,

1 -> 11

2 -> 22

…

99 -> 9999

Those are the first 99 palindromes. Then you have issues where the center number is a pivot.

1->101, 111, 121, … 191. (ten items)

Since the limit is 10,000, the largest number you can get with this method is 9 -> 999.

Then add in numbers 0 through 9.

So, my guess is 99 + 90 + 9 = 198. Was I right?

## Carl — Dec 05, 05 588

## Olivier — Dec 05, 05 589

The interesting question is: for what upper number is the table cloth faster than the ruby script?

:-)

## Scott Stevenson — Dec 05, 05 590

## rob mayoff — Dec 05, 05 591

counter = 0

for n in (0...10000)

counter += 1 if (n.to_s == n.to_s.reverse)

end

puts counter

## Daniel Jalkut — Dec 05, 05 592

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.

## Lee N — Dec 05, 05 593

puts (0..10000).find_all{|n| n.to_s == n.to_s.reverse}.size

## Jim Freeze — Dec 05, 05 594

x ="0"; puts x if x == x.reverse until x.succ! == "100000"

## David — Dec 05, 05 595

while ($i++ < 10000) if ($i == strrev($i)) echo "$i\n";

## Scott Stevenson — Dec 05, 05 596

puts (0..10000).find_all{|n| n.to_s == n.to_s.reverse}.sizeOh wow, that is embarassing. My excuse is that it was 2am when I wrote it. :)

## Daniel Jalkut — Dec 05, 05 597

## Eaten Alive — Dec 06, 05 598

`("0".."10000").find_all{|n| n == n.reverse}.size`

## vasi — Dec 07, 05 600

printf "%d\n", scalar(grep { "$_" eq reverse "$_" } (0..10000));

## vasi — Dec 07, 05 601

length [ n | n <- [0..10000], show n == (reverse $ show n) ]

## Abhi Beckert — Dec 08, 05 602

*grabs fireproof jacket*

## Scott Stevenson — Dec 08, 05 603

## Eaten Alive — Dec 08, 05 604

`while ($i++ < 10000) if ($i == strrev($i)) echo "$i\n";`

Are all variables initialized to 0 in PHP? I don't write in PHP.I would say the Perl version wins the prize for being the most ugly.

## Abhi Beckert — Dec 08, 05 605

## hitoro — Dec 10, 05 606

Can you guess which language I used?

## Eaten Alive — Dec 11, 05 607

## Peter M Jones — Jun 09, 06 1356