## Largest palindrome product (problem 4)

Posted: 18/06/2013 in Project Euler
Tags: , , , ,

I’m actually working out the problems proposed in Project Euler’s website and I thought that it could be useful for many people if I post here my solutions for some of them.

The problem 4 says:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

 

Find the largest palindrome made from the product of two 3-digit numbers.

I just generalized this problem by writing out a modular program, in C, that finds the largest Palindrome for any number of digits given in the command line.

The program may seem larger than necessary, but that’s because I used some general functions I defined a while ago for other purposes, so they work fine with any (valid) input (so at the far end that made me easier to structure the program 🙂 ).

#include <stdio.h>
#include <stdlib.h>

double exponenciar (double base, int exponent);
/* Returns the result of (base ^ exponent) */

int calculaXifres (int n);
/* Returns the number of digits of the number "n". */

long int aIntegerstoInteger (long int array_de_integers[],
int longitud);
/* Maps each element of the array of integers
"array_de_integers", of "longitud" elements,
to each digit of an integer, and returns it back.
For instance,

aIntegerstoInteger ({2, 1, 5}, 3)

will return 215. I will only use this function once,
just for making easier the inversion of a number. */

long int invertirNumero (long int num);
/* Returns the number "num" inverted */

long int maxValueNdigits (int num_digits);
/* Returns the maximum value that a number with
"num_digits" digits can reach. For example,
maxValueNdigits (4) would return 9999. */

long int largestPalindrome (int num_digits);
/* Returns the answer of this problem when
num_digits = 3. */

double exponenciar (double base, int exponent){

double retorna;

if (exponent == 0){
retorna = 1;
} else {
retorna = base * exponenciar (base, exponent - 1);
}

return retorna;
}

int calculaXifres (int n){

int quocient = n;

while (quocient > 0){
quocient = quocient / 10;
}

}

long int aIntegerstoInteger (long int array_de_integers[],
int longitud){

int num_elements = longitud;
int i = 0;
long int integer = 0;

for (i = 0; i < num_elements; i++){
integer += array_de_integers[i] *
(int) exponenciar (10, num_elements - (i + 1));
}

return integer;
}

long int invertirNumero (long int num){

int longitud = calculaXifres (num);
long int num_invertit[longitud];
long int numero_invertit;
int i = 0;

for (i = 0; i < longitud; i++){
num_invertit[i] = num % 10;
num = num / 10;
}

numero_invertit = aIntegerstoInteger (num_invertit, longitud);

return numero_invertit;
}

long int maxValueNdigits (int num_digits){

int i = 0;
long int max_value = 0;

for (i = 0; i < num_digits; i++){
max_value = max_value + (int) exponenciar (10, i);
}

max_value = 9*max_value;

return max_value;
}

long int largestPalindrome (int num_digits){

long int starting = (long int) exponenciar (10, num_digits - 1);
long int ending = maxValueNdigits(num_digits);
long int i = starting;
long int j = i;
long int largest_palindrome = 0L;

for (i = starting; i <= ending; i++){
for (j = starting; j <= ending; j++){
if (i * j == invertirNumero (i * j) &&
i * j >= largest_palindrome){
largest_palindrome = i * j;
}
}
}

return largest_palindrome;
}

int main (int argc, char *argv[]){

int num_digits = atoi (argv[1]);

printf ("%ld\n", largestPalindrome (num_digits));

return 0;
}


Time to compile and to execute the program:

\$ (gcc -Wall -Wconversion prob4.c) && ./a.out 3 906609

And the three-digit factors are 993 and 913, it is to say, $993 \times 913 = 906609$.