Project Euler Problem 4

[Philosophe]

Overview
This VI shows how to solve Project Euler Problem #4.

 
Description
Project Euler Problem #4:

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.

More information about Project Euler can be found @ www.projecteuler.net

 
Requirements

• LabVIEW 2013 (or compatible)

Steps to Implement or Execute Code

1. download the problem4.vi and run it

Additional Information or References

 **This document has been updated to meet the current required format for the NI Code Exchange.**

[StaceyG]

(My apologies if it seems like I'm picking on you today.... I was looking through the list of example VIs and your Euler Project solutions were all in a row....)

Since we're looking for the largest of something, It would be faster to run the loops in reverse, from 999 down instead of from 1 up. Then you only need to find the first palindrome and stop there. (And if we want to generalize the solution to the largest palindrome that is the product of two X-digit numbers, we're now talking a significant time and memory improvement.)

I wonder, though, if it wouldn't be more efficient and elegant to start with a computed list of palindromes and test for divisibility, instead of checking if the results of the multiplication is a palindrome. Start with the largest number made from the product of two 3-digit numbers to find our upper limit on the palindrome. Since 999 is the largest 3-digit number, 999x999 or 998001 is the upper limit for our palindrome. The largest palindrome below that is 997799. Next, we only want palindromes that are a product of two 3-digit numbers, and we know we want those 3-digit numbers to be large. So let's start from 999 as our initial divisor and work downwards. The result of dividing our current palindrome by our current divisor will give us results that start small and get bigger with each new divisor. So, we can keep trying until we either get an integer quotient less than 1000 (success), or get a quotient that is larger than 999 (failure). If we fail, we "decrement" our palindrome and start over.

So let's talk about "decrementing" a palindrome. We want to start by decreasing the middle digit(s) until they reach 0. (I say digit(s) because once we generalize this problem, our palindrome may be an odd number of characters (one middle digit) or an even number of characters (two middle digits).) The, decrement the next set of digits, returning the middle one(s) to 9. So... 997799, 996699, 995599, 994499, 993399, 992299, 991199, 990099, 989989, 988889, etc.. If you notice, the first half of our palindrome is a decreasing series of 3-digit numbers: 997, 996, 995, 994, 993, 992, 991, 990, 989, 988, etc., and the other half of the palindrome is the reverse of that 3-digit number. Once we get down to 100001 (well, we should find our solution to the main problem way before that...), we will start over at the largest 5-digit palindrome: 99999. We'd then test on all 5-digit palindromes until we reach 10001, then we'd try the 4-digit palindromes starting with 9999, etc.

So we can generate a list of descending palindromes by counting down from 999 to 100, reversing the digits and concatenating them. Then from 99 to 10 (with 9 to 0 as a middle digit) to make 5-character palindromes, then 99 to 10 to make 4-character palindromes, then 9 to 0 (with 9 to 0 middles) to make 3-character palindromes, etc.