Nested Loop in Python

Question

I'm trying to find the largest palindrome that is the product of two 3-digit numbers. My guest is that the palindrome will have the form abccba, so I will just loop over each digit and stop at the largest number that is the product of two 3-digit numbers.

This piece of code

def hasLargeDivisors(n):
    """
    Function to determine if a number has two divisors
    greater than 99
    """
    d = 999
    while n / d > 99 and n / d < 999 and d > 99:
        if n % d is 0:
            return True
        d-=1

    return False

def compisitePalindrome():
    """
    Function to find the largest palindrome 
    that is the product of 2 three-digit numbers
    """ 
    for a in reversed(xrange(1, 9)):
        for b in reversed(xrange(0, 9)):
            for c in reversed(xrange(0, 9)):
                num = a*100001 + b*10010 + c*1100
                if hasLargeDivisors(num):
                    return num

    return 0

produces 888888 = 962 * 924, which is incorrect.

This code

def hasLargeDivisors(n):
    """
    Function to determine if a number has two divisors
    greater than 99
    """
    d = 999
    while n / d > 99 and n / d < 999 and d > 99:
        if n % d is 0:
            return True
        d-=1

    return False

def compisitePalindrome():
    """
    Function to find the largest palindrome 
    that is the product of 2 three-digit numbers
    """ 
    a = 9
    for b in reversed(xrange(0, 9)):
        for c in reversed(xrange(0, 9)):
            num = a*100001 + b*10010 + c*1100
            if hasLargeDivisors(num):
                return num

    return 0

produces 906609 = 993 * 913, which is correct.

I don't know where I went wrong.

You can highly simplify the algorithm by considering the fact that, any number which is palindrome will be divisible by 11. So, start with highest multiple of 11, which is a multiple of two 3 digits numbers, and then step using -11, in xrange and check whether the number is palindrome or not. — Rohit Jain
– Rohit Jain, Commented Feb 9, 2013 at 9:30
Thanks. I've supplied the answer so they gave me a solution. I'm reading it now and it also suggests what you've mentioned. — Lim H.
– Lim H., Commented Feb 9, 2013 at 9:34

Volatility · Accepted Answer · 2013-02-09 09:19:17Z

4

xrange(1, 9) == (1, 2, 3, 4, 5, 6, 7, 8)

xrange(start, stop, step) generates all numbers from start to (but not including) stop, with a step of step.

xrange(5) == (0, 1, 2, 3, 4)
xrange(1, 5) == (1, 2, 3, 4)
xrange(1, 5, 2) == (1, 3)

You can do xrange(1, 10) to include 9 in the range as well.

edited Feb 9, 2013 at 9:19

answered Feb 9, 2013 at 9:13

Volatility

32.4k11 gold badges84 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lim H. Over a year ago

Thanks. So how can I limit the range from 1 to 9 with xrange()?

Paul Hankin · Accepted Answer · 2013-02-09 09:47:16Z

2

There's only (approximately) half a million pairs of 3-digit numbers, so it's quicker and simpler to test them all.

def palindrome_3products():
    for i in xrange(100, 1000):
        for j in xrange(i, 1000):
            if str(i * j) == str(i * j)[::-1]:
                yield i * j, i, j

print max(palindrome_3products())

answered Feb 9, 2013 at 9:47

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Collectives™ on Stack Overflow

Nested Loop in Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related