Números primos

¿Qué es un número primo? 

Un primo es un número natural (mayor que 1) que únicamente tiene dos divisores: el 1 y a sí mismo. Por ejemplo:

• 2 es primo (y de hecho es el único par)
• 3 es primo (y junto al 2 son los únicos números primos consecutivos, lo cual es lógico ya que el 2 es el único par)
• 4 no es primo, porque es divisible por 1, 2 y 4. En este caso, se llaman números compuestos (de nuevo a excepción del 1)
  
• 5 es primo, 6 no, 7 sí,... 199 sí, ... 983 sí,... y así hasta el infinito

 

El número 1 no es primo

Hemos comentado que el número 1 no es considerado primo, ¿por qué?

En el fondo se trata de una convención, ya que si fuésemos riguroso con la definición de números primos, en efecto sólo es divisible por sí mismo y por la unidad (de nuevo, sí mismo). De hecho, hasta el siglo XIX sí que se consideraba primo al número 1.

El hecho de considerar el 1 como no primo permite una formulación simplificada del teorema fundamental de la aritmética, que nos dice que:

Todo entero positivo n > 1 puede ser representado exactamente de una única manera como un producto de potencias de números primos

Por ejemplo:

 

 

Propiedades de los números primos

Algunas características de los números primos son:

• En el sistema decimal, salvo el 2 y el 5, todos los números primos terminan en 1, 3, 7 o 9
• Excepto el 2 y el 3, todo número primo puede representarse de la forma 6n+1 o 6n-1 (donde n es un número natural) 
• Excepto el 2, todo número primo puede representarse de la forma 4n+1 o 4n-1 
• Lema de Euclides: sean a y b dos números enteros de modo que su producto ab sea divisible por un número primo p implica que p es divisor de a o de b. 
• Teorema de Wilson 

Un número p > 1 es un número primo si y sólo si se cumple que

• (p - 1) ! ≡  -1 mod p
• (p - 1) ! ≡  (p-1) mod p  

La función mod (módulo) nos devuelve el resto de la operación. Para el caso concreto del Teorema de Wilson podemos verlo mejor con un ejemplo, donde comprobamos que para un número primo, el resto calculado coincide con el número a evaluar -1: 

 

O expresado de otra manera (que personalmente me gusta más, y es la que programaremos más adelante)

 

• Pequeño teorema de Fermat. Si p es un número primo, y a es un entero positivo mayor que 1 menor que p (es decir, 1<a<p)  

a^p-1 ≡ 1 (mod p) 

O en otras palabras, si a es un entero positivo y p es un primo que no divide a a, entonces p debe ser un factor de a^p-1-1. Veamos algunos ejemplos:

 

¿Cómo determinamos si un número es o no primo? Tests de primalidad

Acabamos de ver ciertas propiedades que a priori nos permitirían poder deter minar si un número es o no primo. En efecto, aplicarlas es más o menos sencillo para números pequeños, e incluso relativamente medianos. Pero cuando nos topamos con número grandes lo de ir comprobando si es divisible o no por todos los primos previos al número se convierte en una tarea ardua (incluso para los ordenadores más potentes). Para hacernos una idea, el número primo más grande conocido en la actualidad tiene la friolera de 24862048 cifras.

Existen varios enfoques para abordar la determinación de si un número es o no primo (esta propiedad se conoce como la primalidad del número). y dichos procedimientos se conocen como tests de primalidad. Estos tests se tratan de algoritmos que intentan verificar si un número dado es compuesto, y en función de lo que consigamos evaluar tenemos dos posibles resultados

Se demuestra que es compuesto, y por lo tanto, no es primo.

Non conseguimos demostrar que sea compuesto, por lo que ante la falta de una mejor certificación de que el número dado no sea compuesto podemos tener un cierto nivel de confianza de que se trate de un número primo.

Hemos que tener en cuenta que las operaciones ariméticas a realiar en los diversos procedimientos que comentaremos ahora suponen un consumo considerable de recursos de la máquina efectuando los cálculos (en especial cuando intervienen operaciones como el cálculo de factoriales que veíamos antes en el Teorema de Wilson, que hace que el tiempo necesario para la evaluación de números muy grandes sea prohibitivo.

La criba de Eratóstenes

Se trata del primer procedimiento matemático conocido para la determinación de este tipo de números (data del siglo 2 a.e.c, aunque existen referencias a los números primos anteriores a la de este método). El método consiste en confeccionar una lista (entre el número 2 y el número máximo que queramos evaluar) en la que se identifiquen todos los números primos contenidos en la misma.

El proceso para determinar estos números consiste en, de manera iterativa, ir "tachando" y marcando como compuestos todos los multiplos que sucedan al último número primo que hayamos encontrado. Veámoslo mejor con un ejemplo (supongamos que se nos pide encontrar todos los primos hasta el número 35:

• El primer número primo que nos encontramos es el 2, así que tachamos todos sus múltimos (todos los números pares)
• El siguiente sería el 3, así que tachamos todos los múltiplos siguientes (el 6 ya estaría tachado al ser múltiplo de 2, el 9, el 12 tachado previamente, el 15,...)
• El siguiente número es el 4, que al estar tachado por el 2 no es primoç
• Seguimos por el 5, que es primo, y tacharíamos por tanto todos sus múltiplos en la lista
• ...
• Así hasta terminar con la siguiente lista: 2, 3, 5, 7, 11, 13, 17, 19, 23, 19, 31.

Veamos una posibilidad de programar este método en R:

• Al inicio discernimos si se trata de 0 o 1 (no primo) o 2 (primo) evaluado directamente.
• Inicializamos una variable de iteración i=2.
• Creamos un vector vacío (la criba que iremos rellenando a modo de listado) donde cada elemento estará rellenado con una cadena de caracteres vacía (esto lo conseguimos inicializanod el vector con la función vector(mode = "character" ,val-1), donde el segundo parámetro val-1 será la longitud del mismo (-1 porque lo empezamos en el valor 2).
• Iteramos con un bucle while hasta que nuestro iterador tenga el mismo valor que el valor que queremos determinar si es primo o no.
• Si lo es (i==val) devolvemos TRUE. Enhorabuena, el número es primo
• En caso contrario, miramos lo que contiene el vector con la criba en la posición correspondiente. Si está vacío quiere decir que es un número primo entre 2 y nuestro valor, y lo marcamos con la letra P.
• Además, en este caso, iteramos sobre el resto de elementos de la lista empezando en j=i+i (para acceder al siguiente elemento de la lista múltiplo del primo intermedio que acabamos de encontrar, iterando la lista mientras j sea menor o igual que nuestro número a determinar. Donde en cada caso podemos tener que:
• j sea igual a nuestro número, es decir, es un múltiplo del último primo que hemos encontrado y por lo tanto se trata de un número compuesto, por lo que devolvemos FALSE. Lástima, no es primo.
• j tenga cualquier otro valor, por lo que dicho elemento será un número compuesto múltiplo del primo que acabamos de descubrir, y lo marcamos como C, para evitar considerarlo en futuras iteraciones.
  

# ------------------------------------------------ # eratostenes_prime # ------------------------------------------------ eratostenes_prime <- function(val){ if(val<2){return(FALSE)} if(val==2){return(TRUE)} i = 2 vec = vector(mode = "character" ,val-1) while(i<=val){ if(i==val){return(TRUE)} if(vec[i-1]==""){ vec[i-1]="P" j = i+i while(j<=val){ if(j==val){return(FALSE)} vec[j-1]="C" j=j+i } } i=i+1 } return(FALSE) }

 

El pequeño teorema de Fermat

Tal y como hemos visto en las propiedades de los primos, el pequeño teorema de Fermat nos dice que si p es un número primo, y a es un entero positivo mayor que 1 menor que p (es decir, 1<a<p)  

a^p-1 ≡ 1 (mod p) 

Y para programarlo en R podemos hacer lo siguiente:

[IMPORTANTE] antes de nada, como este método utiliza exponenciales (es decir, tendremos números que se harán grandes) hemos de ser conscientes de las limitaciones que tiene R a la hora de operar con números de gran tamaño (otros lenguajes de programación tendrán problemas similares). En nuestro caso, R tiene limitado el tamaño de los enteros con los que puede operar. Para ver cuál es dicho valor podemos ejecutar en la consola el comando .Machine$integer.max, que en mi caso me devuelve el valor 2147483647. Para solventar este problema, podemos hacer uso de la clase bigz que se encuentra dentro del paquete gmp

# GMP package to deal with big numbers install.packages("gmp") require(gmp)

En el ejemplo de la programación veremos cómo utilizarlo para curarnos en salud cuando los números se hagan excesivamente grandes. Así que ahora sí, vamos a ver cómo programar este pequeño teorema de Fermat: 

• Nuestra función recibe dos parámetros. Por un lado el valor (val) que queremos determinar si es o no primo, y por otro el parámetro a que usaremos como base de la exponencial
• Lo primero de todo, determinar trivialmente si se trata de un no primo en caso de evaluar el 0 o el 1, o en caso de tratarse del 2, devolver TRUE pues es primo.
  
• Sabemos que dicho valor a ha de cumplir una serie de condiciones: ser menor que p y no ser divisor de este (lo que supondría que el valor a determinar es compuesto). Por lo tanto, en un primer bucle while vamos a determinar cual es el menor valor de a que satisface esta condición (lo iremos incrementando de 2 en dos salvo en el caso inicial de a = 1 ya que en resto de casos iremos saltando de impar en impar hasta encontrar uno que satisfaga nuestra condición
• A continuación, y para solventar el problema de números excesivamente grandes que comentábamos en la nota inicial, declararemos una variable auxiliar definida como gran entero (bigz) que será la que utilizaremos en nuestras operaciones
• Evaluamos la expresión exponencial que dicta el pequeño teorema de Fermat. Si el residuo es 0 tenemos un primo (TRUE), y en caso contrario un compuesto (FALSE)
  

# ---------------------------------------------- # fermat_lt_prime # ---------------------------------------------- fermat_lt_prime <- function(val ,a=2){ if(val<=1){return(FALSE)} if(val==2){return(TRUE)} # Evaluate a while(val%%a==0){ if(a%%2==0){a=a+1} else{a=a+2} } val2 = as.bigz(val) # evaluate Fermat's little theorem if((as.bigz(a)^(val2-1)-1)%%val2==0){return(TRUE)} return(FALSE) }

 

Búsqueda ingenua

Puede que te estés preguntando, ¿y por qué no podemos ir mirando todos los números entre 2 y el que queremos determinar si es primo o no para ver si alguno es divisor de este?.

Pues sí, podemos (aunque cuanto mayor sea el número más tardará en realizar las comprobaciones del residuo de la división.

De nuevo nos podemos encontrar con el problema de tratar con números excesivamente grandes, así que igual que hemos visto en el método anterior, utilizaremos la clase bigz a la hora de programarlo en R:

• La función tiene dos parámetros: el valor (val) a determinar y un paráetro from_i para determinar el inicio a partir del cual empezar a evaluar los residuos.
• Como siempre, determinamos la posibilidad de que val sea 0, 1 o 2
• A consinuación, asignamos la variable auxiliar de tipo bigz para poder lidiar con números excesivamente grandes
• En un bucle while, iteraremos hasta que la variable de iteración i sea menor o igual que la raíz cuadrada de nuestro valor a evaluar (ya que éste será su máximo posible divisor), y dentro de cada iteración, si determinarmos que el residuo es 0, entonces el valor es compuesto. En caso contrario, incrementamos el iterador una unidad y volveremos a probar.
• Si salimos del bucle sin haber encontrado un divisor (ya que la raíz del valor será siempre menor que éste, y nunca llegaremos al punto de evaluar la división por si mismo), entonces hemos encontrado que el número no es compuesto.
  

# ----------------------------------------------- # naive_prime # ----------------------------------------------- naive_prime <- function(val ,from_i = 2){ if(val<=1){return(FALSE)} if(val==2){return(TRUE)} # GMP package is required to deal with big numbers val2 = as.bigz(val) i = from_i while(i<=round(sqrt(val))){ if(val2%%i==0){return(FALSE)} i=i+1 } return(TRUE) }

¿y ya está?

Para nada. Con lo que hemos visto aquí no hemos hecho más que rascar la punta del iceberg del mundo de los números primos. 

• No hemos visto, por ejemplo, las aplicaciones que tienen los números primos, entre las cuales destacan la seguridad y criptografía.
• No hemos hablado tampoco del desarrollo de nuevos algoritmos y métodos para determinar la primalidad de números primos más grandes.
• Ni hemos hecho referencia al estudio de los primos denominados de Mersenne y de cómo la búsqueda distribuida de primos de este tipo es la responsable del descubrimiento de los más recientes grandes primos hallados.

Así que si tienes interés por conocer más acerca de este tipo de números, puedes indagar en los enlaces que te dejo a continuación.

 

Bibliografía y enlaces de interés sobre los números primos

• Número primo (Wikipedia ESP)
  
• Prime number (Wikipedia ENG)
  
• Prime numbers (Geeks for geeks)
• A la caza de los números primos: ¿a quién importan y por qué? (BBVA Openmind) 
• Finding primes and proving primality (UTM)
  
• Los números primos y la criba de Eratóstenes (Derivando)
• Los números primos más grandes del mundo y ¡el enigma de los números perfectos! (Derivando)
• The top 5000. The list of largest known primes (UTM)
  

 

Serie de Fibonacci y teorema de Zeckendorf

Serie de Fibonacci

La secuencia de Fibonacci es una sucesión infinita de números naturales en la que cada elemento se obtiene mediante la suma de los dos elementos inmediatamente anteriores a éste:

Para poder generar la secuencia, necesitamos partir, pues, de dos elementos iniciales. Éstos son el 0 y el 1:

Por lo tanto, los primeros 10 elementos (considerando el f0 = 0 como el elemento primero) de la serie serían:

 

Las aplicaciones y curiosidades de esta serie son numerosas. Para profundizar en ellas puedes distraerte con los siguientes enlaces:

• Sucesión de Fibonacci (Wikipedia ESP)
  
• Fibonacci Number (Wikipedia ENG)
• La sucesión de Fibonacci y la razón áurea (Derivando)
  

 

Teorema de Zeckendorf

Hemos comentado que la serie de Fibonacci presenta una gran cantidad de curiosidades y aplicaciones. Una de éstas es el Teorema de Zeckendorf, que en resumen nos viene a decir que cualquier número natural puede descomponerse como una suma de números naturales que pertenecen a la serie de Fibonacci no consecutivos.

Teniendo en cuenta la serie de los 10 primeros elementos de la serie de Fibonacci que hemos visto más arriba, lo que nos viene a decir el teorema de Zeckendorf podemos verlo en los siguientes ejemplos

De nuevo, para ahondar en este tema y ver explicaciones más detalladas y demostraciones, echad un ojo a los siguientes enlaces:

• Zeckendorf's Theorem (Wikipedia ENG)
  
• La sucesión de Fibonacci, el teorema de Zeckendorf y un poemario magistral (Artículo de Marta Macho Stadler para el Cuaderno de Cultura Científica de la Universidad del País Vasco)

 

Programando que es gerundio

Vamos a ver cómo programar en R un par de funciones para calcular tanto la sucesión de Fibonacci para un número dado de elementos, así como la descomposición de Zeckendorf para un numero natural cualquiera.

Los elementos de R que se van a utilizar son:

•  Vectores
• declaración:  vector <- c()
• añadir elemento (e) al vector (vector):   vector <- append(vector, e)
• ordenar vector en orden descendente:  sort(vector, decreasing = TRUE)
• subconjunto de elementos con los índices de aquellas posiciones del vector que cumplen una determinada condición:  which(vector <=> condición)
• sumatorio de elementos del vector:  sum(vector)
• longitud (número de elementos) del vector: length(vector)
  
• Bucle for:  for(i in 1:n){}
• Bloque condicional: if(condición1){}else if(condición2){}else{}
• Bucle condicional: while(condición){}
  

 

Serie de Fibonacci

Construiremos una función (fibonacci) que puede recibir tres parámetros

• items = número de elementos de la serie a generar (por defecto 8)
• n1 = valor del primer elemento de la serie (por defecto 0)
• n2 = valor del segundo elemento de la serie (por defecto 1)

La función se construye dentro de un bucle for que itera sobre i desde el valor 1 hasta el valor recibido en el parámetro items.

Los dos primeros valores de la serie, como hemos visto antes, son los valores prefijados a 0 y 1. Sin embargo, al construir la función permitiendo modificar los dos elementos iniciales nos permitirá crear variantes de la serie de Fibonacci con diferentes elementos de partida.

Es decir, para los elementos de la iteración 1 y 2, los valores serán los indicados en los parámetros n1 y n2, y para el resto de elementos (el else) se construirá mediante la suma de los dos elementos anteriores del vector: fib[i-1] + fib[i-2]

# ------------------------------------------------ # fibonacci # ------------------------------------------------ fibonacci <- function(items = 8 ,n1 = 0 ,n2 = 1) { for(i in 1:items){ if(i==1){ fib <- c(n1) } else if(i==2){ fib <- append(fib, n2) } else{ fib <- append(fib, fib[i-1]+fib[i-2]) } } return(fib) }
 

 Si probamos esta función obtenemos los siguientes resultados: 

• fibonacci(10)
•  0  1  1  2  3  5  8 13 21 34
• fibonacci(30)  
• 0      1      1      2      3      5      8     13     21     34     55     89    144    233    377    610    987   1597   2584   4181   6765  10946  17711  28657  46368  75025 121393 196418 317811 514229

Probemos a generar la secuencia de 10 elementos, pero cuyos parámetros iniciales son diferentes:

• fibonacci(10,2,3)
• 2   3   5   8  13  21  34  55  89 144

 

Descomposición según el teorema de Zeckendorf

Vista la función que nos permite obtener la serie de Fibonacci para un determinado número de elementos (que utilizaremos ahora), pasamos a ver cómo programar la obtención de un vector cuyos elementos representen la descomposición de Zeckendorf para un número dado.

Crearemos por tanto una función (zeckendorf) que reciba un único parámetro:

• val = valor numérico para el cual queremos obtener la descomposición de Zeckendorf

El algoritmo para obtener esta descomposición es bastante sencillo:

1. Buscamos una serie de Fibonacci cuyos elementos sean menores o iguales que el valor que queremos descomponer. Por ejemplo, si queremos obtener la descomposición del número 6, la serie (0,1,1,2,3,5,8) nos valdría, pues en este caso la descomposición de Zeckendorf para el número 6 sería (5,1), elementos presentes en la serie de Fibonacci para la longitud que hemos determinado.
2. De la serie que tenemos, buscamos el mayor número menor o igual que nuestro número a descomponer.
3. Una vez lo tenemos, restamos a nuestro número el valor de Fibonacci que hemos seleccionado.
4. Buscamos ahora el siguiente mayor valor de la serie que sea menor o igual que dicho valor resultante.
5. ... repetimos hasta que tengamos todos los valores.

Y la programación que vamos a realizar es, en esencia, esto mismo:

En un primer bucle while buscaremos una serie de Fibonacci lo suficientemente larga como para incluir el mayor elemento que sea menor o igual que nuestro número que queremos descomponer:

• Para conseguir esto, la condición de salida del bucle es que tengamos una serie (el vector fib) en el que algún elemento sea mayor que el número que estamos buscando.
• Mientras esto no se cumpla, seguiremos iterando incrementando la longitud del vector fib con la serie de Fibonacci, para el cual solicitaremos a la función fibonacci que cada vez nos devuelva una serie con 10 elementos más que la anterior. 

Una vez tenemos el vector con una serie de Fibonacci lo suficientemente grande para extraer de ella los elementos de la descomposición, realizamos otro bucle while para el cual comparamos que la suma de los elementos del vector resultante (zeck) que estamos rellenando a cada paso sea en efecto el valor del nnúmero a descomponer.

• Para poder extraer estos elementos, en cada iteración buscamos cuáles (which) elementos del vector son mayores que la cantidad restante de la suma de elementos que nos falta para obtener el valor resultado esperado.
• Este which nos devuelve un vector con los indices de las posiciones del vector consultado. Si lo ordenamos (sort) en orden descencente, el primer elemento de este vector ordenado será la posición del vector en la serie de Fibonacci que representa el siguiente elemento de la descomposición de Zeckendorf que estamos buscando.
• Tras obtener el elemento, actualizamos el valor actual de la suma y repetimos el bucle hasta obtener todos los elementos cuya suma equivalen el valor objetivo.

Aquí está el código con la función:

 # ------------------------------------------------ # zeckendorf # ------------------------------------------------ zeckendorf <- function(val) { zeck <- c() zsum = 0 fib <- fibonacci(8) n <- 1 # Encontrar serie de Fibonacci adecuada while(length(which(fib > val))==0){ fib <- fibonacci(n*10) n <- n+1 } # Obtener descomposición de Zeckendorf while(zsum < val) { zfib <- which(fib <= (val-zsum)) zfib <- sort(zfib, decreasing = TRUE) zeck <- append(zeck, fib[zfib[1]]) zsum <- zsum + fib[zfib[1]] } return(zeck) }

Pongamos a prueba nuestra función:

• zeckendorf(8)
• 8
  
• Siendo la serie de Fibonacci:  (0 1 1 2 3 5 8)
• zeckendorf(7)
• 5  2
• Siendo la serie de Fibonacci:  (0 1 1 2 3 5 8)
• zeckendorf(88)
• 610 233 34 8 3
• Siendo la serie de Fibonacci: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)

 

Resumen

Hemos visto dos ejemplos sencillitos que nos permiten poner en práctica la creación y manipulación de vectores, su ordenación y la consulta de sus elementos por índice.

Además, hemos puesto en práctica los tres bucles lógicos que más suelen utilizarse (for, if, while).

Como en casi cualquier problema que se programe, esta solución no es única, y puede abordarse de muchas maneras. Igualmente, en otros lenguajes de programación se puede realizar un desarrollo bastante similar en función de las funciones internas que tenga cada lenguaje para la manipulación lógica de objetos y valores, pero lo importante aquí es saber volcar un razonamiento lógico a la hora de implementar lo que queremos hacer para que la máquina nos de el resultado esperado.

Cualquier comentario, replanteamiento del código o duda es más que bienvenido.