“If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is.” ― John von Neumann

### Largest product in a grid (problem 11)

Problem 11 of PE’s website says:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

I provided a general solution in C. My program allocates dynamically any type of matrix, with any size you want, with any length of adjacent numbers you want the program to analize (this is the only extra data you provide as a parameter of the program from the CLI). It also provides some error management (i.e. if both sizes of the grid are less than the length of the adjacent numbers you want to find the product).

My program works this way:

1. Open your command line interpreter and execute the program providing the length of adjacent numbers you want to evaluate. For example, in this problem it is 4, therefore:

$name_of_program 4 2. Now the program is waiting so that the user provides a matrix to the standard input (the program accepts any size!) and press Enter. In order that the program “catches” that you are done, it is to say, that the EOF of stdin is reached, press CTRL-D (but before of this, don’t forget to press Enter, this step is important). 3. It stores the grid in a new (temporal) file. At this point the width (= the amount of numbers of each line) and the height (= the number of lines of the file) of the grid are calculated and a new grid with that right size is created. 4. All the data stored in the file is saved in the grid. 5. All the required calculations inside the grid are performed. 6. The result is printed out on the standard output and the temporal file created by the program is removed from your computer. Here is the C code: #include <stdio.h> #include <stdlib.h> int **newGrid (unsigned int rows, unsigned int columns); /* It returns a pointer to a 2D (rows x columns) matrix. */ void freeGrid (int **grid, unsigned int columns); /* It frees the memory used for grid. */ void recordStdinToFileOpen (FILE * file); /* Entering user's input is stored in a (temporal) file. */ unsigned int countElementsForGrid (FILE * file, int index_of_array); /* After the grid is saved in a file, this function returns the width and the height of the matrix, depending on whether the value of the "index_of_array" argument is 0 or 1, respectively. */ void recordFileOpenToGrid (FILE * from_file, int **grid, unsigned int width, unsigned int height); /* This functions enters the file we are using to allocate dinamically the data and save it in a grid whose size has been previously calculated. */ unsigned long int getLargestProduct (int **grid, unsigned int width, unsigned int height, unsigned int adjacent); /* This function carries out the largest product of any "adjacent" length of adjacent numbers of the "grid" argument, whose size is "width"x"height", and returns the result. For this problem in particular, adjacent = 4, height = 20, width = 20. */ unsigned long int doTheStuff (FILE * file, unsigned int adjacent); /* It gathers all the functions above and returns the return value of the getLargestProduct() function. */ unsigned long int openFileForGrid (unsigned int adjacent); /* It opens a temporal file, does all the stuff described above, and returns the result of doTheSuff() function. When all the work is done, it removes physically that temporal file of your computer. */ int **newGrid (unsigned int rows, unsigned int columns){ int **grid = NULL; unsigned int j = 0; grid = (int **) malloc (columns * sizeof (int *)); for (j = 0; j < columns; j++){ grid[j] = (int *) malloc (rows * sizeof (int)); } return grid; } void freeGrid (int **grid, unsigned int columns){ int j = 0; for (j = 0; j < columns; j++){ free (grid[j]); } free (grid); } void recordStdinToFileOpen (FILE * file){ int num; fseek (file, 0L, SEEK_SET); while (!feof (stdin)){ fscanf (stdin, "%d", &num); if (!feof (stdin)){ fprintf (file, "%d ", num); if (getchar () == '\n'){ fprintf (file, "\n"); } } } } unsigned int countElementsForGrid (FILE * file, int index_of_array){ unsigned int result = 0; unsigned int i = 0, j = 0; /* During the execution time, press Enter after you paste your grid */ unsigned int measures[2] = {i, j}; int first_line_done = 0; int c; fseek (file, 0L, SEEK_SET); while ((c = fgetc (file)) != EOF){ if ((c == ' ') && first_line_done == 0){ i++; } if (c == '\n'){ j++; first_line_done = 1; } else { continue; } } measures[0] = i; measures[1] = j; result = measures[index_of_array]; return result; } void recordFileOpenToGrid (FILE * from_file, int **grid, unsigned int width, unsigned int height){ int i = 0, j = 0; fseek (from_file, 0L, SEEK_SET); for (j = 0; j < height; j++){ for (i = 0; i < width; i++){ fscanf (from_file, "%d", &grid[j][i]); } } } unsigned long int getLargestProduct (int **grid, unsigned int width, unsigned int height, unsigned int adjacent){ unsigned long int result = 1L; unsigned long int i = 0L, j = 0L, i_temp = i, j_temp = j; unsigned long int max = 1L; for (j = 0L; j < height; j++){ for (i = 0L; i < width; i++){ i_temp = i; j_temp = j; if (width - i_temp >= adjacent){ /* Move left-to-right (horitzontally) */ for (i_temp = i; i_temp < adjacent + i; i_temp++){ result *= (unsigned int) grid[j][i_temp]; } if (result >= max) max = result; result = 1L; } if (height - j >= adjacent){ /* Move up-to-down (vertically) */ for (j_temp = j; j_temp < adjacent + j; j_temp++){ result *= (unsigned int) grid[j_temp][i]; } if (result >= max) max = result; result = 1L; } if ((height - j >= adjacent) && (width - i_temp >= adjacent)){ /* Move up-to-down diagonally (\) */ for (j_temp = j, i_temp = i; (j_temp < adjacent + j) && (i_temp < adjacent + i); j_temp++, i_temp++){ result *= (unsigned int) grid[j_temp][i_temp]; } if (result >= max) max = result; result = 1L; } if ((height - j >= adjacent) && (i_temp >= adjacent - 1)){ /* Move up-to-down diagonally (/) */ for (j_temp = j, i_temp = i; (j_temp < adjacent + j) && (i_temp + 1 > i - adjacent + 1); j_temp++, i_temp--){ result *= (unsigned int) grid [j_temp][i_temp]; } if (result >= max) max = result; result = 1L; } } } result = max; return result; } unsigned long int doTheStuff (FILE * file, unsigned int adjacent){ unsigned long int result = 1; unsigned int width = 0, height = 0; int **grid; recordStdinToFileOpen (file); width = countElementsForGrid (file, 0); height = countElementsForGrid (file, 1); if ((adjacent > width) && (adjacent > height)){ fprintf (stderr, "Error: the parameter must be equal or less than, at least, one side of the grid.\n"); exit (1); } grid = newGrid (width, height); recordFileOpenToGrid (file, grid, width, height); result = getLargestProduct (grid, width, height, adjacent); freeGrid (grid, height); return result; } unsigned long int openFileForGrid (unsigned int adjacent){ unsigned long int escape = 0L; FILE * temp_file; temp_file = fopen ("temp.txt", "w+"); if (temp_file != NULL){ escape = doTheStuff (temp_file, adjacent); } else{ fprintf (stderr, "Error: There were a problem when opening a new file.\n"); exit (1); } fclose (temp_file); system ("rm -r temp.txt"); /* Windows users: replace "rm -r temp.txt" by "DEL temp.txt". */ return escape; } int main (int argc, char *argv[]){ char * endptr; const unsigned int adjacent = (unsigned int) strtol (argv[1], &endptr, 10); unsigned long int result; if (argc < 2 || (int) adjacent <= 0){ fprintf (stderr, "Error: A positive integer as parameter is required.\n"); exit (1); } result = openFileForGrid (adjacent); fprintf (stdout, "\n%lu\n", result); return 0; }  I’m going to show you some examples of its use: $ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 2
1 2
3 4

12
$(gcc -Wall -Wconversion -g prob11.c) && ./a.out 3 1 2 9 1 8 4 9 3 3 7 7 7 648$ (gcc -Wall -Wconversion -g prob11.c) && ./a.out 2
1 6 7 2 3

42


$(gcc -Wall -Wconversion -g prob11.c) && ./a.out 5 3 5 5 3 Error: the parameter must be equal or less than, at least, one side of the grid.   $ (gcc -Wall -Wconversion -g prob11.c) && ./a.out -1 Error: A positive integer as parameter is required.

In particular, for this problem:

$(gcc -Wall -Wconversion -g prob11.c) && ./a.out 4 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 70600674  This is the requested answer. ### Some notes about dynamic memory allocation of multi-dimensional arrays (Note: In this post I’m assuming that you know what arrays and pointers are and that you already feel confortable working with them.) Many programming languages such as Pascal have multi-dimensional arrays support. That is, data stored in this kind of arrays can be accessed by indicating its position in the same way we would indicate the position of a point in a geometric space, it is to say, through a $[x_{1}, ..., x_{n}]$ notation, being $n$ the number of dimensions of the space (and, analogically, the number of dimensions of the array we are working in). The point is that, despite ANSI C specification says so (section 6.5.2.1, point 3), C language doesn’t really have multi-dimensional arrays support. Instead, it uses an array-of-arrays approach; we don’t access to an array element by just separating the indices by commas, but accessing at first one array, then accessing to a second one, which is situated in a particular index, and so on until we get to the desired element of data. In this case we use the notation $[x_1]...[x_n]$. A picture is worth a thousand words, so let’s see graphically how can we represent a data retrieval in a 2D-array: In this case we have a 5×4 matrix of chararacters in which we want to retrieve the character ‘h’. In this image C defines an array of columns, a, which has five columns, a[0], a[1], a[2], a[3] and a[4]. For each column we have four rows: it is to say, each column is an array as well. For example, for the first column, a[0], we have the elements (rows) a[0][0], a[0][1], a[0][2] and a[0][3]. In particular, the character ‘h’ is allocated in the second element of the array a[2], it is to say, in a[2][1]. The malloc() and free() functions You need to keep in mind the C’s approach for representing multi-dimensional arrays so that you can understand how the malloc() function works when allocating dynamically memory for multi-dimensional arrays. The prototype of malloc() function is void *malloc(size_t size); It allocates a block of memory (specifically size_t bytes) on the heap and it returns a pointer to the allocated memory. On error, this function returns NULL. In order to avoid memory leaks during the execution-time of our C programs we have to free all the memory blocks we are not going to use for increasing the perfomance of our programs and even for having always available memory enough for successful calls to malloc(). Fortunately C standard library incorporates a function called free(), whose prototype is void free(void *ptr); The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(). It has no return value. Here’s a very straightforward example of a program that right after allocating dynamically a new 1D-array it frees it: #include <stdio.h> #include <stdlib.h> int main (void){ int * blocks_of_data; int number_of_elements = 4; blocks_of_data = (int *) malloc (number_of_elements * sizeof (int)); free (blocks_of_data); return 0; }  I will compile and execute this program using Valgrind, which is a tool for Linux that, among other things, helps to detect memory leaks. This is the output I get after the execution-time: This is a successful result, because it says there are no memory leaks in the program. But let’s remove now the free() function of the previous code and let’s repeat the same step of above to see the new results of Valgrind’s diagnose. It is to say, the result of compiling and executing the program #include <stdio.h> #include <stdlib.h> int main (void){ int * blocks_of_data; int number_of_elements = 4; blocks_of_data = (int *) malloc (number_of_elements * sizeof (int)); /* Now the "free (blocks_of_data)" is missing here. */ return 0; }  is We have lost 16 bytes (the four integer blocks we reserved through the variable number_of_elements = 4 multiplied by the size of every block of data of integer type, which is four bytes too per block). This time the memory leak was very little, only 16 bytes, but it’s really important to not forget to use the free() function for every malloc() call, specially in serious programs where there is a more significant amount of data management, because although you will recover all the memory lost after the execution-time of the program, problems may arise before, for example because of your system’s memory fragmentation. Let’s now see how to allocate dynamically a 2D-array in two different ways: the more straightforward but less efficient one, and the not so obvious but more efficient second one. Take a look at the following piece of code: #include <stdio.h> #include <stdlib.h> int main (void){ int j = 0; int rows = 4, columns = 5; int **grid = NULL; /* Allocating the matrix */ grid = (int **) malloc (columns * sizeof (int *)); for (j = 0; j < columns; j++){ grid[j] = (int *) malloc (rows * sizeof (int)); } /* Time to free the matrix */ for (j = 0; j < columns; j++){ free (grid[j]); } free (grid); return 0; }  It’s at this right point where the C’s approach of multi-dimensional arrays becomes really clear. If you remember the first image of this post, the first row of that 5×4 grid was the array a. That a array of that picture is what I re-called here as grid. Look now at line 13 of the code: the malloc()‘s function usage is just the same as before, when we only had a 1D-array, but now it was obvious since we had clear that C use the concept of ‘array of arrays’. So, after we created the first row for grid, we are just going to extend each element of grid into a new array: it is to say, grid[0] is going to be a new array (it will represent the first column of grid), grid[1] will be a new array as well, and so on. Thus, a for-loop for calling malloc() as times as elements has grid is needed here. Once we understood the concept of array of arrays in C, it becomes obvious how the free() function should work, but be careful: the order you free the memory does matter. Let’s see schematically what is going on there: If you pay attention at the code above, we are calling free (grid) only after we have called free () for every element of grid array, and there is an important reason to do so: if you call free (grid) in the first place, you are freeing only the grid array, it is to say, you are only freeing the element a[0] to element a[4]. What does that mean? It means that you are only freeing the first index of each a[i] array (being i a number between 0 and 4), it is to say, you are freeing a[0][0], a[1][0], a[2][0], a[3][0] and a[4][0]. But this has important side effects: after you free a, you lose each pointer that references each a[i] and you can’t free them later. Therefore you will have memory leaks. Finally, here is the second more efficient method for allocating dynamically an array: #include <stdio.h> #include <stdlib.h> int main (void){ int i = 0; int rows = 4, columns = 5; int **grid = NULL; /* Allocating the matrix */ grid = (int **) malloc (rows * columns * sizeof (int *)); grid[0] = (int *) malloc (rows * sizeof (int)); for (i = 1; i < rows; i++){ grid[i] = grid[i - 1] + columns; } /* Time to free the matrix */ free (grid[0]); free (grid); return 0; }  This second method is more efficient because there are only two calls to malloc() (and, consequently, two calls to free()). Another issue is that we are allocating now grid as a large 1D-array of rows x columns elements; once we have done this, we just assign to grid[j] the memory address of the corresponding block of memory grid[j - 1] moved rows number of rows. In fact, where we write grid[j] = grid[j - 1] + rows the compiler is really performing * (grid + j) = * (grid + (j - 1)) + rows. You can see a practical application of this when I solve the problem 11 of Project Euler (probably in my next post), where I will allocate in a matrix any set of numbers given from the standard input. References: ### Summation of primes (problem 10) Problem 10 of PE’s website says: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.   Find the sum of all the primes below two million. Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (From Wikipedia) And here is the C code. This time the unique remarkable fact is the fastness of the program: #include <stdio.h> #include <stdlib.h> #include <math.h> int esPrimo (unsigned long long int num); /* Returns 1 if "num" is a prime number. Otherwise it returns 0 */ unsigned long long int sumPrimes (unsigned int below_n); /* Returns the summation of all prime numbers below the number "below_n" */ int esPrimo (unsigned long long int num){ int retorno = 1; unsigned long long int i = 5LL; unsigned long long int r; if (num == 1){ retorno = 0LL; /* 1 is not considered a prime number */ } else if (num < 4) { retorno = 1; } else if (num % 2 == 0) { retorno = 0; } else if (num < 9){ retorno = 1; } else if (num % 3 == 0) { retorno = 0; } else { r = (unsigned long long int) sqrt ((double) num); i = 5LL; while (i <= r){ if (num % i == 0){ retorno = 0; break; } if (num % (i + 2) == 0){ retorno = 0; break; } i = i + 6LL; } } return retorno; } unsigned long long int sumPrimes (unsigned int below_n){ unsigned long long int result = 0; unsigned int i = 0; for (i = 0; i < below_n; i++){ if (esPrimo (i)){ result += i; } } return result; } int main (int argc, char *argv[]){ unsigned int below_number = (unsigned int) atoi (argv[1]); printf ("%llu\n", sumPrimes (below_number)); return 0; }  This time I will execute the program with the Unix time command, which displays the system resource usage of a program during its execution time: $ (gcc -Wall -Wconversion prob10.c) && time ./a.out 2000000 142913828922

 

real 0m1.002s user 0m1.000s sys 0m0.000s

It took only one second to perform the summation of all prime numbers below two million! Take a moment to think about the significance of this fact. What makes this program fast is the efficiency of the algorithm that evaluates whether a number is prime.
Compare it now with the first version of the algorithm I wrote:

int esPrimo (unsigned long long int num){

int retorno = 1;
unsigned long long int i = 2LL;

for (i = 2LL; i <= sqrt ((double) num); i++){
if (num % i == 0){
retorno = 0;
break;
}
}

if (num == 0){
retorno = 0;
}

return retorno;
}


This one is a more straightforward one, because it just implements the primitive definition of prime number. But this is also an inconvenience, because it doesn’t even care about some implications of the definition. For example, the fact that if 2 is not a divisor of, let’s say, $17$, implies that nor 4 neither 6 will be divisors of it, because they can be decomposed by a product where there is at least a $2$. The first algorithm just skips all the composite numbers of the ones evaluated before, and that gives its efficiency.

Let’s measure now the time which this “not optimized” version of the same program spends during its execution time:

(gcc -Wall -Wconversion prob10.c -lm) && time ./a.out 2000000 142913828922

 

real 0m10.278s user 0m10.269s sys 0m0.004s

10x times slower. No more words are needed.

### Special Pythagorean triplet (problem 9)

Problem 9 of PE’s website says:

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which

$a^{2} + b^{2} = c^{2}$

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2.$

There exists exactly one Pythagorean triplet for which $a + b + c = 1000.$
Find the product $abc$

First of all, after you submit the correct answer on that website, a new forum is enabled to you so that you can post there the way you reached your solution, and there I found an elegant method that does not require code. I will just quote it:

@theopigott:
"I decided to have a go at this one on paper. I considered Euclid's formula for generating triples (a,b,c): a = m^2 - n^2, b = 2mn, c = m^2 + n^2.

 The aim is that a + b + c = 1000 This implies that 2m^2 + 2mn = 1000, so m^2 + mn = m(m + n) = 500. Now 500 = 2^2 * 3^3, so the possible factorisations (values for m and (m+n)) are: 1 * 500 2 * 250 4 * 125 5 * 100 10 * 50 20 * 25 

However m > n and (m+n) > m, so the only one that would work is m = 20 and m + n = 25, giving n = 5. Substituting back into Euclid's formula gives a = 375, b = 200, c = 425, and the desired product abc = 31875000."

Isn’t that beautiful? Before of writing my C program to solve the problem, I also tried to do it by hand through Euclid’s formula, but I got stuck at $m(m + n) = 500$. There I had an equation with two variables, so I couldn’t continue (avoiding trial and error). I also tried to solve the system of equations

$a + b + c = 1000 \\ a^{2} + b^{2} = c^{2}$

and performing the change of variables $a=m^2$$n^2$ , $b=2mn$ , $c=m^2+n^2$ (because then I could have a system of two equations with only two variables), but then I got a more complex equation with square roots and everything, so it didn't help to simplify the problem, but right the opposite.

I didn't thought about factorizing 500… shame on me! So instead I wrote the following program that solves the problem by brute force:

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

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

int findProduct (int sum_numbers);
/* Returns a number a*b*C such that (a, b, c) is a Pythagorean triplet and
a + b + c = sum_number */

double exponenciar (double base, int exponent){

double retorna;

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

return retorna;
}

int findProduct (int sum_numbers){

int a = 3, b = 4, c = sum_numbers - a - b;
int square_a = (int) exponenciar (a, 2);
int square_b = (int) exponenciar (b, 2);
int square_c = square_a + square_b;

int result = 0;

for (b = 4; b < sum_numbers; b++){
square_b = (int) exponenciar (b, 2);
for (a = 3; a < sum_numbers; a++){
square_a = (int) exponenciar (a, 2);
square_c = square_a + square_b;
c = 1000 - a - b;

if ((int) exponenciar (a + b + c, 2) == (int) exponenciar (sum_numbers, 2) &&
square_c == (int) exponenciar (c, 2)){
result = a*b*c;
break;
}
}
}

return result;
}

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

int number = atoi (argv[1]);

printf ("%d\n", findProduct (number));

return 0;
}


Time to compile and to run the program:

### Smallest multiple (problem 5)

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. ### Largest palindrome product (problem 4) 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$.

### About the language and the new approach of this blog

When I created this blog, a little over two weeks ago, was in order to have a place for having gathered all the solutions I’m finding to my informatic doubts or problems that sometimes arise, so then I could consult them in the future (it’s not the same understanding something explained by others, as something written by and for yourself) and, incidentally, that it could also be useful to other persons who need it.

I started writing this blog in Spanish for many reasons. Among them, there can be highlighted three main ones. The first one, for love to my mother tongue. I know that in an increasingly globalized world, especially in the IT field, it is not the fashion, but I think that, in some moment and in a certain way, we all should do a little tribute and a defense of our culture, especially in these times; I decided to do it by writing a blog about informatics for Spanish people.
And this leads me to the second reason why I opted for this language. For many reasons, we Spanish people, in general, have not ever been high-skilled in English language. Before I was not it either (and I admit that nowadays I still commit gramatical errors when writing), but now I realize how incredibly limited I was when I had to search for any information through the Internet in the Spanish language. It didn’t really seduce me the fact of spending more time reading a dictionary than reading that stuff I really wanted to read. For that reason I decided that, with my blog, I could provide my little contribute to all those Spanish persons who are in the same situation I was before.
The third reason is that most of (good) documentation is written in English, not in Spanish, and this is another of the aspects I wanted to do my bit.

From now this blog will be written entirely in English. I have been thinking about the set out in the last paragraph and I have changed my mind. Regarding the first reason, although I maintain what I explained, I have to say that Internet is what it is thanks to its globality. This means that the core of the internet is people, and since the communication has been the most important humanity’s invention, I think that we have to keep on promoting it (by using a common language), making easier the WWW’s growth.
I don’t forget Spanish people. Precisely because of that I will write in English too. We need to be more competitive, and my feeling is that, at least in the linguistic field, we have been always a bit lazy. I find it great that we want to read stuff in our own language (I prefer it too), but never under the pretext that we are not capable to understand (well) any other language.

If the whole internet had been written in my language, that would have meant that the world, by extension, runs fine with just Spanish, and then I wouldn’t have needed to train myself in other languages, with the consequent self-impoverishment. Thus I’m thankful for the fact that, at least for most people’s perspective, Internet runs in a foreign language.

Regarding the documentation issue, I have noticed something. It’s true that there is more good documentation written in English rather than good documentation written in Spanish but, with time, this difference is being smaller thanks to all those persons who, voluntarily, work hard for achieving translations in their respective languages (thank you! :D). Nevertheless, as I have said, if I stop writing in Spanish is because I think globality has been the stronghold of Internet and the basis of its development, so we should mantain it when possible (observe that I don’t use the word “always”).
More: an important percentage of English written data comes from support forums: there is not really more data coming from third sources than data coming from primary sources.
And the third reason leads me to the second big subtopic of this post: the approach change of the blog.

Yes, I will keep on talking about informatics, but not in the same way I have been doing until now. At least not always.
Something that has always fascinated me is the explanation of stuff behaviour and, by what I perceive, Internet is plenty of how-to explanations, but not of the why-to ones. Most of this good documentation mentioned above belongs to the first group, and the good documentation that belongs to the second one, neither is abundant, nor easy to find. Therefore, although my blog is written in English, I will try to not make it to be just one more of the Net, it is to say, another set of how-to’s. I would like to provide something more, something new.

Most probably I won’t receive so many visits, because living in a period where most of IT practitioners need to produce at a frenzied pace, Google is used more for searching how-to’s rather than why-to’s (and it is logical), so I will be happy if persons who come here can really enjoy of the reading of this site.

Finally, I want to greet from now all the future followers of this blog and to thank you just for your visit! I hope you enjoy of it as much as I do writing here.

Dani

### Representando caminos aleatorios en 2D (II)

Esta es la continuación de la primera parte.

Ya sabemos lo que es un camino aleatorio, lo que es un fractal y de qué manera establecerán los números aleatorios generados por Java la dirección en la que se mueve nuestro bicho por el tablero de GridWorld.

El código fuente que contiene toda la acción (es decir, las llamadas a las funciones que se encargan de mover al bicho o de cambiar su dirección) se llama BugRunner.java. El código en su forma original está copiado en el primer post del blog. Lo único que hacía ese código era crear un tablero, crear un bicho, una roca (que no hace nada, solo está ahí para estorbar al bicho), incorporarlos al tablero y mostrarlo.
Ahora haremos más cosas. Primero que todo pegaré el código tuneado:

import info.gridworld.actor.ActorWorld;
import info.gridworld.actor.Bug;
import info.gridworld.actor.Rock;
import info.gridworld.grid.UnboundedGrid;
import info.gridworld.grid.Location;

public class BugRunner
{

public static void justMove(Bug anyBug){
if (anyBug.canMove()){
anyBug.move();
}
else{
anyBug.turn();
}
}

public static void randomBug(int n, Bug bug_three){
double result;
int i = 0;

for(i = 0; i < n; i++){
result = Math.random();
if(result < 0.25){
bug_three.setDirection(Location.NORTH);
justMove(bug_three);
}
else if((0.25 <= result) && (result < 0.5)){
bug_three.setDirection(Location.EAST);
justMove(bug_three);
}
else if((0.5 <= result) && (result < 0.75)){
bug_three.setDirection(Location.SOUTH);
justMove(bug_three);
}
else{
bug_three.setDirection(Location.WEST);
justMove(bug_three);
}
}
}

public static void main(String[] args)
{
int steps = 500000;
ActorWorld world = new ActorWorld(new UnboundedGrid());
Bug redBug = new Bug();
randomBug(steps, redBug);
world.show();
}
}


Salvo quizá la función randomBug(), no parece muy complicado intuir qué es lo que hace la primera función, ¿verdad? Ésta simplemente recibe un objeto llamado Bug (que previamente creamos en la función principal, main) y decide qué es lo que hace el bicho según si éste tiene espacio para moverse en una dirección o no. La función canMove() evalua si el bicho puede avanzar una casilla en la dirección a la que apunta su cabeza; si puede, se ejecuta el método move() (no voy a ofenderte explicándote qué hace esta función), en caso contrario, el bicho gira 45º en sentido horario.

El cómo están escritos los métodos canMove(), turn() y move(), es lo de menos aquí. Lo único que hay que saber sobre éstos es que son métodos definidos en el objeto Bug (o sea, nuestro bicho), que a su vez hereda los métodos de la clase Actor, que es la que define todos los “protagonistas” de GridWorld (como los bichos, las rocas, o las flores que va dejando el bicho detrás suyo cada vez que avanza una casilla).

Ahora vamos a mirar la función randomBug. Si habéis atendido a las explicaciones dadas en el primer post, no hay mucho más que añadir, simplemente que antes de dar cada paso, redefinimos la dirección a la que apunta el bicho (la probabilidad de que apunte a una dirección u otra es, además, la misma) y a continuación llamamos justMove().

Finalmente, también hay algunos cambios en la función principal, como que en lugar de crear un tablero con los bordes definidos (como teníamos por defecto en la función principal) creamos un tablero sin bordes, esto es, infinito. Evidentemente esto es necesario para poder apreciar las formas tan extrañas que pinta el bicho (en forma de flores que va dejando por su paso).
Además de eso he quitado la roca que molesta, ya que la gracia de un camino aleatorio es que nada altere la partícula que lo traza.
Se crea el objeto redBug y se lo pasamos a la función randomBug, que hace el resto. Además, si nos fijamos, necesitaremos que el bicho se mueva muchas veces, ya que si solo avanzamos una casilla, tampoco podremos apreciar nada. Para eso definimos una variable que recibe un número y la pasamos también por valor a la función randomBug, que es la que utilizará en el bucle como cota superior y la que, por lo tanto, definirá el número de pasos que dará el bicho. Yo le he puesto medio millón de pasos. ¡Vaya caminata va a pegarse!

También he modificado la función zoomOut() de la clase GridPanel, ya que la interfaz gráfica no me permetía alejarme del tablero todo lo que yo quería:

public void zoomOut()
{
/* cellSize = Math.max(cellSize / 20, MIN_CELL_SIZE/20); */

cellSize = cellSize / 10;
revalidate();
}


Lo que está en ese comentario es la línea que había antes de que yo la sustituyera por

cellSize = cellSize / 10;

que es como funciona la función antagónica, zoomIn(), solo que ésta en vez de engrandecer el tablero diez veces lo hace simplemente el doble.

Ejecutamos el programa primero con la vista por defecto y después con el zoom:

Click para ampliar

No, no he puesto la pantalla negra del terminal ahí en medio para molestar, sino para que el bicho sea más fácil de ver. ¿Veis donde queda la cruz del botón anaranjado del terminal? Pues justo a la izquierda está el bicho. Y si os fijáis en la última línea del terminal, aparece las coordenadas del bichito. Simplemente he añadido esto en la penúltima línea en la función main:

System.out.println("Location: " + redBug.getLocation());

Porque imaginaos el panorama. Si yo ya tenía poca paciencia para encontrar a Wally entre quinientos muñecajos, imaginaos lo que supone buscar una mariquita entre medio millón de flores…

Alejamos el zoom:

Click para ampliar

Súperzoom (las imágenes se verán más claras al darle con la lupa encima):

Click para ampliar

Bonito, ¿eh? Vamos a desplazarnos un poco a la izquierda del mapa:

Click para ampliar

Y ahora una ejecución más del mismo programa, directamente con el zoom a tope, solo para ver qué otras formas pintamos:

Click para ampliar

Click para ampliar

¿No resulta increíble que todas esas formas resulten de una sola función que devuelve números aleatorios?

Ahora es un buen momento para señalar un aspecto más de los caminos aleatorios. Resulta que en Física podemos modelar los gases como un conjunto muy vasto de partículas que se mueven a altas velocidades, chocando entre ellas, cambiando su dirección constantemente y, en definitiva, creando la sensación de que cada partícula se mueve de una forma absolutamente aleatoria.
Pero ocurre que ninguna de estas partículas se mueve de forma aleatoria, sino que está sometida a un proceso caótico, esto es, un proceso en el que una pequeña variación de las condiciones iniciales implica un cambio drástico en el comportamiento del sistema. Si tenemos una partícula encerrada en una caja, moviéndose siguiendo un patrón, podemos predecir su posición en cada instante de tiempo. También somos capaces de hacerlo con dos partículas. Pero con tres ya no (ver: problema de los tres cuerpos), al menos no de manera analítica, sino tirando ya de aproximaciones. Ocurre que en un gas no tenemos una, dos o tres partículas, sino que tenemos del orden de billones, de trillones de partículas… y todas ellas en movimiento, interactuando las unas con las otras, forman un sistema caótico. Ojo, no hay que confundir “caótico” con “aleatorio”. Un sistema caótico lo es en el sentido de que, debido a su complejidad, es imposible predecir su estado exacto en un momento dado, pero éste sigue sujeto a un conjunto reducido de leyes físicas: es determinista.

Pero ahora viene lo bueno. Resulta que los sistemas deterministas se comportan (cuidado, no confundir “comportarse” con “ser”) como sistemas aleatorios. Y aquí un ejemplo de ello:

Click para ampliar

¿Os resulta familiar? Pues no ha sido mi bicho. Esa imagen (extraída de la Wikipedia) es una representación de lo que se llama un proceso de Wiener, también llamado movimiento Browniano, que es el nombre que se le pone al movimiento (aparentemente) aleatorio que siguen las partículas de un gas, o de cualquier fluido en general. Precisamente el hecho de que los sistemas (caóticos) deterministas se comporten como si no lo fueran, ha servido de puente para que puedan ser estudiados en términos estadísticos y de probabilidades.
En particular, los caminos aleatorios sirven para modelizar los procesos de Wiener. Y lo mejor de todo es que estos procesos no quedan restringidos a la física estadística, sino que otras ramas de la ciencia como la Economía o la Biología también se sirven de los procesos de Wiener (o sea, de los caminos aleatorios) para modelar otros fenómenos, como la evolución de los precios del mercado o el flujo de moléculas en un proceso de difusión.

### Representando caminos aleatorios en 2D (I)

Esto va sobre estadística, fractales… y belleza.

Antes que nada haré un pequeño resumen de lo que será este post así como de su organización, ya que este es un tema un tanto complejo por el contenido de otras disciplinas que involucra y que se relacionan entre si.

Este post tiene dos partes: la primera, ésta, que es donde definiré el problema a resolver, el razonamiento a seguir, y alguna consideración matemática más (algunos lo llamarán “la parte aburrida”). La segunda parte es donde echaré mano al código del programa y se verá la acción (ésta será “la parte chula”).

Como dice el título, el objetivo es, de alguna manera, representar gráficamente un fenómeno, llamado camino aleatorio, que se da cuando una partícula se mueve aleatoriamente en un espacio de N dimensiones (en nuestro caso particular, el espacio será de dos dimensiones). Esta manera será via una interfaz gráfica que proporciona el programa GridWorld, en la que inicialmente tenemos un bichito moviéndose discretamente en línea recta (mientras no haya obstáculos por su camino, como piedras u otros bichitos) por un plano dividido en cuadrículas.
A propósito, cuando digo “moviéndose discretamente” me refiero a que el movimiento se compone por un número determinado de pasos, es decir, el movimiento no se da de manera continua, no hay “fluidez”; va a saltos. Pero esto nos viene de lujo porque a la hora de demostrar (o mejor dicho, de convencernos sobre) algunas de las propiedades que exhiben los caminos aleatorios nos facilitará bastante la vida.

Obviamente tendremos que modificar el comportamiento de este bicho para que, en lugar de moverse en línea recta, se mueva de forma totalmente aleatoria. Con un número de pasos lo suficientemente grande y con la escala adecuada, veremos generado lo que se llama un fractal aleatorio. ¡Que no cunda el pánico! La traducción al castellano de todo esto está por llegar.

Finalmente añadiré que, como seguramente más de uno habrá podido sospechar, cada uno de estos pasos son decididos mediante una función de Java — Math.random() — que devuelve números aleatorios comprendidos entre el 0 y el 1 (sin llegar a éste). La idea es dividir este rango de valores en cuatro intervalos de manera que, según si el número aleatorio cae en un intervalo u otro, el bicho del programa gira cero, una, dos o tres veces 90 grados en sentido horario. Por lo tanto, si queremos que el bicho se mueva de forma aleatoria, nos interesa que los números devueltos por Math.random() sean realmente aleatorios.

Y esto nos lleva, por fin, al principio del post. Es necesario hacer una matización: los números aleatorios generados por un ordenador son pseudo-aleatorios. Vamos, que no son aleatorios. Hay que recordar que un ordenador es una máquina determinista y, como tal, no conoce el libre albedrío. En particular, no sabe generar números de forma realmente aleatoria. En su lugar utiliza funciones y parámetros tales (como los obtenidos del reloj de la CPU) que le permiten obtener números que, al menos a simple vista, aparentan ser aleatorios.

Para comprobar qué tan aleatorios son estos números generados por la máquina (o qué tan bien simulan serlo) existen los llamados tests de aleatoriedad. Hay muchos (como los especificados al final de esta página) y para diferentes propósitos. Por ejemplo, es posible que un conjunto de números supere un determinado test de aleatoriedad pero no otro.
Como decía más arriba, para asegurarme de que, al final de todo, consigo pintar un camino aleatorio, nunca está de más someter a alguna que otra prueba funciones como Math.random().

Tengo que confesar que la Estadística nunca ha sido mi fuerte, así que para convencerme de que puedo confiar en esta función he optado por un método estadístico algo más rudimentario, como es el de comprobar que, llamando Math.random() un número grande de veces, puedo obtener algo que se parezca a una distribución de Gauss. El razonamiento es el siguiente:

En cualquier ciencia experimental, una manera de acotar los errores aleatorios que surgen de la medición de una determinada magnitud consiste en repetir dicho experimento (es decir, dicha medición) un número muy grande de veces. Cuantas más veces se repita la medición, más probabilidades hay de acercarse al valor real de la magnitud que pretendemos medir (aunque nunca se alcanza de manera exacta).
Pensemos en el siguiente ejemplo: tenemos un dardo e intentamos lanzarlo a una diana (que huelga decir que está justo en el centro del tablero). Fallamos. Demasiado alto. Ahora tiramos dos dardos más. Volvemos a fallar: uno se ha desviado demasiado a la derecha y el otro ha ido más abajo. Ahora tiramos 20.000 dardos. ¿Os imagináis cómo queda el tablero después de 20.000 tiros? Sí, agujereado por todos los puntos.
Si dividiéramos el tablero en regiones del mismo tamaño, contaríamos aproximadamente el mismo número de puntos en cada una de ellas, ya que, libres de influencias externas (por ejemplo, que los dardos estén manipulados) la probabilidad de fallar tanto “por arriba” como “por abajo” es la misma, por lo que, conforme se va incrementando el número de veces que lo intentamos, el centro geométrico de todos estos tiros se aproxima (que no que coincide) a… ¡la diana! Justamente el centro geométrico del tablero.

En el caso del ejemplo obtenemos una distribución de Gauss, es decir, una función que tiene esta forma:

El eje horizontal representa el valor de nuestras mediciones (en el ejemplo podrían ser las coordenadas, con el origen $(0,0)$ situado en la diana, de cada agujero que hemos hecho en el tablero), y el eje vertizal la probabilidad con que podemos obtener esos valores. En la imagen $\mu$ representa la media de todos los valores que hemos obtenido y $\sigma$ la varianza. Una de las propiedades más llamativas de la distribución de Gauss es que, independientemente de los valores de las mediciones, el 68% de éstas tienden a estar dentro del intervalo $[\mu - \sigma, \mu + \sigma]$, coincidiendo el valor más probable precisamente con $\mu$, la media aritmética.

He utilizado esta segunda idea para comprobar que los números aleatorios generados por Math.random() (que recordemos que devuelve números naturales más pequeños que 1) forman algo parecido a una distribución normal. Y digo “algo parecido” porque el hecho de que la media aritmética de todos los números coincida justamente con la media de los dos extremos (que sería el equivalente a la diana de nuestro tablero), 0.5, no significa realmente nada, ya que además necesitaríamos comprobar que el 68% de los valores obtenidos caen dentro de $[\mu - \sigma, \mu + \sigma]$, pero como el fin último de este post no es la estadística y tampoco se trata de aburrir (en exceso) al personal, vamos a hacer un acto de fe y vamos a asumir que la distribución obtenida de invocar muchas veces Math.random() se ajusta a la de la campana de Gauss.

Alguien podría quejarse diciendo que eso es mucho asumir, ya que podría ser que Math.random() devolviera todo el rato valores como 0.4, 0.6, 0.6, 0.4, 0.6… y la media de todo eso nos saldría muy cercana a 0.5, y es verdad, así que aquí está la prueba visual de que, al menos en un primer momento, podemos confiar en Math.random():

Click para ampliar

Ahora vamos a comprobar si la media de un conjunto de valores lo suficientemente grande, pongamos de 100.000.000 valores, se aproxima a 0.5:

Click para ampliar

(El código que hace esto lo he subido aquí.)

La primera media nos da 0.499993… y la segunda 0.50001… Tiene buena pinta. Podemos seguir adelante.
Por aburrido y doloroso que haya sido esto, era necesario para asegurarnos de que al final, utilizando esta función de Java, podemos simular un movimiento realmente aleatorio y de que, en consecuencia, los patrones que vamos viendo a grandes escalas resulten todavía ¡más increíbles!

Pero… ¿qué es un fractal y qué tiene que ver con todo esto? Aunque el tema por si mismo merece un post aparte, haré un esbozo de lo que son estas entidades matemáticas. Fractal proviene de la palabra latina fractus, que significa roto o fracturado. Esto es debido a que los fractales son objetos que no tienen dimensión entera, sino dimensión fraccionaria (de hecho, la primera definición formal que se dio para este tipo de objetos ya involucraba explícitamente el concepto de dimensión).
Una de las primeras definiciones más típicas (y amigables) que se da sobre ellos viene a ser así: un fractal es una forma geométrica que puede ser subdividada en partes, siendo cada una de ellas una copia (o una réplica muy parecida) a escala reducida del fractal entero. Esta propiedad es conocida como autosimilitud, y es la que también aparece a grandes escalas en los caminos aleatorios.

Como dicen que una imagen vale más que mil palabras, aquí podéis trastear con uno de los fractales más conocidos que hay: el conjunto de Mandelbrot. Podéis ir acercando el zoom a cada una de sus “ramas”, por ejemplo, para ver en qué consiste exactamente esto de la autosimilitud.
Un último apunte sobre los fractales. Aunque los fractales más conocidos son los descritos mediante funciones matemáticas iteradas sobre ellas mismas infinitas veces (idealmente), no hay que verlos como unos objetos exóticos que nada tienen que ver con la realidad. Véase por ejemplo el problema de cuánto mide la costa de Gran Bretaña.

Dicho esto, vámonos ya a la segunda parte.