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

i guess we can write

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?

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.

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

}

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

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

}

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

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

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

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.