Problem 4

by

The code Chris posted to solve problem 4 loops over the larger factor as its outer loop, and then the smaller factor as its inner loop. I’d like to share a solution that flips this order, and another solution coming at this problem from a different angle.

I haven’t run across a string.reverse in python, so all the solutions below use the following ispali function:

def ispali(n):
    """ determine if input is palindromic, iteratively """
    s=str(n)
    idx=0
    while(idx <= len(s)//2):
        if(s&#91;idx&#93; != s&#91;-1-idx&#93;):
            return False
        idx += 1
    return True
&#91;/sourcecode&#93;

Not that it really matters I guess, but I expect this to be twice as quick as comparing a string with its reverse anyway. You only need to go half way through a string to know if its a palindrome or not. But whatever. While I was thinking about how to write an ispali function, I also came up with the following (which needs an "import types" line)

&#91;sourcecode language="python"&#93;
def ispali(n):
    """ determine if input is palindromic, recursively """
    return type(n)==types.IntType and ispali_rec(str(n)) \
         or type(n)==types.StringType and \
            (len(n) < 2 or n&#91;0&#93;==n&#91;-1&#93; and ispali_rec(n&#91;1:-1&#93;))
&#91;/sourcecode&#93;

Recursive functions, FTW! I guess there's not much point in getting it all in one statement (but not one line, that's what the '\'s are for), besides some sort of fun. I was reading <a href="http://diveintopython.org/power_of_introspection/index.html">Chapter 4 of Dive Into Python</a>, and learning about the <a href="http://diveintopython.org/power_of_introspection/built_in_functions.html#d0e8510">type</a> function, and <a href="http://diveintopython.org/power_of_introspection/and_or.html">how 'and' and 'or' work</a> in python (which is interesting, you should check it out) when I started coding this function. (This chapter also inspired me to re-write my performance testing script in python, and make each of my scripts modules... I can say more about this another time if anybody is interested).

So, anyway, on to new solutions for the actual problem. First, flip our nested loops, looping over the smaller factor for the outer loop.


def max_for_pali(smaller, bound):
    """ determine largest n in [smaller,bound] with smaller*n a palindrome

    return a tuple with 1 element, n, if such an n exists
    return an empty tuple if no such n exists
    """
    ret = bound
    while(ret >= smaller):
        if ispali(ret * smaller):
            return (ret,) # tuple of size 1, needs trailing ','
        ret -= 1
    return ()

def solve(digits):
    """ the main solver function """

    # the bounds
    lower_b = 10**(digits - 1) + 1
    upper_b = 10**(digits) - 1

    # the biggest product, and its two factors
    max_pali, sm_fact, lg_fact = 0, 0, 0

    smaller = upper_b
    while(smaller >= lower_b):
        if(smaller * upper_b < max_pali):
            break
        for m in max_for_pali(smaller, upper_b):
            p = m*smaller
            if(p > max_pali):
                max_pali, sm_fact, lg_fact = p, smaller, m
        smaller -= 1

    print "%d*%d=%d" % (sm_fact, lg_fact, max_pali)

I’m amused with the return value of the max_for_pali function, and its use in the main solve function. First of all, you might notice that to define a tuple of length one, you have to include a trailing comma. Otherwise it gets treated as a single object, not a tuple-worth of a objects. Then, in the main solve function, I loop over all solutions returned by max_for_pali – but there’s only ever 0 or 1 solution! I thought this was a kinda fun way to avoid an if(len) sort of statement. Of course, there’s no real call for defining the function max_for_pali anyway, but I like it.

This solution also demonstrates a way to make strings that, if memory serves, has not been used in any post here yet. The ‘%’ operator works on strings, taking a formatting string (on the left) and a tuple (on the right). The motto seems to be that this is like printf in c.

The next solution is a little different, in that its outer loop is looping over the palindromes themselves, and the inner loop is to find the factors. My first thought about this approach was that it wouldn’t be very efficient, so I wasn’t even going to bother with it. But I thought about it some more and decided to code it up, and I’m glad I did.

def make_pali(n):
    """ make a palindrome with leading digits n """
    s = str(n)
    l = len(s)
    for i in xrange(0,l):
        s = s + s[l-1-i]
    return int(s)

def factors(n, d):
    """ try to find a nice factorization of n with d digits per factor """
    i = int(math.sqrt(n))
    j = n//i
    while(j < 10**d and i >= 10**(d-1)): # expect the first test to fail first
        if(i*j == n):
            return [i,j]
        i -= 1
        j = n//i
    return []

def solve(digits):
    """ main function """

    max_pali, prod = 0, []

    pali_head = 10**digits - 1

    while(pali_head >= 10**(digits - 1)):
        max_pali = make_pali(pali_head)
        prod = factors(max_pali, digits)
        if(len(prod)):
            break
        pali_head -= 1

    print "%d*%d=%d" % (prod[0], prod[1], max_pali)

This solution has the advantage of stopping as soon as the answer is found, instead of worrying about if there is another combination of factors that’ll give a larger palindrome than one already found.

While testing these scripts, I noticed some interesting patterns. Here are what the above scripts have given me as the largest palindomic products, based on the number of digits of the two factors:

 1: 3 * 3 = 9
 2: 91 * 99 = 9009
 3: 913 * 993 = 906609
 4: 9901 * 9999 = 99000099
 5: 99681 * 99979 = 9966006699
 6: 999001 * 999999 = 999000000999
 7: 9997647 * 9998017 = 99956644665999
 8: 99990001 * 99999999 = 9999000000009999

This points out a few things. First of all, my second solution, as posted above, actually fails on the first input. That’s because there’s a built-in assumption there that the maximum palindromic product of two n digit numbers will be a 2n digit number. There also seems to be a pattern to the factors, at least for even inputs – the larger factor is a string of 9s. Does that continue? Apparently NOT! Here’s some more values (these took a while – more on performance later):

 9: 999920317 * 999980347 = 999900665566009999
10: 9999986701 * 9999996699 = 99999834000043899999
11: 99999943851 * 99999996349 = 9999994020000204999999

With these values determined, one can go back and make another improvement or two (which we could probably have guessed at the beginning), if we allow ourselves some assumptions. Specifically, we now expect that the biggest palindrome will begin with a 9, and therefore end with a 9. Since we’re looking at its factors, we can rule out any factors that are even, or multiples of 5, since neither of these will ever give a product ending in 9.

Ok, you all know by now that I can’t resist performance comparisons, so here’s a graph:

The tickmarks on the x-axis are for the number of digits of the factors, and the y-axis is actually the logs of the times (in some reasonable scale). “LoopS” refers to the solution whose outer loop is over the smaller factor (my first solution above), and “LoopL” loops over the larger factor in its outer loop (my own implementation of Chris/Eric’s solution). “Factor” is my second solution above, and “FewFactor” has a couple of lines added to Factor to ignore multiples of 2 and 5.

What I find interesting here is that LoopS and LoopL switch back and forth between which is faster. Looking back at how the factors are coming out, this probably seems reasonable.

I couldn’t resist going out to a few more digits (I took it to 11 above), but only with the FewFactor solution, which seemed to be winning out, timewise. Here are the times it took to run for those higher digits:

 7: 7 seconds
 8: 37 seconds
 9: 3671 seconds ~ 1 hour
10: 298 seconds ~ 5 minutes (lots quicker than 9 digits!)
11: 5402 seconds ~ 90 minutes
12: ?

I finally gave up on 12 digits after running for nearly 30 hours.

Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: