0x0004 - Project Euler 004

Problem:

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.

Solution:

1. Brute Force Approach:

def is_palindrome(n) :
    return str(n) == str(n)[::-1]

largest = 0
for a in range(100, 1000) :
    for b in range(100, 1000) :
        c = a*b
        if is_palindrome(c) and c > largest:
            largest = c
print largest

2. Efficient Approach:

largest = 0
for i in range(999,99,-2) :
    for j in range(i,99,-2) :
        x = i*j
        if x%11==0:
            y = str(x)
            if x > largest and y == y[::-1]:
                largest = x
print largest

Analysis:

The brute-force approach would be to calculate product of pairs of three digit numbers and then find the largest palindrome from them.

In the first program, I’ve made a function is_palindrome, which takes an object (string or numeric) to be checked if it is a palindrome. A simple logic to determine this is to convert the object to string and check if it matches it’s reverse completely. The function str() converts its argument to a string. A sequence, such as a list or string, can be reversed easily in Python by appending [::-1] at the end. This has a syntax [start:stop:step]. So, with no values for start and stop, the default values (first and last indices) are considered. If the value for step is ‘-1’, the sequence is returned in reverse.

Initially a variable largest is given the value 0. Then, we have a nested for loop with limits 100 and 999 each, which give the two three-digit numbers. Within the inner for loop, the product c = a*b is calculated. We then check if this product is a palindrome by passing it as an argument to the is_palindrome function and also if it is larger than the value of largest. If both conditions are satisfied, the value of largest is modified accordingly. At the end, the value of largest is printed to the standard output.

In the efficient program, I have used some facts about palindromes.

• Every even-lengthed palindromic number, having more than or equal to 6 digits, is evenly divisible by 11. Proof : If we have a 6 digit palindrome ABCCBA. Then we can write it as = 100000 x A + 10000 x B + 1000 x C + 100x C + 10 x B + A = 100001 x A + 10010 x B + 1100 x C = 11 ( 9091 x A + 910 x B + 100 x C ) Similarly we can prove for palindromes of other lengths.
• If a palindrome is formed by the products of two numbers, then both factors have to be odd. For e.g., 9009 = 99 x 91.

Thus we can calculate products of only odd factors, and then, before checking whether the product is a palindrome, we can check the divisibility by 11. As we need to find the largest palindrome, we start calculating from 999 to 100 in the outer for loop. Also, we don’t need to start the inner for loop from 999. This is explained as follows: in the first loop, products 999×999, 999×998, 999×997,…999×100 are found. If, for the next loop of i = 998, we calculate j from 999, then we have a repetition since this time we have a term 998×999, and we had 999×998 in the previous loop. Thus, if we start the inner loop (of j) from i to 100, we eliminate all repetitions.

The running time is further reduced by eliminating any function calls. This is possible by placing the code for is_palindrome within the code (in the if statement).

Running times:

The time taken by the brute-force approach using Python 2.7 under Ubuntu 10.10 terminal is 1005.312 milliseconds. Whereas the running time of the efficient approach is 39.523 milliseconds, which is about 3.93% of the time taken by brute-force approach.