Posts Tagged ‘prob4’

Typical – I’m late

May 30, 2009

Here are my solutions from the last set that I never got around to posting:

Problem 3 – I guess I just printed the list and then took the biggest here.


def divisors(n):
  divs = set([1])

  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      divs.add(i)
      divs.add(n/i)

  return divs

def isPrime(n):
  return len(divisors(n)) == 1

divs = list(divisors(600851475143))
divs.sort()
divs.reverse()

for div in divs:
  if isPrime(div):
    print div

Problem 4 –

def isPalidrome(num):
    numstr = str(num)
    for i in range(len(numstr)):
	if numstr[i] != numstr[-i-1]:
	    return False
    return True

i = 999
j = 999
prod = i * j
biggest = 0
big_i = 0
big_j = 0

while prod > biggest:
    while prod > biggest:
	if isPalidrome(prod):
	    biggest = prod
	    big_i = i
	    big_j = j
	    break
	j -= 1
	prod = i * j
    i -= 1
    j = i
    prod = i * j

print "Biggest is: ", big_i, " x ", big_j, " = ", biggest

Problem 5 – Okay, this one is cheap, but Carolyn and I figured out that it was super easy to just count which divisors you needed, so there wasn’t really much coding to do. 🙂

print 20*19*9*17*4*7*13*11

Problem 6 – Hmm. Don’t see where I put the source to this one, so maybe I skipped it. I’ll post it with the solutions to next (i.e. this) week’s problems.

Cheers.

Advertisements

Problem 4

May 28, 2009

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.

Followup to BiggestPalindrome

May 23, 2009

I found a way to shave my running time down from 5.75 seconds to about 0.1 seconds. Basically, I just eliminated a lot of unnecessary multiplications and palindrome checks.


NotPalindrome[x_] := (y = ToString[x]; y != StringReverse[y]);

BiggestPalindrome[n_] :=
 (x = 1;
 For[i = 10^n - 1, i > 10^(n - 1) - 1, --i,
 For[j = i; m = i*j, j > 10^(n - 1) - 1 && NotPalindrome[m] && m >= x, --j, m = i*j];
 If[m >= x, x = m]];
 x)

It takes about 0.21 seconds to compute the largest palindrome that is the product of two four digit numbers, and about 19.5 seconds to compute the largest palindrome that is the product of two five digit numbers.

BiggestPalindrome

May 22, 2009

Once again, I cheated by using Mathematica instead of one of the two sanctioned computing environments (Python or Sage). To test whether or not a number was a palindrome, I used Mathematica’s built-in abilities to convert an expression into a string, and to reverse the characters in any given string. Here is my code (it is based on an algorithm I remember Eric describing last week):

Palindrome[x_] := (y = ToString[x]; y == StringReverse[y]);

BiggestPalindrome[n_] := (x = 1;
  For[i = 10^n - 1, i > 10^(n - 1) - 1, --i,
   For[j = i, j > 10^(n - 1) - 1, --j, m = i*j;
    If[Palindrome[m] && m >= x, x = m]]]; x)

Typing BiggestPalindrome[n] will give the largest palindrome that is the product of two n-digit numbers.It took Mathematica about 5.75 seconds to compute the solution when n=3. I asked Mathematica to give me the answer for n=4, but I got tired of waiting for it to finish.

I’m sure there must be a way to cut down on the number of loops to go through. If there is, I’m sure somebody else will produce it.