NumPy Project Euler Problem 4

This entry is part 4 of 9 in the series NumPy Project Euler

Project Euler Problem 4 is a bit silly. It’s about palindromic numbers. I could not find an appropriate algorithm, so I just tried something out. It seems to work OK.

1. Create a 3-digit numbers array

We will create an array to hold 3-digit numbers from 100 to 999 using our favorite NumPy function arange. Check the first and last element of the array with the assert_equal function from the numpy.testing package.

a = numpy.arange(100, 1000)
numpy.testing.assert_equal(100, a[0])
numpy.testing.assert_equal(999, a[-1])

2. Create the products array

Now we will create an array to hold all the possible products of the elements of the 3-digits array with itself. We can accomplish this with the outer function. The resulting array needs to be flattened with ravel, to be able to easily iterate over it. Call the sort method on the array to make sure the array is properly sorted. After that we can do some sanity checks.

numbers = numpy.outer(a, a)
numbers = numpy.ravel(numbers)
numbers.sort()
numpy.testing.assert_equal(810000, len(numbers))
numpy.testing.assert_equal(10000, numbers[0])
numpy.testing.assert_equal(998001, numbers[-1])

3. Find the largest palindromic number

At this point I decided to continue with standard Python. We can probably do something fancy with NumPy, but it looked like reversing string representations of the numbers, and comparing them to the originals would be simpler.

for i in xrange(-1, -1 * len(numbers), -1):
   s = str(numbers[i])
 
   if s == s[::-1]:
      print s
      break

Below is the complete program.

import numpy
import numpy.testing
 
#A palindromic number reads the same both ways.
#The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.
 
#Find the largest palindrome made from the product of two 3-digit numbers.
 
#1. Create  3-digits numbers array
a = numpy.arange(100, 1000)
numpy.testing.assert_equal(100, a[0])
numpy.testing.assert_equal(999, a[-1])
 
#2. Create products array
numbers = numpy.outer(a, a)
numbers = numpy.ravel(numbers)
numbers.sort()
numpy.testing.assert_equal(810000, len(numbers))
numpy.testing.assert_equal(10000, numbers[0])
numpy.testing.assert_equal(998001, numbers[-1])
 
#3. Find largest palindromic number
for i in xrange(-1, -1 * len(numbers), -1):
   s = str(numbers[i])
 
   if s == s[::-1]:
      print s
      break

Have a Go

Although I am pretty sure this is the right solution, it might be a good idea to check the result. Find out which two 3-digit numbers produce our palindromic number by modifying the code a bit. Try implementing the last step in a NumPy way.

 

If you liked this post and are interested in NumPy check out NumPy Beginner’s Guide by yours truly. I would like to make a few announcements. First, I was recently interviewed by floss4science about the book. Second, a gentle reminder that the Christmas NumPy Book Giveaway is going to end this month.

Series NavigationNumPy Project Euler Problem 3NumPy Project Euler Problem 5
By the author of NumPy Beginner's Guide, NumPy Cookbook and Instant Pygame. If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.
Share
This entry was posted in programming and tagged , , , . Bookmark the permalink.