Constante de Kaprekar

El número 6174 es un número realmente misterioso. A simple vista, puede no parecer tan obvio, pero estamos a punto de ver que cualquier persona que sepa restar también puede descubrir el misterio que hace al número 6174 tan especial. En en año 1949 el matemático Dattatreya Ramachandra Kaprekar (Devlali, India) ideó un proceso que hoy en día conocemos como la Operación de Kaprekar. Esta operación está sujeta a las siguientes reglas:

\{\omega\in \mathbb{N}\ |\ \omega = n_{1}n_{2}n_{3}n_{4}\ |\ 0 \leq n \leq 9\ |\{n_{1}n_{2}n_{3} | n_{2}n_{3}n_{4}\}\ne nnn \}

Esto es:

  • \omega\in \mathbb{N} \rightarrow El número inicial ha de ser una cadena de dígitos que formen un numero natural.
  • \omega = n_{1}n_{2}n_{3}n_{4} \rightarrow La longitud de \omega ha de ser de 4 dígitos.
  • 0 \leq n \leq 9 \rightarrow Cada uno de los dígitos ha de ser un número natural comprendido entre el 0 y el 9, ambos inclusive.
  • \{n_{1}n_{2}n_{3} | n_{2}n_{3}n_{4}\}\ne nnn \rightarrow No puede haber tres dígitos seguidos iguales.

Por ejemplo, aquí algunos ejemplos de números aceptados y no aceptados conforme a las reglas de arriba:

Aceptados No aceptados
1234 1118
7391 4333
8033 5555
2764 0000
\vdots \vdots

La operación es muy sencilla, consiste en elegir un número que cumpla la reglas ya descritas anteriormente. Por ejemplo el número 9581. A continuación, reorganizar los dígitos para obtener el número más grande y el más pequeño que estos dígitos pueden hacer.

Número mas grande posible \rightarrow 9851
Número mas pequeño posible \rightarrow 1589

Después, restar al número más grande el número más pequeño para obtener un nuevo número.

9851-1589=8262

Si se repite una y otra vez la operación con cada nuevo número, se termina obteniendo la constante de Kaprekar, o sea el número 6174.

8622-2268=6354
6543-3456=3087
8730-0378=8352
8532-2358=6174 \Longleftarrow

El motivo por el que no se puede escoger un número con tres dígitos consecutivos iguales es por que o bien en la primera resta (cuatro dígitos seguidos iguales) o en la segunda resta (tres dígitos seguidos iguales) termina dando resto 0. Por ejemplo:

7666-6667=999
999-999=0

Al final, da igual el número que se escoja (siempre que cumpla las reglas anteriores), al final siempre devuelve el número 6174.

A continuación dejo el código fuente de un programa en C que hace la Operación de Keprekar sobre un número introducido.

/*
 * constanteKaprekar v0.01
 * Copyleft - 2016  Javier Dominguez Gomez
 * Written by Javier Dominguez Gomez <jdg@member.fsf.org>
 * GnuPG Key: 6ECD1616
 * Madrid, Spain
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Compilation: gcc -std=gnu99 -O0 -g3 -Wall -c -o constanteKaprekar.o "constanteKaprekar.c"
 *              gcc -o constanteKaprekar constanteKaprekar.o
 *
 * Usage:       ./constanteKaprekar
 */

#include <stdio.h>
#include <stdbool.h>

/* Procedimiento para ordenar dos numeros. */
void swap(int *x, int *y) {
	if (*x < *y) {
		int aux;
		aux = *x;
		*x = *y;
		*y = aux;
	}
}

/* Funcion que devuelve la longitud de un int. */
int LongitudInt(int n) {
	int i = 1;
	while (n > 9) {
		i++;
		n /= 10;
	}
	return i;
}

/* Funcion que devuelve un int con sus digitos en orden descendente. */
int OrdenacionDescendenteInt(int n) {
	int i, n_ordenado = 0;
	for (i = 9; i >= 0; i--) {
		int aux = n;
		while (aux > 0) {
			int digit = aux % 10;
			if (digit == i) {
				n_ordenado *= 10;
				n_ordenado += digit;
			}
			aux /= 10;
		}
	}
	return n_ordenado;
}

/* Funcion que devuelve un int con sus digitos en orden ascendente. */
int OrdenacionAscendenteInt(int n) {
	int i, n_ordenado = 0;
	for (i = 0; i <= 9; i++) {
		int aux = n;
		while (aux > 0) {
			int digit = aux % 10;
			if (digit == i) {
				n_ordenado *= 10;
				n_ordenado += digit;
			}
			aux /= 10;
		}
	}
	return n_ordenado;
}

/* Funcion que comprueba si el numero introducido tiene 4 digitos. */
static bool CompruebaDigitos(int n) {
	if (LongitudInt(n) < 4) {
		printf("Longitud del numero %d invalida. Tiene que tener 4 digitos.\n", n);
		return false;
	} else {
		return true;
	}
}

int main() {
	int n, x, y, kaprekar;

	do {
		printf("Numero de 4 digitos: ");
		scanf("%d", &n);
	} while (CompruebaDigitos(n) == false);

	x = OrdenacionDescendenteInt(n);
	y = OrdenacionAscendenteInt(n);
	kaprekar = x - y;

	printf("%d - %d = %d\n", x, y, kaprekar);

	do {
		if (kaprekar == 0) {
			printf("Numero %d invalido por resto 0.\n", n);
			break;
		}
		x = OrdenacionDescendenteInt(kaprekar);
		y = OrdenacionAscendenteInt(kaprekar);
		kaprekar = x - y;
		printf("%d - %d = %d\n", x, y, kaprekar);
	} while (kaprekar != 6174);

	return 0;
}

Una vez compilado este es su funcionamiento:

./constanteKaprekar
Numero de 4 digitos: 9581
9851 - 1589 = 8262
8622 - 2268 = 6354
6543 - 3456 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174

Puertas lógicas

OR

  1. Ecuación lógica
    S = A + B
  2. Código electrónico internacional
    7432
  3. Funcionamiento
    Tabla de la verdad
    A B S
    0 0 0
    0 1 1
    1 0 1
    1 1 1

AND

  1. Ecuación lógica
    S = A \cdot B
  2. Código electrónico internacional
    7408
  3. Funcionamiento
    Tabla de la verdad
    A B S
    0 0 0
    0 1 0
    1 0 0
    1 1 1

NOT

  1. Ecuación lógica
    S = \overline{A}
  2. Código electrónico internacional
    7404
  3. Funcionamiento
    Tabla de la verdad
    A S
    0 1
    1 0

NOR

  1. Ecuación lógica
    S = \overline{A+B}
    S = \overline{A} \cdot \overline{B}
  2. Código electrónico internacional
    7402
  3. Funcionamiento
    Tabla de la verdad
    A B S
    0 0 1
    0 1 0
    1 0 0
    1 1 0

NAND

  1. Ecuación lógica
    S = \overline{A\cdot B}
    S = \overline{A}+\overline{B}
  2. Código electrónico internacional
    7400
  3. Funcionamiento
    Tabla de la verdad
    A B S
    0 0 1
    0 1 1
    1 0 1
    1 1 0

XOR

  1. Ecuación lógica
    S = A\oplus B
    S = A\cdot \overline{B}+\overline{A}\cdot B
  2. Código electrónico internacional
    7486
  3. Funcionamiento
    Tabla de la verdad
    A B S
    0 0 0
    0 1 1
    1 0 1
    1 1 0

XNOR

  1. Ecuación lógica
    S = \overline{A\oplus B}
    S =\overline{A\cdot B}+A\cdot B
  2. Código electrónico internacional
    XOR+NOT
  3. Funcionamiento
    Tabla de la verdad
    A B S
    0 0 1
    0 1 0
    1 0 0
    1 1 1

Si te ha interesado este artículo puede que también te interese este: Álgebra de Boole

Cálculo de números primos en C

Un número primo es un número natural que solo es divisible (con resto cero) por si mismo y por 1. Por ejemplo, el número 4 no es primo por que se puede dividir entre 1, 2 y 4, sin embargo el número 3 si es primo, ya que solo se puede dividir entre 1 y si mismo. Veamos el detalle:

4 % 1 = 0 (true)
4 % 2 = 0 (true)
4 % 3 = 1 (false)
4 % 4 = 0 (true)

Como se puede ver, el número 4 no solo es divisible con resto cero entre 1 y él mismo, también lo es entre 2, por lo tanto no es un número primo. Veamos ahora el detalle con el número 11:

11 % 1  = 0 (true)
11 % 2  = 1 (false)
11 % 3  = 2 (false)
11 % 4  = 3 (false)
11 % 5  = 1 (false)
11 % 6  = 5 (false)
11 % 7  = 4 (false)
11 % 8  = 3 (false)
11 % 9  = 2 (false)
11 % 10 = 1 (false)
11 % 11 = 0 (true)

En el caso del número 11 si podemos afirmar que es un número primo ya que solo es divisible por 1 y por él mismo.

Ahora que ya sabemos cómo podemos identificar un número primo solo queda hacer la lógica en un programa C en el que indicaremos como valor para la variable limite la cantidad de números a analizar, para este ejemplo he puesto 1000.

#include <stdio.h>

int main(int argc, char **argv) {
	int i, limite = 1000, primo, j;

	for (i = 2; i <= limite; i++) {
		for (j = 2; j < i; j++) {
			primo = 1;
			if (i % j == 0) {
				primo = 0;
				break;
			}
		}
		if (primo != 0) printf("%d ", i);
	}
	return 0;
}

Y tras compilarlo, al ejecutarlo nos devuelve lo siguiente:

./numerosPrimos
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

 

Para obtener más cantidad de números primos solo hay que modificar el valor de la variable limite.

Cálculo aproximado de Pi

A lo largo de la historia, varias personas han intentado hallar una fórmula que sirva para obtener una aproximación lo mas exacta posible del número Pi. Algunas fórmulas son muy precisas, pero todas tienen un margen de error cada cierto número elevado de decimales. Por suerte hoy disponemos de computadoras que permiten realizar cálculos a enormes velocidades.

Pi

A finales del año 2010 los matemáticos Alexander Yee y Shigeru Kondo utilizaron el Algoritmo de Chudnovsky como método para calcular los decimales de Pi y una computadora casera con 96 GB de memoria RAM para conseguir superar el record que ya poseían, y que actualmente es de 10 Billones de decimales. Para ello tardaron 371 días con la computadora trabajando a su máximo rendimiento. Toda una proeza, sin duda.

La expresión matemática del Algoritmo de Chudnovsky es la siguiente:

\displaystyle {426880 \sqrt{10005} \over \pi}= \sum_{k=0}^\infty {(6k)!(13591409+545140134k) \over (3k)!(k!)^3 (-640320)^{3k}}

Aquí he hecho un Hack con el algoritmo en C que devuelve como resultado un valor escandalosamente aproximado de Pi con 16 dígitos:

#include <stdio.h>
#include <math.h>

//Funcion que devuelve el factorial de un numero
double fact(double n) {
 if(n == 0) return 1;
 else return n * fact(n-1);
}

int main(void) {

 double k, pi;

 //Algoritmo de Chudnovsky
 for(k=0.0; k<=1.0; k++) {
  pi += fact((6.0 * k)) * (13591409.0 + (545140134.0 * k)) / ((fact(3.0 * k) * pow(fact(k),3.0)) * pow(-640320.0,(3.0 * k)));
 }

 pi = 426880 * sqrt(10005)/pi;

 printf("%.16f\n", pi);

 return 0;
}

El resultado de su ejecución sería el siguiente:

./chudnovsky
3.1415926535897931

Pero esto no es suficiente. Si lo que queremos es obtener, por ejemplo, un millón de decimales o más tendremos que usar un método un poco diferente, y para ello utilizaremos la librería GMP de la Free Software Foundation. Esta librería nos proporcionará una serie de funciones y procedimientos aritméticos para nuestros cálculos, así que para poder probarlo es necesario instalar la librería en nuestro sistema antes de nada. Este es un ejemplo* de código C que tras ser compilado y ejecutado nos devolverá tantos dígitos de Pi como le hayamos indicado como argumento:

/*
* Compute pi to a certain number of decimal digits, and print it.
*
*   gcc -O2 -Wall -o chudnovsky chudnovsky.c -lgmp
*
* WARNING: This is a demonstration program only, is not optimized for
* speed, and should not be used for serious work!
*
* The Chudnovsky Algorithm:
*                               _____
*                     426880 * /10005
*  pi = ---------------------------------------------
*         _inf_
*         \     (6*k)! * (13591409 + 545140134 * k)
*          \    -----------------------------------
*          /     (3*k)! * (k!)^3 * (-640320)^(3*k)
*         /____
*          k=0
*
* http://en.wikipedia.org/wiki/Pi#Rapidly_convergent_series
*
* First million digits: http://www.piday.org/million.php
*
* Copyright (c) 2012 Brian "Beej Jorgensen" Hall <beej@beej.us>
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

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

// how many to display if the user doesn't specify:
#define DEFAULT_DIGITS 60

// how many decimal digits the algorithm generates per iteration:
#define DIGITS_PER_ITERATION 14.1816474627254776555

/**
 * Compute pi to the specified number of decimal digits using the
 * Chudnovsky Algorithm.
 *
 * http://en.wikipedia.org/wiki/Pi#Rapidly_convergent_series
 *
 * NOTE: this function returns a malloc()'d string!
 *
 * @param digits number of decimal digits to compute
 *
 * @return a malloc'd string result (with no decimal marker)
 */
char *chudnovsky(unsigned long digits)
{
	mpf_t result, con, A, B, F, sum;
	mpz_t a, b, c, d, e;
	char *output;
	mp_exp_t exp;
	double bits_per_digit;

	unsigned long int k, threek;
	unsigned long iterations = (digits/DIGITS_PER_ITERATION)+1;
	unsigned long precision_bits;

	// roughly compute how many bits of precision we need for
	// this many digit:
	bits_per_digit = 3.32192809488736234789; // log2(10)
	precision_bits = (digits * bits_per_digit) + 1;

	mpf_set_default_prec(precision_bits);

	// allocate GMP variables
	mpf_inits(result, con, A, B, F, sum, NULL);
	mpz_inits(a, b, c, d, e, NULL);

	mpf_set_ui(sum, 0); // sum already zero at this point, so just FYI

	// first the constant sqrt part
	mpf_sqrt_ui(con, 10005);
	mpf_mul_ui(con, con, 426880);

	// now the fun bit
	for (k = 0; k < iterations; k++) {
		threek = 3*k;

		mpz_fac_ui(a, 6*k);  // (6k)!

		mpz_set_ui(b, 545140134); // 13591409 + 545140134k
		mpz_mul_ui(b, b, k);
		mpz_add_ui(b, b, 13591409);

		mpz_fac_ui(c, threek);  // (3k)!

		mpz_fac_ui(d, k);  // (k!)^3
		mpz_pow_ui(d, d, 3);

		mpz_ui_pow_ui(e, 640320, threek); // -640320^(3k)
		if ((threek&1) == 1) { mpz_neg(e, e); }

		// numerator (in A)
		mpz_mul(a, a, b);
		mpf_set_z(A, a);

		// denominator (in B)
		mpz_mul(c, c, d);
		mpz_mul(c, c, e);
		mpf_set_z(B, c);

		// result
		mpf_div(F, A, B);

		// add on to sum
		mpf_add(sum, sum, F);
	}

	// final calculations (solve for pi)
	mpf_ui_div(sum, 1, sum); // invert result
	mpf_mul(sum, sum, con); // multiply by constant sqrt part

	// get result base-10 in a string:
	output = mpf_get_str(NULL, &exp, 10, digits, sum); // calls malloc()

	// free GMP variables
	mpf_clears(result, con, A, B, F, sum, NULL);
	mpz_clears(a, b, c, d, e, NULL);

	return output;
}

/**
 * Print a usage message and exit
 */
void usage_exit(void)
{
	fprintf(stderr, "usage: chudnovsky [digits]\n");
	exit(1);
}

/**
 * MAIN
 *
 * See usage_exit() for usage.
 */
int main(int argc, char **argv)
{
	char *pi, *endptr;
	long digits;

	switch (argc) {
		case 1:
			digits = DEFAULT_DIGITS;
			break;

		case 2:
			digits = strtol(argv[1], &endptr, 10);
			if (*endptr != '\0') { usage_exit(); }
			break;

		default:
			usage_exit();
	}

	if (digits < 1) { usage_exit(); }

	pi = chudnovsky(digits);

	// since there's no decimal point in the result, we'll print the
	// first digit, then the rest of it, with the expectation that the
	// decimal will appear after "3", as per usual:
	printf("%.1s.%s\n", pi, pi+1);

	// chudnovsky() malloc()s the result string, so let's be proper:
	free(pi);

	return 0;
}

Por ejemplo, si queremos saber los 1000 primeros dígitos de Pi tendríamos que ejecutarlo de la siguiente manera:

./chudnovsky 1000

 Y nos devuelve Pi con los siguientes 1000 dígitos:

3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019

Como curiosidad, si obtenemos 44904 decimales de Pi podremos observar que en la posición 44899 aparece la cadena... 44899. Alucinante, ¿verdad? Aquí se puede ver un fragmento de los últimos 44904 dígitos:

Cadena 44899 en la posición 44899 de los decimales de Pi.
Cadena 44899 en la posición 44899 de los decimales de Pi.

IMPORTANTE: No te recomiendo que pruebes a calcular un número de decimales de Pi muy elevado (por ejemplo un millón), ya que es posible que tu CPU comience a calentarse considerablemente. Este era un truco muy viejo que se usaba para "romper" el ordenador de alguien hace muchos años, y consistía en meter en el arranque un algoritmo que calculase decimales de Pi como si no hubiera mañana en un sumatorio de infinitas iteraciones.

*Agradecimientos a Brian "Beej Jorgensen" Hall.

Curiosidades de la simetría numérica

¿Quien dijo que las matemáticas eran aburridas? Son lo suficientemente complejas como para estar en "casi todos" los rincones del Universo, pero también tienen algunas fórmulas sencillas que dan como resultado unas series numéricas que forman patrones simétricos, capicúas, progresiones geométricas y un montón de cosas más. A continuación dejo unos ejemplos matemáticos y su desarrollo en C para que lo pruebe el que quiera:

Ejemplo 1
#include <stdio.h>

int concat();

int main(void) {
	int num = 1;

	for (int i = 1; i <= 9; i++) {
		printf("%9d * 8 + %d = %d\n", num, i, num*8+i);
		num = concat(num, i+1);
	}
}

int concat(int x, int y) {
	int temp = y;
	while (y != 0) {
		x *= 10;
		y /= 10;
	}
	return x + temp;
}

El resultado de la ejecución de este primer ejemplo será la siguiente:

        1 x 8 + 1 = 9
       12 x 8 + 2 = 98
      123 x 8 + 3 = 987
     1234 x 8 + 4 = 9876
    12345 x 8 + 5 = 98765
   123456 x 8 + 6 = 987654
  1234567 x 8 + 7 = 9876543
 12345678 x 8 + 8 = 98765432
123456789 x 8 + 9 = 987654321
Ejemplo 2
#include <stdio.h>

int concat();

int main(void) {
	int num = 1;

	for (int i = 1; i <= 9; i++) {
		printf("%9d * 9 + %2d = %d\n", num, i+1, num*9+i+1);
		num = concat(num, i + 1);
	}
}

int concat(int x, int y) {
	int temp = y;
	while (y != 0) {
		x *= 10;
		y /= 10;
	}
	return x + temp;
}

El resultado de la ejecución de este segundo ejemplo será la siguiente:

        1 x 9 +  2 = 11
       12 x 9 +  3 = 111
      123 x 9 +  4 = 1111
     1234 x 9 +  5 = 11111
    12345 x 9 +  6 = 111111
   123456 x 9 +  7 = 1111111
  1234567 x 9 +  8 = 11111111
 12345678 x 9 +  9 = 111111111
123456789 x 9 + 10 = 1111111111
Ejemplo 3
#include <stdio.h>
#include <math.h>

void f(int x) {
	printf("f(%2d) = ((10^%2d)-1)/9 = %.0f\n", x, x, (pow(10, x) - 1) / 9);
}

int main(int argc, char **argv) {
	int x;
	printf("f(x) = ((10^x)-1)/9\n\n");
	for (x = 1; x <= 20; x++) f(x);
	return 0;
}

El resultado de la ejecución de este tercer ejemplo será la siguiente:

f(x) = ((10^x)-1)/9

f( 1) = ((10^ 1) - 1) / 9 = 1
f( 2) = ((10^ 2) - 1) / 9 = 11
f( 3) = ((10^ 3) - 1) / 9 = 111
f( 4) = ((10^ 4) - 1) / 9 = 1111
f( 5) = ((10^ 5) - 1) / 9 = 11111
f( 6) = ((10^ 6) - 1) / 9 = 111111
f( 7) = ((10^ 7) - 1) / 9 = 1111111
f( 8) = ((10^ 8) - 1) / 9 = 11111111
f( 9) = ((10^ 9) - 1) / 9 = 111111111
f(10) = ((10^10) - 1) / 9 = 1111111111
f(11) = ((10^11) - 1) / 9 = 11111111111
f(12) = ((10^12) - 1) / 9 = 111111111111
f(13) = ((10^13) - 1) / 9 = 1111111111111
f(14) = ((10^14) - 1) / 9 = 11111111111111
f(15) = ((10^15) - 1) / 9 = 111111111111111
f(16) = ((10^16) - 1) / 9 = 1111111111111111
f(17) = ((10^17) - 1) / 9 = 11111111111111111
f(18) = ((10^18) - 1) / 9 = 111111111111111111
f(19) = ((10^19) - 1) / 9 = 1111111111111111111
f(20) = ((10^20) - 1) / 9 = 11111111111111111111
Ejemplo 4
#include <stdio.h>

int concat();

int main(void) {
	int num = 9;

	for (int i = 9; i >= 2; i--) {
		printf("%8d * 9 + %d = %d\n", num, i-2, num*9+i-2);
		num = concat(num, i-1);
	}
}

int concat(int x, int y) {
	int temp = y;
	while (y != 0) {
		x *= 10;
		y /= 10;
	}
	return x + temp;
}

El resultado de la ejecución de este tercer ejemplo será la siguiente:

       9 x 9 + 7 = 88
      98 x 9 + 6 = 888
     987 x 9 + 5 = 8888
    9876 x 9 + 4 = 88888
   98765 x 9 + 3 = 888888
  987654 x 9 + 2 = 8888888
 9876543 x 9 + 1 = 88888888
98765432 x 9 + 0 = 888888888
Ejemplo 5
#include <stdio.h>

int main(void) {
	double num = 1;

	for (int i = 1; i <= 9; i++) {
		printf("%9.0f * %-9.0f = %0.f\n", num, num, num*num);
		num = (num*10)+1;
	}
}

El resultado de la ejecución de este cuarto ejemplo será la siguiente:

        1 x 1         = 1
       11 x 11        = 121
      111 x 111       = 12321
     1111 x 1111      = 1234321
    11111 x 11111     = 123454321
   111111 x 111111    = 12345654321
  1111111 x 1111111   = 1234567654321
 11111111 x 11111111  = 123456787654321
111111111 x 111111111 = 12345678987654321

Sorprendente, ¿verdad?

Obtención de la función canónica a partir de la tabla de la verdad

Ya vimos en un post anterior sobre el álgebra de Boole los principios mas básicos de su aplicación en sistemas digitales. En este nuevo post toca explicar los que son las funciones canónicas y cómo podemos obtenerlas a partir de la tabla de la verdad de una función lógica. Esto nos va a venir muy bien para simplificar circuitos que inicialmente pueden ser enormes y muy aparatosos. Así pues, se define término canónico de una función lógica a todo producto o suma en el que aparecen todas las variables en su forma directa a o complementada \overline{a}. Estas son las dos formas canónicas minterm y maxterm:

1ª forma canónica minterm \Rightarrow suma de productos canónicos.
2ª forma canónica maxterm \Rightarrow producto de sumas canónicas.

OBTENCIÓN A PARTIR DE LA TABLA DE LA VERDAD

Supongamos que tenemos la siguiente tabla de la verdad para una función lógica de tres variables a, b y c:

Término minterm Término maxterm a b c F
0 0 0 0 0 0
1 1 0 0 1 1
2 2 0 1 0 1
3 3 0 1 1 0
4 4 1 0 0 0
5 5 1 0 1 1
6 6 1 1 0 1
7 7 1 1 1 1

Minterms: Se toman las salidas F que son "1" y se expresa como suma de términos producto en los que las variables que son "1" se expresan como literales y las que son "0" como invertidas

F(a,b,c) = \overline{ab}c+\overline{a}b\overline{c}+a\overline{b}c+ab\overline{c}+abc \Rightarrow
\Rightarrow F(a,b,c)=m_{1}+m_{2}+m_{5}+m_{6}+m_{7} = \sum m(1,2,5,6,7)

Maxterms: Se toman las salidas F que son "0" y se expresa como producto de términos suma en los que las variables que son "0" se expresan como literales y las que son "1" como invertidas.

F(a,b,c)=(a+b+c)(a+\overline{b}+\overline{c})(\overline{a}+b+c) \Rightarrow
\Rightarrow F(a,b,c)=M_{0} \cdot M_{3} \cdot M_{4} = \prod M(0,3,4)

PASAR DE LA 1ª FORMA CANÓNICA A LA 2ª FORMA CANÓNICA

F(a,b,c)=m_{1}+m_{2}+m_{5}+m_{6}+m_{7}=\sum m(1,2,5,6,7)

1. Se saca la función minterm invertida con los términos que son 0.

\overline{F(a,b,c)}=m_{0}+m_{3}+m_{4}=\sum m(0,3,4)

2. Se hace la inversa de la función aplicando la Ley de Morgan a los términos canónicos.

F(a,b,c)=\overline{m_{0}+m_{3}+m_{4}}=\overline{\sum m(0,3,4)}\Rightarrow
\Rightarrow F(a,b,c)=\overline{m_0} \cdot \overline{m_3} \cdot \overline{m_4}

3. Se obtiene directamente cambiando los términos minúscula por mayúscula.

F(a,b,c)=M_{0} \cdot M_{3} \cdot M_{4}

PASAR DE LA 2ª FORMA CANÓNICA A LA 1ª FORMA CANÓNICA

F(a,b,c)=M_{3} \cdot M_{4} \cdot M_{7}=\prod M(3,4,7)

1. Se representa la función invertida, tomando los términos maxterm que no aparecen.

\overline{F(a,b,c)}=M_{0} \cdot M_{1} \cdot M_{2} \cdot M_{5} \cdot M_{6} = \prod M(0,1,2,5,6)

2. Se hace la inversa de la función aplicando la Ley de Morgan a los términos canónicos.

F(a,b,c)=\overline{M_{0} \cdot M_{1} \cdot M_{2} \cdot M_{5} \cdot M_{6}}=\overline{\prod M(0,1,2,5,6)} \Rightarrow
\Rightarrow F(a,b,c)=\overline{M_{0}}+\overline{M_{1}}+\overline{M_{2}}+\overline{M_{5}}+\overline{M_{6}}

3. Se obtiene directamente cambiando los términos mayúscula por minúscula.

F(a,b,c)=m_{0}+m_{1}+m_{2}+m_{5}+m_{6}

EJEMPLOS

En este ejemplo veremos qué sucede cuando uno de los términos no es canónico. ¿Que significa que "no es canónico"? Supongamos que tenemos que hallar la 2ª forma canónica de la siguiente función lógica:

F(a,b)=\overline{a+a\overline{b}}

Aquí parecen dos términos, y ambos han de ser obligatoriamente canónicos, pero el primero no lo es por que aparece una a sola. Para que sea un término canónico han da parecer todas las variables en cada término, que en este caso son dos, a y b. Para hacerlo canónico podemos aplicar algunas leyes del álgebra de Boole. Por ejemplo:

F(a,b)=\underbrace{\overline{a+a\overline{b}}}_{Ley \ de \ Morgan}=\overline{a} \cdot \underbrace{\overline{a\overline{b}}}_{Ley \ de \ Morgan}=\overline{a} \cdot (\overline{a}+b) \Rightarrow

\Rightarrow \underbrace{\overline{a} \overline{a}}_{\overline{a} \cdot \overline{a}=\overline{a}}+\overline{a}b=\overline{a}+\overline{a}b=\underbrace{\overline{ab}}_{m_{0}}+\underbrace{\overline{a}b}_{m_{1}}+\underbrace{\overline{a}b}_{m_{1}}

En este momento ya tenemos lo tres términos de forma canónica, o lo que es lo mismo, la función tiene dos variables a y b y en cada término aparecen las dos variables. Para terminar, con la tabla de la verdad de esta función lógica de dos variables podremos obtener las dos funciones canónicas:

Tabla de la verdad:

Término minterm Término maxterm a b F
0 0 0 0 1
1 1 0 1 1
2 2 1 0 0
3 3 1 1 0

Minterm:

F(a,b)=m_{0}+m_{1}=\sum m(0,1)

Maxterm:

F(a,b)=M_{2} \cdot M_{3}=\prod M(2,3)

Álgebra de Boole

George Boole (1815 - 1864) desarrolló una herramienta matemática para solucionar problemas en función de dos únicos estados, el estado SI y el estado NO. Posteriormente se utilizaría para el estudio de los primeros computadores, George Booleen los que se pudo comprobar que para realizar grandes y complejos cómputos era mas factible usar la electrónica digital en vez de la analógica. Hoy lo seguimos utilizando prácticamente para todo. Puede parecer superfluo o poco relevante, pero en realidad se trata de la la base fundamental para entender las exigencias computacionales del procesamiento digital de la información, vamos ¡casi nada!

La aplicación del álgebra de Boole en computadores es del tipo binario, lo que quiere decir que el estado de un elemento del circuito lógico viene representado por una variable que puede valer "1" o "0". Un ejemplo que se utiliza siempre en sistemas digitales es un interruptor y como base una carga, de modo que si el interruptor está abierto hay tensión y si está cerrado no. Es decir, SI/NO, 1/0, verdadero/falso.

Por poner un ejemplo práctico, podremos decir "0" cuando una lámpara está apagada y "1" cuando está encendida.

Hoy en día tenemos sistemas de computadoras muy complicados en los que por muy complejos que estos sean al final internamente tienen un montón de dispositivos que o están abiertos o están cerrados. Lo complicado es que son muchos, y como son muchos pues nos veremos obligados a realizar funciones matemáticas con todos esos dispositivos para hacer funcionar un sistema digital.

En matemáticas, una función no es otra cosa mas que una representación de una serie de variables de entrada relacionadas ente si con las operaciones aritméticas correspondientes, de forma que el resultado de esa combinación nos va a dar un resultado de salida.

En el álgebra de Boole es exactamente igual, solo que el resultado de salida va a ser siempre un "0" o un "1". Por ejemplo, una función de tres variables de entrada se podría representar de la siguiente manera:

 F(a, b, c) = abc+ab\overline{c}+\overline{a}bc

Para poder facilitar el cálculo de los valores de salida utilizaremos una "tabla de la verdad". Se trata de una tabla que recoge todas las combinaciones de las variables de entrada y los valores que toman las salidas, por ejemplo, para la función de tres variables del ejemplo la tabla de verdad sería:

a b c F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

En este caso desconocemos cuál es la función F, pero si sabemos que salidas tiene. De momento eso no es importante, solo es un ejemplo. Ahora bien, la salida de F para cada caso dependerá de la función.

A continuación se detallan algunos ejemplos de operaciones que se podrán realizar en el álgebra de Boole con puertas lógicas.

OPERACIONES EN EL ÁLGEBRA DE BOOLE

  1. Unión o adición: F = A + B
    Es la suma de las variables, en lógica equivalente a la función OR.OR BooleEn un circuito con interruptores podríamos representar esta operación de la siguiente forma (interruptores en paralelo):
    Unión o adiciónEn este caso, para que la salida sea 1 y se encienda la bombilla bastaría con que uno de los dos (o los dos) interruptores A o B valgan 1. Por lo tanto, su tabla de verdad sería:
    A B F
    0 0 0
    0 1 1
    1 0 1
    1 1 1
  2. Intersección o producto: F = a \cdot b
    Es el producto de las variables, en lógica equivalente a la función AND.AND BooleEn un circuito con interruptores podríamos representar esta operación de la siguiente forma (interruptores en serie):
    Intersección o productoEn este caso, para que la salida sea 1 y se encienda la bombilla bastaría con que los dos interruptores A y B valgan 1. Por lo tanto, su tabla de verdad sería:
    A B F
    0 0 0
    0 1 0
    1 0 0
    1 1 1
  3. Complementación o inversión: F = \overline{a}
    Esta operación es simplemente la inversión del valor de la variable a la que se le aplique, por ejemplo A = \overline{A} o \overline{B} = B.

Tabla de verdad completa con todas las operaciones:

A B F=A+B F=A \cdot B F=\overline{A} F=\overline{B}
0 0 0 0 1 1
0 1 1 1 1 0
1 0 1 0 0 1
1 1 1 1 0 0

Leyes fundamentales

A continuación unas leyes muy básicas y fáciles de recordar que nos van a servir principalmente para simplificar y de este modo para hacer circuitos más reducidos, por lo tanto más eficaces:

a + \overline{a} = 1
a \cdot \overline{a} = 0
0 + a = a
1 \cdot a = a
1 + a = 1
0 \cdot a = 0
a + a = a
a \cdot a = a
\overline{\overline{a}} = a

Conmutativa: a + b = b + a \rightarrow a \cdot b = b \cdot a
Asociativa: a + b + c = (a + b) + c = a + (b + c) \rightarrow a \cdot b \cdot c = (a \cdot b) \cdot c = a \cdot (b \cdot c)
Distributiva: a + bc = (a+b)(a+c) \rightarrow a(b+c) = ab + ac
Absorción: a + ab = a(1 + b) = a \rightarrow a(a + b) = aa + ab = a
Morgan: \overline{a + b} = \overline{a} \cdot \overline{b} \rightarrow \overline{a \cdot b} = \overline{a} + \overline{b}
Teorema de Shannon: F=f(a,b,c) = a \cdot f(1,b,c)+\overline{a} \cdot f(0,b,c)
F=bc \Rightarrow F=abc+\overline{a}bc

Composición de circuitos

Podemos crear un circuito a partir de una función y también al revés, por ejemplo, el circuito resultante de la siguiente función sería:

S=a\overline{c}+bc+\overline{a}c
Circuito ejemplo Boole

En los próximos artículos veremos la obtención de las diferentes funciones canónicas a partir de una tabla de la verdad como las que ya hemos visto aquí y también la simplificación mediante mapas de Karnaugh.

Conversor de Binario a Decimal en Java

En marzo escribí una entrada en la que explicaba la notación matemática para convertir un número binario a decimal. Aunque Java no es de mis lenguajes preferidos, quise hacer la implementación de una clase en este lenguaje para compararlo con el mismo método en otros de mas bajo nivel como C o Ensamblador. Sin mas dilación, aquí va el código:

import java.util.Scanner;
 
public class BinarioDecimal {
 
	//Atributos
	private static String binario;
	private static int longitud;
	private static int decimal;
 
	//Constructor vacío
	public BinarioDecimal() {}
 
	//Programa principal
	public static void main(String[] args) {
		binario = getStringInput("Binario: ");
		longitud = binario.length();
		int n = longitud;
		for (int i = 0; i < longitud; i++) {
			n--;
			int b = Character.getNumericValue(binario.charAt(i));
			decimal += b*(int)Math.pow(2,n);
		}
		System.out.printf("Decimal: %d", decimal);
	}
 
	//Metodo para leer la entrada por teclado
	public static String getStringInput(String prompt) {
		Scanner in = new Scanner(System.in);
		System.out.print(prompt);
		String input = in.nextLine();
		in.close();
		return input;
	}
}

He añadido alguna cosa de más, como la entrada de datos mediante la clase Scanner de java.util para hacerlo interactivo, aunque lo importante es que aquí se puede apreciar la fórmula matemática de conversión:

\displaystyle \sum_{i=0}^{n=bits-1} b_{i} \cdot 2^{n-i}

GnuPG - Defiende tu correo

Si crees que tu correo es seguro, probablemente no lo sea. Y si crees que a nadie le interesa lo que puedas escribir por mail a tus amigos o familiares, probablemente estés equivocad@.

"¿Pero por qué, si yo no soy nadie importante?"

Sí eres importante, y mucho. El que "vigila" tiene interés por saber con quién te relacionas, que comida te gusta, que ropa llevas, que música escuchas o que orientación política te define, y una lista interminable de cosas mas. Esa información es tremendamente valiosa, y sirve para muchas cosas, como estadística, fines comerciales o seguimiento policial en caso de detección de asuntos "sospechosos" en las comunicaciones.

Con las fotos pasa lo mismo, hay quien no se lo cree (o no quiere creerlo), pero las redes sociales poseen sofisticados sistemas de reconocimiento facial con el que identifican patrones para catalogar personas en momentos determinados, en lugares determinados y en coordenadas determinadas. La mayoría de las veces regalamos toda esta información sin darnos cuenta o restando importancia a todo ello, pero si que es importante, hay mucho en juego.

Afortunadamente existen métodos y herramientas para poner trabas o hacer mas difícil la "escucha" de las comunicaciones. Una de ellas es GnuPG para el correo electrónico o para cifrar archivos. La imagen que pongo a continuación de la Free Software Foundation explica muy bien qué es y para que sirve.

Defiende tu correo by Free Software Foundation.
Defiende tu correo by Free Software Foundation.

Pero cifrar el correo no es suficiente, nuestros ordenadores y Smartphones vienen preconfigurados de modo que sin enterarnos envían datos de todo tipo sobre nuestra vida y nuestros hábitos, cada pocos minutos, de forma constante. Parece una película de ficción, pero no lo es. No estoy contando nada nuevo, algunos llevamos muchos años denunciando y divulgando siempre que tenemos ocasión estas prácticas y fines. En este video lo cuenta de una forma excelente Marta Peirano, y razón no le falta.

Ya sabéis, si queréis privacidad, solo hay que tener voluntad. Ahí fuera hay Petabytes de información para ser un poco mas invisible, solo hay que buscar en internet (con Tor).

Bitcoin: Relación "Precio-Estabilidad del precio"

No voy a hacer ningún análisis técnico ni aportaré datos sobre macroeconomía, principalmente por que no poseo tal conocimiento sobre la materia. Pero si voy a plantear la situación que parece que se avecina, según diversas opiniones en el mundo Bitcoin. La mayoría de los "expertos" en Bitcoin coinciden en que después de las grandes subidas de la estabilidad del precio vendrá una gran subida en el valor del Bitcoin, como ya ha ocurrido anteriormente. Pero cuidado, también hay algún "experto" que dice lo contrario, son menos, aunque no por ello equivocados. En este gráfico de Azop se puede ver qué es lo que sucedió sobre el 17 de mayo de 2012 o el 28 de diciembre de 2012. Hubo una subida progresiva muy considerable, apenas sin rebote y con un volumen dentro de lo normal. Pero también está marcada una gran subida sobre el 26 de septiembre de 2013, y en esas fechas no hubo un pico de estabilidad que superara los 60 puntos (la mitad que las dos anteriores). Luego se aprecia una bajada continua que duró casi un año y medio, hasta finales de junio de 2015 donde la estabilidad vuelve a subir por encima de los 80 puntos, pero el precio del Bitcoin no subió a lo loco, se estabilizó y parece que desde aquel momento entramos en un periodo en el que las subidas y bajadas son mucho mas moderadas y de lenta progresión.

Estabilidad del precio del Bitcoin a fecha 7 de abril de 2016.
Estabilidad del precio del Bitcoin a fecha 7 de abril de 2016.

En el siguiente gráfico de Bitstamp está marcado el pico de estabilidad comprendido entre agosto y noviembre de 2015 que aparece en el gráfico anterior, donde se aprecia un considerable crecimiento del volumen, catapultando el precio hasta duplicarlo, aunque luego se volvería a estabilizar en torno a los $400.

Subida de volumen entre agosto y noviembre de 2015, en Bitstamp.

Bitstamp es un exchange Británico-Esloveno, hoy en día uno de los mas importantes del mundo. Pero quien realmente manda es China. Su exchange por excelencia, Huobi, tiene el siguiente registro de volumen que llama la atención:

Subida espectacular de volumen en Huobi, entre octubre de 2015 y abril de 2016.
Subida espectacular de volumen en Huobi, entre octubre de 2015 y abril de 2016.

Espectacular. ¿Que ha pasado en ese periodo? ¿Será la creación de alguna nueva mina en China que opera a toda máquina? ¿Será que ante una devaluación estrepitosa de Yuán los chinos con ahorros están buscando una vía de escape? Curioso cuanto menos. Parece que cada vez que sube el volumen de cualquier exchange importante se ve reflejado en una subida del precio. Lo que si es seguro es que la estabilidad del precio de Bitcoin está subiendo como la espuma desde febrero de 2016, y si nos fijamos en la misma foto en el pasado podríamos pensar que se aproxima una gran subida en el precio.

Lo importante en todo este asunto es que suba el volumen, que la gente se documente, lea, estudie y utilice Bitcoin si cree que es una buena idea, para comprar o para vender, pero que se utilice, el precio es lo de menos (menos para los que buscan lucrarse). Lo que es seguro es que en los próximos años habrá sorpresas, para bien o para mal. Tranquilidad, no hay que apresurarse. El futuro de Bitcoin no está escrito, pero si triunfa lo hará a lo grande.