1

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

Even though the algorithm is fast enough for the problem at hand, I'd like to know if I missed any obvious optimizations.

from __future__ import division
from math import sqrt

def createPalindrome(m):
    m = str(m) + str(m)[::-1]
    return int(m)

def problem4():
    for x in xrange(999,99,-1):
        a = createPalindrome(x)
        for i in xrange(999,int(sqrt(a)),-1):
            j = a/i
            if (j < 1000) and (j % 1 == 0):
                c = int(i * j)
                return c
Nicolás Siplis
  • 71
  • 3
  • 16

3 Answers3

1

It seems the biggest slowdown in my code is converting an integer to a string, adding its reverse and converting the result back to an integer.

I looked up more information on palindromes and stumbled upon this formula, which allows me to convert a 3-digit number "n" into a 6-digit palindrome "p" (can be adapted for other digits but I'm not concerned about that).

p = 1100*n−990*⌊n/10⌋−99*⌊n/100⌋

My original code runs in about 0.75 ms and the new one takes practically the same amount of time (not to mention the formula would have to be adapted depending on the number of digits "n" has), so I guess there weren't many optimizations left to perform.

Nicolás Siplis
  • 71
  • 3
  • 16
0

Look here for Ideas

In C++ I do it like this:

int euler004()
    {
    // 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.
    const int N=3;
    const int N2=N<<1;
    int min,max,a,b,c,i,j,s[N2],aa=0,bb=0,cc=0;
    for (min=1,a=1;a<N;a++) min*=10; max=(min*10)-1;
    i=-1;
    for (a=max;a>=min;a--)
     for (b=a;b>=min;b--)
        {
        c=a*b; if (c<cc) continue;
        for (j=c,i=0;i<N2;i++) { s[i]=j%10; j/=10; }
        for (i=0,j=N2-1;i<j;i++,j--)
         if (s[i]!=s[j]) { i=-1; break; }
        if (i>=0) { aa=a; bb=b; cc=c; }
        }
    return cc; // cc is the output
    }
  • no need for sqrt ...
  • the subcall to createPalindrome can slow things down due to heap/stack trashing
  • string manipulation m = str(m) + str(m)[::-1] is slow
  • string to int conversion can be faster if you do it your self on fixed size array
  • mine implementation runs around 1.7ms but big portion of that time is the App output and formating (AMD 3.2GHz 32bit app on W7 x64)...

[edit1] implementing your formula

int euler004()
    {
    int i,c,cc,c0,a,b;
    for (cc=0,i=999,c0=1100*i;i>=100;i--,c0-=1100)
        {
        c=c0-(990*int(i/10))-(99*int(i/100));
        for(a=999;a>=300;a--)
         if (c%a==0)
            {
            b=c/a;
            if ((b>=100)&&(b<1000)) { cc=c; i=0; break; }
            }
        }
    return cc;
    }
  • this takes ~0.4 ms

[edit2] further optimizations

//---------------------------------------------------------------------------
int euler004()
    {
    // 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.
    int i0,i1,i2,c0,c1,c,cc=0,a,b,da;
    for (c0=  900009,i0=9;i0>=1;i0--,c0-=100001)    // first digit must be non zero so <1,9>
    for (c1=c0+90090,i1=9;i1>=0;i1--,c1-= 10010)    // all the rest <0,9>
    for (c =c1+ 9900,i2=9;i2>=0;i2--,c -=  1100)    // c is palindrome from 999999 to 100001
     for(a=999;a>=948;a-- )
      if (c%a==0)
        {
        // biggest palindrome is starting with 9
        // so smallest valid result is 900009
        // it is odd and sqrt(900009)=948 so test in range <948,999>
        b=c/a;
        if ((b>=100)&&(b<1000)) { cc=c; i0=0; i1=0; i2=0; break; }
        }
    return cc;
    }
//---------------------------------------------------------------------------
  • this is too fast for me to properly measure the time (raw time is around 0.037 ms)
  • removed the divisions and multiplications from palindrome generation
  • changed the ranges after some numeric analysis and thinking while waiting for bus
  • the first loop can be eliminated (result starts with 9)
Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • 1
    I've never used C++ so I may be wrong here, but aren't you checking several numbers to see if they're palindromes or not? I used `m = str(m) + str(m)[::-1]` to create a palindrome from a 3-digit number, precisely to avoid having to check several non-palindromes. However, since you stated string manipulation is slow I decided to dig a little bit more into palindromes and found this link: http://math.stackexchange.com/questions/97752/generating-numeric-palindromes So, a 3 digit number becomes a 6 digit palindrome with the formula: 1100×n−990×⌊n/10⌋−99×⌊n/100⌋ – Nicolás Siplis Feb 19 '15 at 13:59
  • @NicolásSiplis 1. yes I check all the dot products because it is faster to decide if number is palindrome then check if it is divisible by some 3 digit number. 2. you can use string but do not create it dynamically for each digit, instead create static array and set the digits without reallocations. 3. if you want to use that formula then you are still facing the problem of finding divisor you could speed up it by something like sieves of Erasthostenes but that will need memory and initialization time which for only 6 digit numbers will be likely slower then mine code. – Spektre Feb 20 '15 at 07:24
  • @NicolásSiplis that formula of yours sorts the palindromes so if coded right it is faster (so I was wrong in previous comment bullet 3) added C++ code to my answer. it could be further optimized but I see no point in it (0.4ms from which is around 0.3ms overhead of App output formating) – Spektre Feb 20 '15 at 08:01
  • @NicolásSiplis had an idea while waiting for bus ... after coding the result is 10x faster see edit2 – Spektre Feb 20 '15 at 10:27
0

I wrote this a while back when I just started learning python, but here it is:

for i in range (999, 800, -1):

for j in range (999,800, -1):

    number = i*j
    str_number = str(number)

rev_str_number = str_number[::-1]

if str_number == rev_str_number:

    print("%s a palendrome") % number

I did not check all the numbers you did, but I still got the correct answer. What I really learned in this exercise is the "::" and how it works. You can check that out here.

Good luck with Euler!

Community
  • 1
  • 1
Chef1075
  • 2,614
  • 9
  • 40
  • 57
  • did you try `for j in range(i, 800, -1)`? Otherwise you are checking the same value twice ... – ssm Feb 19 '15 at 08:27
  • I wrote this so long ago, I'm not sure what I tried and what I did not. I just pulled up the old file and posted it. – Chef1075 Feb 19 '15 at 08:28
  • The problem with this solution is that you're checking several numbers that may or may not be palindrome. I decided to just create a palindrome from a given number (999 returns 999999, 998 returns 998899, etc.) and then check if it's evenly divisible by two 3-digit numbers. – Nicolás Siplis Feb 19 '15 at 13:48
  • Agreed. It is not efficient. It was just a way to learn the syntax of python. – Chef1075 Feb 19 '15 at 16:54