DIGITALES 3: PROFE CHUCHO: Números primos del 0 al 511

Un número primo es aquel número que solo es divisible por si mismo y por la unidad. Se asume que el número 1 no es primo, aunque hay discusión al respecto. Así, los veinte primeros números primos son: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 y 71.

Para conocer la historia de los números primos y detalles se recomienda consultar la página http://es.wikipedia.org/wiki/N%C3%BAmero_primo.

Otro enlace interesante es http://mimosa.pntic.mec.es/jgomez53/matema/conocer/primos.htm

La famosa Criba de Eratóstenes, matemático griego que ideo una forma fácil y sencilla de identificar a los números primos, eliminando los múltiplos de los primeros números primos (como son el 2, 3, 5, 7, 11, 13, 23, etc.) mayores o iguales que el número primo elevado al cuadrado, consultar en http://amigosdelamatematica.blogspot.es/1202842500/

Veamos como podemos implementar un algoritmo en Arduino que nos permita dado un número, conocer si este es un número primo o no. Para ello inicialmente elaboramos el código para un contador binario ascendente de 9 bits implementado en Arduino mega 2560:

int outPin[] = {37, 39 ,41, 43, 45,47,49,51,53};

int tiempo = 2000;

void setup()

{

int i = 0;

for ( i = 0; i < 9; i++)

pinMode(outPin[i], OUTPUT);

}

void loop()

{

int i = 0, j=0;

for ( i = 0; i <512; i++)

{

for ( j = 0; j < 9; j++)

{

if ( ( (i >> j) & 1 ) == 1 )

digitalWrite(outPin[j], HIGH);

else digitalWrite(outPin[j], LOW);

}

delay(tiempo);

}}

`Vamos a analizar con todo detalle el programa hasta aquí, trabajando con una plaqueta Arduino Mega2560:` `Lo primero que hacemos es hacer un arreglo o lista de valores, indicando los pines correspondientes a cada led.` `La instrucción Int outPin[]= {37,39,41,43,45,47,49,51,53}; nos evita tener que declarar por separado para cada led su pin de conexión.` La siguiente instrucción `int` `tiempo = 2000;` determina el tiempo que transcurre para el cambio de un número binario al siguiente, ( 2 segundos)

`A continuación para la configuración de pines como salidas se tiene la instrucción` `void` `setup() { int i=0; for (i = 0; i < 9;i++); pinMode(outPin[i],OUTPUT);} , donde el primer led a la derecha, para nuestro caso correspondiente al bit menos significativo, el LED 0 lo conecta al pin 37, el siguiente, el LED 1 al 39, y así sucesivamente hasta conectar el led correspondiente al bit mas significativo, LED 8, al extremo izquierdo, en el pin 53.` `Los nueve leds junto con su valor en paréntesis los vamos a denominar LED 0 (1), LED 1 (2), LED 2(4), LED 3 (8), LED 4 (16), LED 5 (32), LED 6(64), LED 7 (128), LED 8 (256).` `Luego pasamos al bucle principal:` `void loop()` `{` `int i=0, j=0;` `for (i=0;i<512;i++)` `{` `for(j=0;j<9;j++)` `{` `if ( ( ( i >> j ) & 1) ==1)` `digitalWrite(outPin[j], HIGH);` `else digitalWrite(outPin[j],LOW);}` `delay(tiempo);}` `}`

Las instrucciones for anidadas permiten que el contador avance por todos los 512 números correspondientes a los 9 bits, desde el 0, (000000000)₂ hasta el 511, (111111111)₂, pero en cada número hace un recorrido del 0 al 8, correspondiente a los 9 bits de cada número en binario manejados por los 9 LEDs.

 La función
loop() al  ejecutarse una y otra vez, lo
que hace es iterar por los 512 números que podemos mostrar, ya que tenemos 9
Leds, y 2 elevado a 9 es igual a 512.

Fijaremos nuestra mayor atención en la instrucción:

{ if ( ( ( i >> j ) & 1) ==1)

digitalWrite(outPin[j], HIGH);

else digitalWrite(outPin[j],LOW);}

Para que por
cada número, se encienda  o apague  cada led correspondiente, la clave está en el
bucle que realiza la operación “(i >> j) & 1″.

La instrucción ( i >> j )

maneja el 
operador de desplazamiento a la derecha

>>

de los
bits de la expresión binaria correspondiente al decimal en referencia.

Por
ejemplo al llegar el contador al decimal 100 que ya vimos corresponde al
binario 001100100_2, la
instrucción (100>>0) establece que el binario permanece sin
alteración;

luego
(100>>1) quiere decir que el binario 001100100₂se desplaza
hacia la derecha una posición colocando un 0 como bit mas significativo o sea
queda  000110010₂ que equivale
al 50, o sea 100 dividido por 2; luego la instrucción (100>>2) al
desplazar al 100 en binario 2 posiciones a la derecha rellenando con cero a la
izquierda queda 000011001₂ , o sea el 25 decimal, 100 dividido por
4, o lo que es lo mismo 50 dividido por 2. Esto nos lleva a la conclusión que
la instrucción

( i >> j )

nos sirve para efectuar las sucesivas divisiones por 2 que hay que
realizar con cualquier número en decimal para su conversión en binario.

&1

es un operador AND.  El 1 en 9  bits
es 000000001₂.  La operación
lógica  AND obedece a la siguiente tabla:
0&0=0; 0&1=0; 1&0=0; 1&1=1. 
Para que dé un 1 los 2 bits deben ser 1, de lo contrario la AND da 0.

La
instrucción (i
>> j) & 1 realiza la operación AND bit por bit entre el
binario establecido al aplicar el desplazamiento a la derecha del decimal en
cuestión con el 1 en binario. Veamos con ejemplos:   (100>>1)&1
= 0  pues la AND bit a bit entre 000110010₂y 000000001₂ es igual a 0.  Por otra parte, (100>>2)&1=1, pues
la AND bit a bit entre 25 y 1 es igual a 1, pues la AND entre 000011001₂y
000000001₂ es igual a 1, por ser ambos 1 los bits menos
significativos de las dos expresiones binarias. Vemos entonces que de esta
manera se pueden tomar los residuos  al
efectuar la divisiones sucesivas  por 2.

Veamos ahora
en su conjunto la instrucción completa :

{ if ( ( ( i >> j ) & 1) ==1)

digitalWrite(outPin[j], HIGH);

else digitalWrite(outPin[j],LOW);}

Cada iteración del bucle divide el número en cuestión por 2 y se queda
únicamente con el bit de menor valor. Así  sabemos si tenemos que encender o no el LED.

Por ejemplo,
para mostrar el número 341, que en binario es (101010101) deberíamos encender
los Leds  0, 2,  4, 6 y 8, 
dejando  apagados el resto.  El calculo sería:

LED 0: 341 (101010101
& 1) -> 1, encendido

LED 1: 341 /
2 = 170 (010101010 & 1) -> 0, apagado

LED 2: 170 /
2 = 85 (001010101& 1) -> 1, encendido

LED 3: 85 / 2
=   42 (000101010 & 1) -> 0,
apagado

LED 4: 42 / 2
=   21 (000010101 & 1) -> 1,
encendido

LED 5: 21 / 2
=   10 (000001010 & 1) -> 1,
apagado

LED 6: 10 / 2
=  5   
(000000101 & 1) -> 1, encendido

LED 7: 5 / 2
=    2    (000000010 & 1) -> 1, apagado

LED 8: 2 / 2
=    1  
 (000000001 & 1) -> 1,
encendido

Como vemos, el
resultado del cálculo es correcto. Básicamente lo que se hace es ir desplazando
los bits hacia la derecha y quedándonos con el bit menos significativo.

Lo que vamos a hacer luego es recorrer todos los números entre el 0 y el número sobre el que queremos saber si es primo o no.

Dentro de un bucle comprobaremos el principio del número primo. "Divisible por si mismo y por la unidad". Es decir, que si encontramos un número que es divisible por el número evaluado, este dejará de ser primo.

Por ejemplo, el número 10 no es primo. Ya que 10 es divisible por 2 y 5. Esto, expresado en términos matemáticos vendría a decir, que el residuo entre los dos números es 0.

Veámoslo:

10/2 = 5, residuo 0

10/5 = 2, residuo 0

La función que nos ayuda a conocer el residuo entre dos números es el módulo. Y en Arduino se representa con el tanto por ciento.

Así:

10%2 = 0

10%5 = 0

10%3 = 1 (Ya que 10/3 = 3 y el residuo es 1)

Adicional a la identificación de si el número desde el 0 al 511 (9 bits) es primo, en el monitor del puerto serial del Arduino se va a imprimir el número en sistema decimal, binario, octal, hexadecimal, y su respectivo carácter en código ASCII; así mismo se visualiza en 9 leds el encendido y apagado de los leds en binario, con cambio en el contador cada 5 segundos, y un buzzer electromagnético con un led jumbo se activan durante 150 ms cuando se detecta que el número es primo.

El programa respectivo, completo, es el siguiente:

int outPin[] = {37, 39 ,41, 43, 45,47,49,51,53};//9 leds del contador binario

int tiempo = 5000; //tiempo de reloj del contador

int k = 0;

int residuo = 0;

int nc = 0; //contador de divisiones exactas

int buzzer = 9;

int led = 8;

void setup()

{

int i = 0;

for ( i = 0; i < 9; i++)

pinMode(outPin[i], OUTPUT);

Serial.begin(9600);

pinMode(buzzer,OUTPUT);

pinMode(led,OUTPUT);

}

void loop()

{

Serial.println(" NUMEROS DEL 0 AL 511 EXPRESADOS EN DECIMAL,BINARIO OCTAL, HEXADECIMAL, CARACTER ASCII,CON IDENTIFICACION SI ES NUMERO PRIMO");

int i = 0, j=0;

for ( i = 0; i <512; i++)

{

for ( j = 0; j < 9; j++)

{

if ( ( (i >> j) & 1 ) == 1 )

digitalWrite(outPin[j], HIGH);

else digitalWrite(outPin[j], LOW);

}

for ( k = 1; k <= i; k++)

{

residuo = i % k; //residuo al dividir el número i entre el número k

if (residuo == 0)

{

nc = nc + 1; //contador de divisiones exactas, sin residuo, se incrementa

}

if ((nc <= 2)&&( nc > 1)) //contador menor o igual a 2 y a la vez mayor a 1 (número primo)

{

Serial.println (" ");

Serial.print (" ");

Serial.print ("PRIMO.....");

Serial.print (i,DEC);

Serial.print (" Decimal ");

Serial.print (i,BIN);

Serial.print (" Binario ");

Serial.print (i,OCT);

Serial.print (" Octal ");

Serial.print (i,HEX);

Serial.print(" Hexadecimal ");

Serial.print (i,BYTE);

Serial.print(":Caracter ASCII ");

digitalWrite(buzzer,HIGH);

digitalWrite(led,HIGH);

delay (150);

digitalWrite(buzzer,LOW);

digitalWrite(led,LOW);

delay(tiempo);

nc = 0;

}

else if (nc != 2) //contador de divisiones exactas, diferente de 2 (al no ser primo)

{

Serial.println (" " );

Serial.print (" ");

Serial.print (i,DEC);

Serial.print (" Decimal ");

Serial.print (i,BIN);

Serial.print (" Binario ");

Serial.print (i,OCT);

Serial.print (" Octal ");

Serial.print (i,HEX);

Serial.print(" Hexadecimal ");

Serial.print (i,BYTE);

Serial.print(":Caracter ASCII ");

delay(tiempo);

nc = 0;

}

Importante que el lector entienda el algoritmo para la identificación del número primo, punto crucial del presente proyecto. La instrucción ((nc <= 2)&&( nc > 1)) establece cuando el número es primo, excluyendo el cero y el uno, permitiendo que estos dos números sean evaluados.

La instrucción (nc != 2) indica que al ser el contador nc diferente a 2, el número de divisiones exactas, o sea sin residuo, diferente a 2, ello significa que el número no es primo.

Este proyecto nos invita a estudiar los sistemas numéricos decimal, binario, octal, y hexadecimal, y la conversión de un sistema a otro.

Al ser posicional, el sistema decimal es un sistema de numeración en el cual el valor de cada dígito depende de su posición dentro del número. Al primero corresponde el lugar de la unidades, el dígito se multiplica por

100

(es decir 1); el siguiente las decenas (se multiplica por 10); centenas (se multiplica por 100), etc.

Consultar: http://es.wikipedia.org/wiki/Sistema_de_numeraci%C3%B3n_decimal

Respecto al sistema binario, en base 2, del cual ya se ha trabajado en proyectos anteriores, sabemos que solo utiliza dos dígitos, llamados bits, el cero y el uno. Se recomienda repasar en el enlace http://es.wikipedia.org/wiki/Sistema_binario.

La matemática binaria fue trabajada por George Boole quien creó un algebra que lleva su nombre. Ver información en http://es.wikipedia.org/wiki/George_Boole

El sistema numérico en base 8 se llama octal y utiliza los dígitos 0 a 7. Se recomienda consultar http://es.wikipedia.org/wiki/Sistema_octal

Del hexadecimal, base 16, ya habíamos hablado en proyectos anteriores, sabemos que utiliza 16 caracteres alfanuméricos, los números del 0 al 9, y las letras de la A hasta la F. Consultar la página http://es.wikipedia.org/wiki/Sistema_hexadecimal

Se recomienda al lector ejercitarse en la conversión entre los diferentes sistemas numéricos:http://www.dav.sceu.frba.utn.edu.ar/homovidens/gomezgomez_paz/PROYECTIN/PAGINA/conversionentresistdenumC.htm

Respecto al código ASCII (American Standard Code for Information Interchange) consultar http://es.wikipedia.org/wiki/ASCII

DIGITALES 3: PROFE CHUCHO

martes, 7 de octubre de 2014

Números primos del 0 al 511

1 comentario:

Archivo del blog