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

I removed my solution to pastebin so my crappy solution isn't immediatly visible... http://pastebin.com/f107ef4e0

EDIT: Looking back at this now, I'm kinda ashamed =P.

EDIT 2: I'll actually try to address your question...

You don't have to do the x iteration at all. You can simply compute x as y * z. That will then print out all of the palindromes. Then you need to pick out the largest.

Good luck!

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

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 4

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;
            }
        }

1. 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 5

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 6

I will assume you actually mean Euler #4:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

See my discussion solution in C# here. This may point you in the right direction for a Python implementation.

Answer 7

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 8

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 9

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 10

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 11

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;    
    }