Euler problem number #4

Question

Using Python, I am trying to solve problem #4 of the Project Euler problems. Can someone please tell me what I am doing incorrectly? The problem is to Find the largest palindrome made from the product of two 3-digit numbers. Here is what I have thus far.

import math

def main(): 
    for z in range(100, 1000):
        for y in range(100, 1000):
            for x in range(1, 1000000):
                x = str(x)
                if x == x[::-1] and x == z*y:
                    print x 

if __name__ == '__main__':
    main()

Answer 1

Some efficiency issues:

1. start at the top (since we can use this in skipping a lot of calculations)
2. don't double-calculate

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

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        for y in xrange(x, 99,-1):  # so we don't double count   
            if x*y < max_seen: continue  # since we're decreasing, 
                                # nothing else in the row can be bigger
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

Answer 2

Try computing x from the product of z and y rather than checking every number from 1 to a million. Think about it: if you were asked to calculate 500*240, which is more efficient - multiplying them, or counting up from 1 until you find the right answer?

Answer 3

Here's some general optimizations to keep in mind. The posted code handles all of this, but these are general rules to learn that might help with future problems:

1) if you've already checked z = 995, y = 990, you don't need to check z = 990, y = 995. Greg Lind handles this properly

2) You calculate the product of z*y and then you run x over a huge range and compare that value to y*z. For instance, you just calculated 900*950, and then you run x from 1000 to 1M and see if x = 900*950. DO you see the problem with this?

3) Also, what happens to the following code? (this is why your code is returning nothing, but you shouldn't be doing this anyway)

x = str(100)
y = 100
print x == y

4) If you figure out (3), you're going to be printing a lot of information there. You need to figure out a way to store the max value, and only return that value at the end.

5) Here's a nice way to time your Euler problems:

if __name__ == "__main__":
    import time
    tStart = time.time()
    print "Answer = " + main()
    print "Run time = " + str(time.time() - tStart)

Answer 4

Wow, this approach improves quite a bit over other implementations on this page, including mine.

Instead of

• walking down the three-digit factors row by row (first do all y for x = 999, then all y for x = 998, etc.),

we

• walk down the diagonals: first do all x, y such that x + y = 999 + 999; then do all x, y such that x + y = 999 + 998; etc.

It's not hard to prove that on each diagonal, the closer x and y are to each other, the higher the product. So we can start from the middle, x = y (or x = y + 1 for odd diagonals) and still do the same short-circuit optimizations as before. And because we can start from the highest diagonals, which are the shortest ones, we are likely to find the highest qualifying palindrome much sooner.

maxFactor = 999
minFactor = 100

def biggest():
    big_x, big_y, max_seen, prod = 0, 0, 0, 0

    for r in xrange(maxFactor, minFactor-1, -1):
        if r * r < max_seen: break

        # Iterate along diagonals ("ribs"):

        # Do rib x + y = r + r
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i, r-i, prod

        # Do rib x + y = r + r - 1
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i - 1)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i,r-i-1, prod

    return big_x, big_y, max_seen

# biggest()
# (993, 913, 906609)

A factor-of-almost-3 improvement

Instead of calling is_palindrome() 6124 times, we now only call it 2228 times. And the total accumulated time has gone from about 23 msec down to about 9!

I'm still wondering if there is a perfectly linear (O(n)) way to generate a list of products of two sets of numbers in descending order. But I'm pretty happy with the above algorithm.

Answer 5

comparing string with an integer in

x == z*y

there are also logical errors

start in reverse order range(999, 99, -1). that'll be more efficient. remove third loop and second comparison altogether.

Answer 6

rather than enumerating all products of 3-digit numbers (~900^2 iterations), enumerate all 6- and 5-digit palyndromes (this takes ~1000 iterations); then for each palyndrome decide whether it can be represented by a product of two 3-digit numbers (if it can't, it should have a 4-digit prime factor, so this is kind of easy to test).

also, you are asking about problem #4, not #3.

Answer 7

This adds a couple of optimizations to @GreggLind's good solution, cutting the run time in half:

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

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        # Optim. 1: Nothing in any row from here on can be bigger.
        if x*x < max_seen: break  

        for y in xrange(x, 99,-1):  # so we don't double count   
            # Optim. 2: break, not continue
            if x*y < max_seen: break  # since we're decreasing, 
                                # nothing else in the row can be bigger

            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

The line

if x*x < max_seen: break

means that once we get to the point where x is less than sqrt of largest palindrome yet seen, not only do we not need to investigate any more factors on that row; we don't even need to investigate any more rows at all, since all remaining rows would start from a number less than the current value of x.

This doesn't reduce the number of times we call is_palindrome(), but it means many fewer iterations of the outer loop. The value of x that it breaks on is 952, so we've eliminated the checking of 853 rows (albeit the "smaller" ones, thanks to the other break).

I also noticed that

if x*y < max_seen: continue

should be

if x*y < max_seen: break

We are trying to short-circuit the whole row, not just the current iteration of the inner loop.

When I ran this script using cProfile, the cumulative time for biggest() was about 56 msec on average, before the optimizations. The optimizations shrank it to about 23 msec. Either optimization alone would deliver most of that improvement, but the first one is slightly more helpful than the second.

Answer 8

Here is a solution that you might consider. It could be far more efficient but only takes a little time to run.

largest = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        c = a * b
        if str(c) == ''.join(reversed(str(c))):
            largest = max(largest, c)
print(largest)

Answer 9

Here is an efficient general solution (~5x faster than others I have seen):

def pgen(factor):
    ''' Generates stream of palindromes smaller than factor**2 
        starting with largest possible palindrome '''
    pmax = str(factor**2)
    half_palindrome = int(pmax[0:len(pmax)/2]) - 1
    for x in xrange(half_palindrome, 0, -1):
        yield int(str(x) + str(x)[::-1])

def biggest(factor):
    ''' Returns largest palindrome and factors '''
    for palindrome in pgen(factor):
        for f1 in xrange(factor/11*11, factor/10, -11):
            f2 = palindrome/f1
            if f2 > factor:
                break
            if f2*f1 == palindrome:
                return palindrome, f1, f2

>>> biggest(99)
(9009, 99, 91)
>>> biggest(999)
(906609, 993, 913)
>>> biggest(9999)
(99000099, 9999, 9901)
>>> biggest(99999)
(9966006699L, 99979, 99681L)
>>> biggest(9999999)
(99956644665999L, 9998017, 9997647L)
>>> biggest(99999999)
(9999000000009999L, 99999999, 99990001L)
>>> biggest(999999999)
(999900665566009999L, 999920317, 999980347L)

Answer 10

The other advice here is great. This code also works. I start with 999 because we know the largest combination possible is 999*999. Not python, but some quickly done pseudo code.

public static int problem4()
    {       
    int biggestSoFar=0;
        for(int i = 999; i>99;i--){
            for(int j=999; j>99;j--){
                if(isPaladrome(i*j))
                   if(i*j>biggestSoFar)
                        biggestSoFar=i*j;
            }
        }
        return biggestSoFar;    
    }

Answer 11

The question states:

What is the largest prime factor of the number 600851475143?

I solved this using C#, but the algorithm itself is language-agnostic.

1. Create a method for determining if a number is prime or not. This can be brute-force (rather than using a much more efficient sieving algorithm) and looks like this:

---

private static long IsPrime(long input)
        {
            if ((input % 2) == 0)
            {
                return 2;
            }
            else if ((input == 1))
            {
                return 1;
            }
            else
            {
                long threshold = (Convert.ToInt64(Math.Sqrt(input)));
                long tryDivide = 3;
                while (tryDivide < threshold)
                {
                    if ((input % tryDivide) == 0)
                    {
                        Console.WriteLine("Found a factor: " + tryDivide);
                        return tryDivide;
                    }
                    tryDivide += 2;
                }
                Console.WriteLine("Found a factor: " + input);
                return -1;
            }
        }

2. Once I have a function to determine primality, I can use this function to find the highest prime factor

---

private static long HighestPrimeFactor(long input)
{
    bool searching = true;
    long highestFactor = 0;
    while (searching)
    {
        long factor = IsPrime(input);
        if (factor != -1)
        {
            theFactors.Add(factor);
            input = input / factor; 
        }
        if (factor == -1)
        {
            theFactors.Add(input);
            highestFactor = theFactors.Max();
            searching = false;
        }
    }
    return highestFactor;
}

I hope this helps without giving too much away.

Answer 12

This code is more efficient. I've also included a print statement to output the time taken for completion.

import time
start_time = time.time()

def palindrome(n):
    if str(n)==str(n)[-1::-1]:
        return True
    else:
        return False
def highestprod(n):
    global x
    x=''
    for i in range (n):
        x+='9'
    x=int(x)
    return x**2

def smallestprod(n):
    global y
    y=''
    for i in range (n):
        y+='1'
    y=int(y)
    return y**2

def lpp(n):  #where n is the no of digits 
    lst=[]
    k=highestprod(n)
    l=smallestprod(n)
    for i in range(k,int(k/1.15),-1):
        if i%10==0:
            pass
        elif palindrome(i):
            lst.append(i)
    val=0
    for m in lst:
        no=int(x)
        while True:
            if no<y:
                break
            elif m%no==0 and x>(m/no)>y and no>y:
                val=m
                break
            else:
                no-=1
        if val:
            break
    print(val)

lpp(3) #<<<==== type here. Can find the answer for n=2,3 and 4 (4 might take 9-10 seconds) but n>4 takes so much time.

print("--- %s seconds ---" % (time.time() - start_time))

Ive tried lpp(5). Took too much time so I killed the program.

Answer 13

If your program is running slow, and you have nested loops like this:

for z in range(100, 1000):
    for y in range(100, 1000):
        for x in range(1, 1000000):

Then a question you should ask yourself is: "How many times will the body of the innermost loop execute?" (the body of your innermost loop is the code that starts with: x = str(x))

In this case, it's easy to figure out. The outer loop will execute 900 times. For each iteration the middle loop will also execute 900 times – that makes 900×900, or 810,000, times. Then, for each of those 810,000 iterations, the inner loop will itself execute 999,999 times. I think I need a long to calculate that:

>>> 900*900*999999
809999190000L

In other words, you're doing your palindrome check almost 810 billion times. If you want to make it into the Project Euler recommended limit of 1 minute per problem, you might want to optimise a little :-) (see David's comment)

Answer 14

This is what I did in Java:

public class Euler0004
{
    //assumes positive int
    static boolean palindrome(int p)
    {
        //if there's only one char, then it's
        //  automagically a palindrome
        if(p < 10)
            return true;

        char[] c = String.valueOf(p).toCharArray();

        //loop over the char array to check that
        //  the chars are an in a palindromic manner
        for(int i = 0; i < c.length / 2; i++)
            if(c[i] != c[c.length-1 - i])
                return false;

        return true;
    }


    public static void main(String args[]) throws Exception
    {
        int num;
        int max = 0;

        //testing all multiples of two 3 digit numbers.
        // we want the biggest palindrome, so we
        // iterate backwards
        for(int i = 999; i > 99; i--)
        {
            // start at j == i, so that we
            //  don't calc 999 * 998 as well as
            //  998 * 999...
            for(int j = i; j > 99; j--)
            {
                num = i*j;

                //if the number we calculate is smaller
                //  than the current max, then it can't
                //  be a solution, so we start again
                if(num < max)
                    break;

                //if the number is a palindrome, and it's
                //  bigger than our previous max, it
                //  could be the answer
                if(palindrome(num) && num > max)
                    max = num;
            }
        }

        //once we've gone over all of the numbers
        //  the number remaining is our answer
        System.out.println(max);

    }
}

Answer 15

Here is my solution:

polindroms = [(x, y, x * y) for x in range(100, 999) for y in range(100, 999) if str(x * y) == str(x * y)[::-1]]
print max(polindroms, key = lambda item : item[2])