Archive for June, 2013

Problem 8 of PE’s website says:

Find the greatest product of five consecutive digits in the 1000-digit number:

73167176531330624919225119674426574742355349194934\\  96983520312774506326239578318016984801869478851843\\  85861560789112949495459501737958331952853208805511\\  12540698747158523863050715693290963295227443043557\\  66896648950445244523161731856403098711121722383113\\  62229893423380308135336276614282806444486645238749\\  30358907296290491560440772390713810515859307960866\\  70172427121883998797908792274921901699720888093776\\  65727333001053367881220235421809751254540594752243\\  52584907711670556013604839586446706324415722155397\\  53697817977846174064955149290862569321978468622482\\  83972241375657056057490261407972968652414535100474\\  82166370484403199890008895243450658541227588666881\\  16427171479924442928230863465674813919123162824586\\  17866458359124566529476545682848912883142607690042\\  24219022671055626321111109370544217506941658960408\\  07198403850962455444362981230987879927244284909188\\  84580156166097919133875499200524063689912560717606\\  05886116467109405077541002256983155200055935729725\\  71636269561882670428252483600823257530420752963450\\

This problem can only be done by using brute force, so here we go.
I provided a general solution in C. My program waits an entering number from the standard input, and then it performs the task. The user also provides as parameters the number of digits of its entering number and the N consecutive digits he/she wants the program to use (in this case it will be 5), in this right order.

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

void charArrToIntArr (char from[], int to[], int length){

    int i = 0;

    for (i = 0; i < length; i++){
      	to[i] = from[i] - 48;
      	/* "ASCII value of a number" - 48 = "the number itself" */
    }
}

int findLargestProduct (int big_number[], int size, int n_consecutive){
    
    int i = 0, j = 0;
    int product = 1;
    int largest_product = 1;

    while (n_consecutive <= size){
      	for (j = i; j < n_consecutive; j++){
         	product *= big_number[j];
      	}
      	n_consecutive++;
      	if (largest_product <= product){
         	largest_product = product;
      	}
     	product = 1; i++;
    }

    return largest_product;
}

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

    const unsigned int size_max = (unsigned int) atoi (argv[1]);
    int n_consecutive = atoi (argv[2]);

    char * big_number_temp = malloc (size_max * sizeof (char));
    int big_number[size_max];

    int i = 0;
    
    while (!feof (stdin)){
      	scanf ("%c", &big_number_temp[i]);
      	if (!feof (stdin)){	    
         	if (big_number_temp[i] == '\n'){
            	i--;
         	}
            i++;

         	if (i == size_max){
            	fprintf (stderr, "\nWarning: Array's limit reached (at %d).\n", i);
            	break;
         	}
    	}
    } 

    charArrToIntArr (big_number_temp, big_number, i);
    free (big_number_temp);

    printf ("%d\n", findLargestProduct (big_number, i, n_consecutive));

    return 0;
}

Finally,

$ (gcc -Wall -Wconversion prob8.c) && ./a.out 1000 5
# (Ctrl + Shift + v)
40824

The problem 5 of PE’s website says:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

My first impulse was to solve it by brute force, but that was not really challenging (everyone can do a loop), so I found a more elegant way to find the solution by using some basic number theory facts.

The smallest positive number that is evenly divisible by each number of a given set is just the least common multiple (lcm) of all them. You read a bit more here for taking a grasp about what is this.

Let’s be lcm (a, b) and gcd (a, b) the least common multiple and the greatest common divisor (which, as the name says, is the maximum common divisor that a set of numbers have), respectively, of two integers a and b. Then the following assertions are true:

a) For any given set of integers \{n_{1}, ..., n_{m}\}, the lcm of all them can be carried out by the following recursive formula:

lcm = (n_{1}, n_{2}, n_3... , n_{m}) = lcm (...lcm(lcm(n_{1}, n_{2}), n_{3}), ... , n_{m}).

b) lcm (a, b) = \dfrac{ab}{gcd(a, b)}

Keeping that in mind, I wrote out three functions for solving the problem:

One function to compute the gcd of a couple of integers and another one for computing the lcm of a couple of integers too. The third one will compute the lcm of an entire set of numbers (expressed in a C array), and I will use the idea expressed in a). Of course, it’s a recursive function whose base case is exactly the lcm of two integers.

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

long long int gcd (long long int a, long long int b); 
/* Carries out the greatest common divisor of "a" and "b" */

long long int lcm (long long int a, long long int b);
/* Carries out the least common multiple of "a" and "b" */

long long int lcmn (long long int nums[], int card);
/* Carries out the least common multiple of the integers of
the "nums[]" array, whose size is "card". */


long long int gcd (long long int a, long long int b){
	
	long long int result;
	
	if (b == 0LL){
		result = a;
	} else {
		result = gcd (b, a % b);
	}
	
	return result;
}

long long int lcm (long long int a, long long int b){

	long long int leastCommonMultiple = (a*b) / gcd (a, b);

	return leastCommonMultiple;
}

long long int lcmn (long long int nums[], int card){
	
	const int args_required_lcm = 2;
	long long int current_nums[args_required_lcm];
	long long int result;
	int iteration = card;
	
	if (iteration == 2){
		current_nums[0] = nums[0];
		current_nums[1] = nums[1];
	} else {
		current_nums[1] = nums[iteration - 1];
		current_nums[0] = lcmn (nums, iteration - 1);
	}

	result = lcm (current_nums[0], current_nums[1]);

	return result;
}

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

	const int numbers_requested = atoi (argv[1]);
	long long int numbers[numbers_requested];
	int i = 0;

	for (i = 0; i < numbers_requested; i++){
		numbers[i] = i + 1LL;
	}

	printf ("%lld\n", lcmn (numbers, numbers_requested));

	return 0;
}

Time to compile and to run the program:

$ (gcc -Wall -Wconversion prob5.c) && ./a.out 20
232792560

This is the solution.

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;
    int comptador = 0;
 
    while (quocient > 0){
      quocient = quocient / 10;
      comptador++;
    }
 
    return comptador;
}
 
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.