If you precompute the palindromes in the range, store a table of prefix sums, and calculate each of the 10,000 cases in constant time it will probably pass (in

If you precompute the palindromes in the range, store a table of prefix sums, and calculate each of the 10,000 cases in constant time it will probably pass (in ruby). Edit: as electrograv pointed out, another optimization is to generate palindromes from sqrt(start) to sqrt(end) rather than testing each number in the range for palindrome-ness. This saves you a factor of 10^3.5.