Project Euler – Problem 4

Written by on 16 October 2010

Topics: Project Euler

Today it is time to look at the solution to Problem 4 of Project Euler. It differs a bit in the nature of the problem from the first 3 we have looked at so far. However, it is still mathematics and a solution can still be coded, and most important it is still fun.

The problem formulation reads:

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.

I think it is a nice recreational little exercise.

Before we jump to finding the answer to the problem I want to share a site with you that I stumbled on called Functional fun. The site also deals with Project Euler problems, but solves them using Linq, rather than plain C#.

Solution strategies

For this exercise I briefly discuss two different solution strategies, but only present you with one solution. We need to find a palindrome which is the product of two 3-digit numbers. And that we can approach from two different angles.

a) We can start multiplying 3-digit numbers and then check if the result is a palindrome.

b) We can make palindromes and see if we can find to 3-digit numbers which are the factor pair we are looking for.

My quick calculations shows me that both approaches has the same amount of possible checks to make to find the palindrome.

Solution b

I will pursue solution strategy b, as that is the first I thought of.

if we we square 999, we will have the largest possible number we can as a product of two 3-digit numbers. 999 * 999 = 998001. The largest palindrome which can be made which is less than that must be 997799. The smallest possible palindrome we can encounter is 11111. Under the assumption that we will only have to deal with even digit palindromes a helper function for constructing palindromes is fairly simple.

I cheated a bit and made the palindromes with string manipulation like this:

private int makePalindrome(int firstHalf) {
    char[] reversed = firstHalf.ToString().Reverse().ToArray();
    return Convert.ToInt32(firstHalf + new string(reversed));
}

Once we have obtained a palindrome number (p), we need to check if a factor pair (i, j) of 3-digit numbers exists. In Problem 3, we established that i in such a factor pair must be larger than the square root of the palindrome number, and as a result j must be lower. So we can limit our search for i knowing that we only have to check number between 999 and the square root of the palindrome number. Furthermore we can limit our search by checking that j = p/i < 1000, since it means that the proposed solution no longer consists of two 3-digit numbers, which was one of the requirements.

Now we have derived a set of stopping conditions for the search, all we need to do now, is to check if i is a factor to the palindrome. This can be done with my beloved modulo operator.

bool found = false;
int firstHalf = 998, palin = 0;
int[] factors = new int[2] ;

while (!found) {
    firstHalf--;
    palin = makePalindrome(firstHalf);
    for (int i = 999; i > 99; i--) {
        if ((palin / i) > 999 || i*i < palin) {
            break;
        }

        if ((palin % i == 0)) {
            found = true;
            factors[0] = palin / i;
            factors[1] = i;
            break;
        }
    }
}

Console.WriteLine("Found the palindrom {0}, which is made from {1}*{2}", palin, factors[0], factors[1]);

On line 9 in the code, I check the stop conditions for the search, which we deduced earlier on. And in if clause line 13-18, we check if we have indeed found a factor, and in that case store the result before we end.

With this code I get the result:

Found the palindrom 906609, which is made from 913*993
Solution took 15,625 ms

24 Comments For This Post I'd Love to Hear Yours!

  1. atul says:

    i guess we can write

    for (int i = 999; i * i > palin; i–-)
    

    and removing i*i < palin from if block.

    Checking it till 99 is unnecessary.

  2. Kristian says:

    Hi Atul.

    This is so far back that I hardly remember the problem but looking at your code, you are right. However it wont change anything, since we will break out of the loop as soon as we find a palindrome anyway.

  3. naveed says:

    Q-Input three positive numbers from user. Compute and display the average of the two highest numbers.

    Please give me the solution………

  4. Kristian says:

    This sounds exactly like a homework assignment, so no I wont give you the solution. If you have a question to an almost working solution I could probably give you some feedback. But otherwise no.

  5. Soham says:

    I could not get this point though I have looked at Probelm 3 :

    ” we established that i in such a factor pair must be larger than the square root of the palindrome number, and as a result j must be lower.”

    Why is that so?

  6. Kristian says:

    Because if both i and j is smaller than the square root of p, then multiplying the two will be smaller than p.

    If both i and j are larger then multiplying the two will be larger than p.

    Therefore only one of i and j can be larger than square root of p.

  7. Soham says:

    Ok. I thought it’s a check for the prime number. If the number is composite then it should have a factor(not necessarily prime) larger than the square root of that number. That’s why we discard the number by checking this.

  8. Randall says:

    Can you explain more the code in line 9?

    if ((palin / i) > 999 || i*i < palin)

  9. Kristian says:

    I am doing it a bit backwards by making all palidromes and then checking if I can find integers i, j such that i*j = palin.

    The line you refer to is two checks.

    the first part (palin/i > 999), means that j would be a four digit or above, and thus this would be true for any i smaller than the current one I am testing and then we can break.

    the second part (i*i < palin) means that we are now below the squareroot of the palindrome and all the checks I have made for i,j will now be made again, but with i=j, and j=i. So no need to continue there either.

  10. Ilya says:

    You have a small typo, spend some time to figure it out (first thought I was mistaken). You have:
    largest possible number we can as a product of two 3-digit
    numbers. 999 * 999 = 9998001
    you probably meant 998001 instead of 9998001

    Great tutorials. I’m using F# to implement them, very nice experience.

  11. Kristian says:

    Thanks for noticing. It is fixed now.

  12. Stephen says:
    class Program
    	{
    		static void Main(string[] args)
    		{
    			Stopwatch timer = new Stopwatch();
    			timer.Start();
    
    			int num1 = 0;
    			int num2 = 0;
    			int answer = 0;
    
    			for (num1 = 100; num1 < 1000; num1++)
    			{
    				for (num2 = 100; num2 < 1000; num2++)
    				{
    					int x = num1 * num2;
    
    					if (isPalindrome(x))
    					{
    						if (x > answer)
    						{
    							answer = x;
    						}
    					}
    				}
    			}
    
    			timer.Stop();
    			Console.WriteLine("Answer: {0} which is made from {1}, and {2}\n\nIt took {3} seconds to find the answer.", answer, num1, num2, timer.Elapsed.ToString("ss\\.ff")); //Why are num1 and num2 showing up incorrectly?
    			Console.ReadLine();
    		}
    
    		private static bool isPalindrome(int x)
    		{
    			int n = x;
    			int rev = 0;
    			int digit = 0;
    			while (n > 0)
    			{
    				digit = n % 10;
    				rev = rev * 10 + digit;
    				n = n / 10;
    
    				if (n == rev)
    				{
    					return true;
    				}
    			}
    			return false;
    		}
    	}

    I am getting the right answer, however, when my console writes my answer out, why are my num1 and num2 values incorrect?

  13. chi says:

    Small typo, not significant, but you say:
    The smallest possible palindrome we can encounter is 11111.

    If the smallest product is 100*100 = 10000, then the smallest possible palindrome is 10001.

  14. chi says:

    unless you are already considering palindromes that can be factored into two 3 digit numbers, then i guess my point is moot. disregard 🙂 great walkthroughs btw. only once has my solution been the same, so it’s a nice way to look at a different angle

  15. Lorenzo says:

    I have done this way!!

    #include
    #include

    int identf3digt(int i)
    {
    int r, t=2, z;
    for(r=100;r=100 && z<=999))
    {
    t=1;
    break;
    }

    }
    if(t==2)
    return 0;
    return 1;
    }

    main(){
    int i, r, z, t, f, g, v, maior;
    maior=1;
    for(i=10000;i<=998001;i++)
    {
    if(i<100000)
    {
    r=i/10000;
    z=(i%10000)/1000;
    t=((i%10000)%1000)/100;
    f=(((i%10000)%1000)%100)/10;
    g=((((i%10000)%1000)%100)%10);
    }
    else
    {
    r=i/100000;
    z=(i%100000)/10000;
    t=((i%100000)%10000)/1000;
    f=(((i%100000)%10000)%1000)/100;
    g=((((i%100000)%10000)%1000)%100)/10;
    v=(((((i%100000)%10000)%1000)%100)%10);
    }

    if(imaior)
    if(identf3digt(i)==1)
    maior=i;

    if(i>=100000)
    if(r==v && z==g && t==f)
    if(i>maior)
    if(identf3digt(i)==1)
    maior=i;

    }
    printf(“%d”,maior);
    printf(“\n\n”);
    system(“pause”);
    }

  16. Lorenzo says:

    again!!
    #include
    #include

    int identf3digt(int i)
    {
    int r, t=2, z;
    for(r=100;r=100 && z<=999))
    {
    t=1;
    break;
    }

    }
    if(t==2)
    return 0;
    return 1;
    }

    main(){
    int i, r, z, t, f, g, v, maior;
    maior=1;
    for(i=10000;i<=998001;i++)
    {
    if(i<100000)
    {
    r=i/10000;
    z=(i%10000)/1000;
    t=((i%10000)%1000)/100;
    f=(((i%10000)%1000)%100)/10;
    g=((((i%10000)%1000)%100)%10);
    }
    else
    {
    r=i/100000;
    z=(i%100000)/10000;
    t=((i%100000)%10000)/1000;
    f=(((i%100000)%10000)%1000)/100;
    g=((((i%100000)%10000)%1000)%100)/10;
    v=(((((i%100000)%10000)%1000)%100)%10);
    }

    if(imaior)
    if(identf3digt(i)==1)
    maior=i;

    if(i>=100000)
    if(r==v && z==g && t==f)
    if(i>maior)
    if(identf3digt(i)==1)
    maior=i;

    }
    printf(“%d”,maior);
    printf(“\n\n”);
    system(“pause”);
    }

  17. Jean-Marie Hachey says:

    Table 1
    Largest palindrome product of two factors of equal length (2 to 10 digits)

    Palindromes in Table 1 are divisible by 11 and, therefore, contain an even number of digits.

    http://img11.hostingpics.net/pics/300342pe4palindromestable1.jpg

    ___

    Sources:
    1) Project Euler 4: Find the largest palindrome product
    http://blog.dreamshire.com/2009/05/17/project-euler-problem-4-solution/
    2) Prime Factorization Calculator
    http://www.mathblog.dk/tools/prime-factorization/
    3) Javascripter.net
    http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
    4) Palindromic prime
    http://en.wikipedia.org/wiki/Palindromic_prime
    (And references cited therein).

  18. Tegar Percy says:

    I Haven’t Figured How to ordered it perfectly yet..
    but it would ordered some numbers, though…
    it also has lesser loop than through the brute force…
    if you can improve it a bit.. please, made me know..
    THIS CODE WAS WRITTEN IN C++

    int x=0,y=0,i=10;
    int count=0;
    while(y=0 && y-x<i)
    {
    int c=(i-x)*(i-(y-x));
    cout<<i-x<<" x "<<i-(y-x)<<" = "<<c<<endl;
    x–;
    count++;
    }
    y++;
    }

  19. Tegar Percy says:

    This is my optimized algorithm for that case..
    but this isn’t ordered after x=i/2+1
    if you find the fix of this algorithm, let me know…

    int x=0,y=0,i=10;
    int count=0;
    while(y=0 && y-x<i)
    {
    int c=(i-x)*(i-(y-x));
    cout<<i-x<<" x "<<i-(y-x)<<" = "<<c<<endl;
    x–;
    count++;
    }
    y++;
    }
    cout<<count<<" loop";

  20. MY algorithm is…
    Consider the digits
    of P – let them be x, y and z. P must be at least 6 digits long since the palindrome 111111 = 143×777 – the product of two 3-digit integers. Since P is
    palindromic:
    P=100000x+10000y+1000z+100z+10y+x

    P=100001x+10010y+1100z

    P=11(9091x+910y+100z)

    Since 11 is prime, at least one of the integers a or b must have a factor of 11.
    So if a is not divisible by 11 then we know b must be. Using this information .we can determine what values of b we check depending on a:

    largestPalindrome = 0
    a = 999
    while a >= 100
    if a mod 11 = 0
    b = 999
    db = 1
    else
    b = 990 //The largest number less than or equal 999
    //and divisible by 11
    db = 11
    while b >= a
    if a*b <= largestPalindrome
    break
    if isPalindrome(a*b)
    largestPalindrome = a*b
    b = b-db
    a = a-1
    output largestPalindrome

  21. Hrishabh says:

    I havent found a better solution to this problem than the link below:

    http://spectre92z.wordpress.com/2014/08/25/eulers-problem-4-the-largest-palindrome-made-from-the-product-of-two-3-digit-numbers/

    Also read the first comment

  22. Matthew R says:

    Implemented a brute force solution in Java and optimized it down to 5ms

    
    int MAX = 999;
    int MIN = 100;
    int answer = 0;
    
    for (int i = MAX; i &gt;= MIN; --i) {
         for (int j = MAX; j &gt;= MIN; --j) {
    	            
              int n = i * j;
    	  if (isPalindrome(n) == true &amp;&amp; n &gt; answer) {
    	       answer = n;
    	  }
    	  // If n is less than the current answer, then break out of loop cause its only getting smaller
    	  else if (n &lt; answer) break;
         }
    }
    
    
  23. Adrian says:

    Brute-force is really disappointing from a mathematical standpoint, isn’t it? It’s not even really worth spending time on since it’s so straight forward to just check every possible combination and return the first found.

  24. It’s in point of fact a great and useful piece of info.
    I am glad that you shared this useful information with us.
    Please stay us up to date like this. Thanks for sharing.

Trackbacks For This Post

  1. Euler, encore une fois! | QySource
  2. Eulers problem 4 : The largest palindrome made from the product of two 3-digit numbers. | Legionesque
  3. Eulers problem 4 : The largest palindrome made from the product of two 3-digit numbers. | spectre92z

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.