Project Euler Problem 4

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Project Euler Problem 4

Postposted on Tue May 25, 2010 6:14 pm

I was doing Problem 4 from projecteuler.net and went beyond the call of duty for palindromic number counting. I did 4 digits, 5 digits and then 6 digits.

Here is my code.

I did a 5 digit one and it took around 9.3 minutes to complete with the above code. I just completed a 6 digit one as well, which took 19 hours, but it had a bug in it (integer multiplication overflow) so it was all for naught.

What are some of your solutions? I'm avoiding duplicates with my jCount variable which cut down considerably on the processing time, but something tells me that there is another way.

Do you guys think that I should start at the highest number possible instead of at the bottom and stop once a palindromic number is found?
Image
Nitrodist
Grand Gerbil Poohbah
 
Posts: 3280
Joined: Wed Jul 19, 2006 1:51 am
Location: Minnesota

Re: Project Euler Problem 4

Postposted on Tue May 25, 2010 8:07 pm

Nitrodist wrote:Do you guys think that I should start at the highest number possible instead of at the bottom and stop once a palindromic number is found?

Why on earth wouldn't you? The way it's set up right now you need to iterate through all possible combinations even if the best one occurs 10% of the way through. Just make sure you decrement each factor alternately.

Couldn't you just use j=i instead of j=digits/10+jCount?

And while I don't know whether it'd be any faster in Java, you ought to be able to do the isPalindrome check via integer arithmetic instead of converting to a string. :D
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Project Euler Problem 4

Postposted on Tue May 25, 2010 8:08 pm

I did this one a while ago when I was working some of the Euler problems. Rather than loop over all pairs of multiples as you did (which grows rather fast), I basically generated all palindromic numbers of the right length in descending order and factored them, stopping with the first match. In Python, the six digit case takes about 90 seconds.

This is the main code:
Code: Select all
def find_pal_pairs(n):
    ql, qh = 10**(n-1), 10**n
    def ndigits(t):
        return t >= ql and t < qh
    for s in genpalinrev(2*n):
        fp = filter(lambda t: ndigits(t[0]) and ndigits(t[1]),
                    getfacpairs(int(s)))
        if fp:
            print fp, s
            break


This is the helper function to generate pairs of factors (sloppily on edge cases, sometimes including redundant pairs). It uses the common optimization that factor pairs are symmetric around roughly the ceiling of the sqrt of N. It doesn't matter if you have extra pairs in the factorization (e.g. (1, 9) and (9, 1)), because the code just tests if the list of pairs is non-empty after filtering:
Code: Select all
def getfacpairs(num):
    return [(n, num / n) for n in xrange(1, int(ceil(sqrt(num)+1))) if not num % n]


The other helper function generates palandromic numbers recursively, again somewhat sloppily (including "numbers" like 00900, but these will be at the end and shouldn't affect the answer):
Code: Select all
def genpalinrev(n):
    if n == 0:
        return ['']
    elif n == 1:
        return [str(d) for d in xrange(9, -1, -1)]
    else:
        l = genpalinrev(n-2)
        return [str(d) + o + str(d) for d in xrange(9, -1, -1) for o in l]


I wonder if there is a better way to generate the palindromes in descending order: a way without keeping the state to do it all at once recursively, but the recursive way is the most straightforward. Something like the cool STL algorithm to generate permutations in lexicographic order without keeping any state besides the last permutation would be great.
bitvector
Grand Gerbil Poohbah
 
Posts: 3234
Joined: Wed Jun 22, 2005 4:39 pm
Location: Mountain View, CA

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 3:42 pm

So, SNM, how does one know that the product of two numbers multiplied together is next in descending order from another in the same sequence?

I took a stab at it a few days ago but didn't get anywhere fast. The problem is that if I do 9*9, 9*8, 8*8, 8*7, as we start to go lower, we start missing numbers. like 9*7.

I drew out a little representation that looks like a triangle on its side starting with 9*9, 9*8, 8*8, etc. to 1 *1 and then filling in the blanks with any products not found with an 9 * 1-7 in the second column and then 8 * 1-6 in the next column, thus progressively getting shorter with each one.

I'm really not sure how to approach this problem. Has this been done before? How about taking something from bitvector's approach with finding similar numbers near that range with the square root?

p.s., I don't know any python bitvector, sorry ;)
Image
Nitrodist
Grand Gerbil Poohbah
 
Posts: 3280
Joined: Wed Jul 19, 2006 1:51 am
Location: Minnesota

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 7:07 pm

Nitrodist wrote:So, SNM, how does one know that the product of two numbers multiplied together is next in descending order from another in the same sequence?

I'm not sure I understand your question.

Of course, I also don't understand the third sentence of my original post, so.... :lol:
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 7:19 pm

Nitrodist wrote:p.s., I don't know any python bitvector, sorry ;)

Should be relatively easy to translate into another language; Python is fairly readable even if you don't use it on a daily basis (the available online reference materials are sufficient to learn the syntax).
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37705
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 8:22 pm

just brew it! wrote:
Nitrodist wrote:p.s., I don't know any python bitvector, sorry ;)

Should be relatively easy to translate into another language; Python is fairly readable even if you don't use it on a daily basis (the available online reference materials are sufficient to learn the syntax).

I'll post a walk-through of it in a bit. The one potentially "tricky" part for people only familiar with mainstream procedural and OO languages is the use of list comprehensions.

SNM wrote:
Nitrodist wrote:So, SNM, how does one know that the product of two numbers multiplied together is next in descending order from another in the same sequence?

I'm not sure I understand your question.

I think he's asking how you iterate over pairs of (x, y) where x*y is strictly decreasing (like a space filling curve over the multiplication table).
Last edited by bitvector on Sat May 29, 2010 8:41 pm, edited 2 times in total.
bitvector
Grand Gerbil Poohbah
 
Posts: 3234
Joined: Wed Jun 22, 2005 4:39 pm
Location: Mountain View, CA

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 8:36 pm

bitvector wrote:The one potentially "tricky" part for people only familiar with mainstream procedural and OO languages is the use of list comprehensions.

Well... that, and the explicit use of indentation for control flow. But that one's pretty easy to get used to, since it merely forces the programmer to indent the code the way it should've been in the first place. :wink:
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37705
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 9:17 pm

just brew it! wrote:
Nitrodist wrote:p.s., I don't know any python bitvector, sorry ;)

Should be relatively easy to translate into another language; Python is fairly readable even if you don't use it on a daily basis (the available online reference materials are sufficient to learn the syntax).


Also, I don't know anything about lambda calculus :D
SNM wrote:
Nitrodist wrote:So, SNM, how does one know that the product of two numbers multiplied together is next in descending order from another in the same sequence?

I'm not sure I understand your question.

Of course, I also don't understand the third sentence of my original post, so.... :lol:


That made me lol :lol:

Yeah, the problem is similar to the reason why I have to find all products in 100-999 * 100-999 because even if you find one at first, there is no way to know it is the highest. When we start at the top, we can't just go 999 * 999-100 and then decrement to 998 * 998-100, stopping at the first palindrome found. Let's say that we find a palindrome at 999 * 100. We don't know for sure that there isn't one at 998 * 998-101 which would be greater than the 999 * 100 solution, so we must iterate through all possible products within 100-999 * 100-999.

even doign it for single digit numbers (1-9 * 1-9) is a headache. Multiplication tables never looked so scary :lol: Perhaps there's something that we can gleam from a multiplication table of 1-9 * 1-9?
Image
Nitrodist
Grand Gerbil Poohbah
 
Posts: 3280
Joined: Wed Jul 19, 2006 1:51 am
Location: Minnesota

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 9:18 pm

bitvector wrote:I did this one a while ago when I was working some of the Euler problems. Rather than loop over all pairs of multiples as you did (which grows rather fast), I basically generated all palindromic numbers of the right length in descending order and factored them, stopping with the first match. In Python, the six digit case takes about 90 seconds.
Okay, so to walk through the code -- as I say here, I generate palindromes in decreasing order and then factor them, stopping with the first that fits the criteria (that has a pair of factors with n digits).

Here, I define find_pal_pairs as the outer function and it takes in the desired number of digits in the factors (e.g. if n=3 you want two 3 digit numbers that multiply to a 6 digit palindrome). Next, I just define a small function that tests whether a number has the correct number of digits. You could do this many ways, including converting to a string and testing the length, but I just do it by seeing if the number is <= 10 taken to the (n-1)th power and < 10 to the nth power.
Code: Select all
def find_pal_pairs(n):
    ql, qh = 10**(n-1), 10**n
    def ndigits(t):
        return t >= ql and t < qh

Next I generate all of the palindromic numbers of length 2*n in descending order as a list and loop over that list in order. In the body of the loop, s is current number (as a string).
Code: Select all
    for s in genpalinrev(2*n):

In the body of the loop, I convert the current palindrome number to a number (int(s)) and then call getfacpairs on that number. That helper function returns pairs of factors of the number stopping at about the square root of the number (since above that point you'll get duplicate entries which are just (y, x) where (x, y) is already in the list). So if you passed it 15, it should return a list with [(1, 15), (3, 5)]. Now here's a part that might seem weird -- the list that getfacpairs returns is passed to filter. Filter takes a function which is used to filter out entries in the list. Basically you give filter a list and you give it a function and it calls the function for every element in the list. When it's done, it returns a list that contains only the elements where the function returned "true." So, if you passed filter a list of words and a function that tested if a string started with a capital letter, you'd get back a list of only the capitalized words. In this case, the function passed to filter tests whether the first and second elements of the pair (e.g. both x and y in (x, y)) have the right number of digits (remember, that's all the ndigits function does).
Code: Select all
        fp = filter(lambda t: ndigits(t[0]) and ndigits(t[1]),
                    getfacpairs(int(s)))

Now, after we call filter, what are we left with? Well we are left with a list of factor pairs (x, y) of the current palindrome where both x and y are the right number of digits. So if the list is non-empty, if it contains any pairs, that means we have found a match: x*y multiply to a palindrome. So in Python "if x" is used to test if a list or collection is non-empty. If the list is non-empty, we've found our result and we print it and stop the loop. Most of the time, when filter is done, the list will be empty because none of the pairs meet the criteria.
Code: Select all
        if fp:
            print fp, s
            break


So now all we have left is the helper functions.

First, the function to generate palandromic numbers of a certain length recursively and in descending order. I did this by simple recursive decomposition: if we need to generate all palindromes of length 0 or 1, it is trivial, and those are our base cases. The list of palindromes with zero digits just contains the empty string. The list of palindromes with one digit is easy too -- just the numbers 0-9 in descending order. The xrange thing says generate all numbers in the range [9, -1) (non-inclusive with -1 and decrement by 1). A more intuitive way of writing this is "reversed(xrange(0, 10))" (e.g. the range [0, 10) reversed).
Code: Select all
def genpalinrev(n):
    if n == 0:
        return ['']
    elif n == 1:
        return [str(d) for d in xrange(9, -1, -1)]

Now the recursive case: if we need to generate palindromes of length N, we can do it by generating all palindromes of length N-2 and then appending two matching characters on each end. So if we have the list ['99', '88', ...] we can make a list of palindromes of length 4 by simply adding matching pairs of digits to each one: ['9999', '9889', ... '8998', ...]. So we loop over all digits 9 to 0 for each entry in the list of palindromes of N-2. So we append 9 to each end of '99', '88', all the way to '00' and then append 8 to each end of '99', '88', etc. gathering the list of all of them.
Code: Select all
    else:
        l = genpalinrev(n-2)
        return [str(d) + o + str(d) for d in xrange(9, -1, -1) for o in l]


Finally, this is the helper function to generate pairs of factors of our number "num". We just loop over all numbers 1 to about the ceiling of the square root of num. For each number i in our loop, we test "if not num % i", which means that i divides into num evenly (the remainder is 0). If the test is true, the pair (i, num / i) is added to the list. So this gives us all of the pairs of factors of num.
Code: Select all
from math import sqrt, ceil

def getfacpairs(num):
    return [(i, num / i) for i in xrange(1, int(ceil(sqrt(num)+1))) if not num % i]


just brew it! wrote:
bitvector wrote:The one potentially "tricky" part for people only familiar with mainstream procedural and OO languages is the use of list comprehensions.

Well... that, and the explicit use of indentation for control flow. But that one's pretty easy to get used to, since it merely forces the programmer to indent the code the way it should've been in the first place. :wink:

Just writing up the explanation of this, I realized there are some other less than obvious Pythonic things here -- decreasing xrange, the use of "if x" to test for empty collections (or "if not x" to test if something is 0), as well as filter and lambda functions (more FP than Python, but still...). It's quite dense, and if you're only used to Blub languages, it could be confounding.
bitvector
Grand Gerbil Poohbah
 
Posts: 3234
Joined: Wed Jun 22, 2005 4:39 pm
Location: Mountain View, CA

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 10:26 pm

Nitrodist wrote:Yeah, the problem is similar to the reason why I have to find all products in 100-999 * 100-999 because even if you find one at first, there is no way to know it is the highest. When we start at the top, we can't just go 999 * 999-100 and then decrement to 998 * 998-100, stopping at the first palindrome found. Let's say that we find a palindrome at 999 * 100. We don't know for sure that there isn't one at 998 * 998-101 which would be greater than the 999 * 100 solution, so we must iterate through all possible products within 100-999 * 100-999.

That's true. But you can know that if you find a palindrome at 998*997 then anything with smaller factors can't be a larger number. So you find a way to butterfly through them all (you can probably find a way to order this so your product is monotonically decreasing, but I"m not sure).

Or, you could do a brute-force approximation, ie, 999*(999 through 900), then 998*(998 through 900), etc.

Just as interesting a problem would be figuring out whether it's faster in the general case to make products and then check for it being a palindrome, or checking for palindromes and then looking for factors. :D
Core i7 920, 3x2GB Corsair DDR3 1600, 80GB X25-M, 1TB WD Caviar Black, MSI X58 Pro-E, Radeon 4890, Cooler Master iGreen 600, Antec P183, opticals
SNM
Emperor Gerbilius I
 
Posts: 6206
Joined: Fri Dec 30, 2005 10:37 am

Re: Project Euler Problem 4

Postposted on Sat May 29, 2010 11:03 pm

Multiplying and checking for factors is an O(n^2) operation in terms of the number of iterations it takes. The check to see if a number if a palindrome is assumed to take O(1) time. Generating all possible palindromes is an O(10^n) operation and integer factorization is slow. Multiplying and checking for factors is theoretically a faster algorithm.

Another approach is to generate two lists by both methods, sort them and take their intersection. You might not need to generate the entire lists to get the answer if you are clever about the order in which you generate the lists.

By the way, It seems to me that there exists some mathematical property of palindromes formed in this matter that you could probably exploit to move from palindrome to palindrome, which would be the elegant solution to this, although the exact nature of that property is something that is immediately obvious to me. Is it possible that figuring that out is an open problem?
Disclaimer: I over-analyze everything, so try not to be offended if I over-analyze something you wrote.
Shining Arcanine
Gerbil Jedi
 
Posts: 1717
Joined: Wed Jun 11, 2003 11:30 am

Re: Project Euler Problem 4

Postposted on Sun May 30, 2010 2:46 am

Shining Arcanine wrote:Multiplying and checking for factors is an O(n^2) operation in terms of the number of iterations it takes. The check to see if a number if a palindrome is assumed to take O(1) time. Generating all possible palindromes is an O(10^n) operation and integer factorization is slow. Multiplying and checking for factors is theoretically a faster algorithm.
But you're mixing terms here -- the "n" you are using in each of the two cases aren't the same. The multiply and check method takes O(n^2) iterations where n is the range of possible n digit numbers, not the number of digits. For example, if you have 3 digits, you have 900 possible 3 digits numbers -- that's exponential in the number of digits. Whereas the "n" in the generating palindromes case is the number of digits. Think about it: for n=3 digits, there are 900*900 possible pairs to multiply, whereas there are 900 total possible palindromes. For n=5 digits, there are 90000*90000 possible pairs and 90000 total possible palindromes. On each iteration, you have to do more work to factor than just to multiply, but doing it in decreasing palindrome order lets you traverse the state space in a much more convenient order. And I'm not sure how you could check if a number is a palindrome in O(1) time.

Here's a way to generate palindromes in reverse order without keeping extra state so you can check them one by one without keeping the state of all of the palindromes or doing all of the generation upfront:
Code: Select all
def genpalinrevgen(n):
    if not n % 2:
        n = n / 2
        for i in reversed(xrange(10**(n-1), 10**n)):
            yield int(str(i) + str(i)[::-1])
    else:
        n = n / 2
        for i in reversed(xrange(10**(n-1), 10**n)):
            for j in reversed(xrange(0, 10)):
                yield int(str(i) + str(j) + str(i)[::-1])

You can see the output by evaluating the generator until it runs out (e.g. [x for x in genpalinrevgen(6)]). In Python [::-1] reverses a string.
bitvector
Grand Gerbil Poohbah
 
Posts: 3234
Joined: Wed Jun 22, 2005 4:39 pm
Location: Mountain View, CA


Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 0 guests