Project Euler – Problem 4

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

Posted by Kristian

28 comments

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.

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.

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

Please give me the solution………

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.

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?

Kristian

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.

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.

Can you explain more the code in line 9?

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

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.

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.

Thanks for noticing. It is fixed now.

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?

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.

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

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”);
}

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”);
}

[…] voilà, y’a que deux manières de procéder (n’importe qui vous dira la même chose, MathBlog par exemple) […]

Jean-Marie Hachey

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).

Tegar Percy

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++;
}

Tegar Percy

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";

Harshit Varshney

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

[…] believe the solution (written in C) presented below is more official page here. Please feel free to […]

[…] believe the solution (written in C) presented below is more official page here. Please feel free to […]

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

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;
     }
}

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.

The duc Motorcar

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.

written in MATLAB (2,448ms), first I check if a number is a palindrome, then divide it by all numbers between 100 and 999,
finally it factors out any integers solutions between 100 and 999, if none exists it looks for the next highest palindrome. it also prints the palindrome with its respective factors

clear
x=998001;
while x>0
if int2str(x)==fliplr(int2str(x))
d=(x./(100:1:999)).*(mod((x./(100:1:999)),1)==0);
d=d(d<=999);
d=d(d>=100);
if isempty(d)==0
break
else
x=x-1;
end
else
x=x-1;
end
end
x

Leave a Reply