1. Introducción

Owens (2008) afirma que un número primo es un entero positivo $p$ el cual tiene exactamente dos divisores positivos distintos. Por otro lado Prieto (2013) añade que un número natural es primo si tiene exactamente dos divisores distintos: 1 y él mismo.

Una lista parcial de los primeros números primos es la siguiente: 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, ...

Según Rowland (2008), persiste la creencia de que los números primos están distribuidos de manera aleatoria y esa intuición ha llevado a los matemáticos; a despertar su interés sobre aquellas funciones que generan primos de manera confiable.

Xiao (2015), comenta que las evidencias del conocimiento sobre número primos se remontan a la civilización egipcia, y desde entonces se han propuesto diversas fórmulas que generan solo algunos números primos.

2. Funciones Generadoras de Números Primos

Ribenboim (1996) menciona que hay tres clases de funciones generadoras de números primos y que las podemos englobar en tres clasificaciones principales:

• Una función que produce al enésimo número primo f(n) = P_n.

• Una función f(n) que genera siempre un primo, y f(n) ≠ f(m) para m ≠ n

• El conjunto de valores positivos de f es igual al conjunto de números primos.

2.1. Ejemplos de Funciones Generadoras

Un ejemplo de funciones conocidas para hallar al enésimo número primo es la fórmula de Willans (1964) que se aprecia en la ecuación 1.

La expresión se basa en el teorema de Wilson (1770) el cual afirma que un número $n$ es primo, si $\frac{(n-1)!+1}{n}$ produce a un entero.

La desventaja de este tipo de funciones es su inviabilidad en la práctica computacional, el cálculo de la operación factorial es un inconveniente cuando se trabaja con números muy grandes.

Como ejemplo de funciones que generan siempre primos, pero no necesariamente al conjunto de los números primos, tenemos: $f\left(n\right)=17$ para toda $n>1$.

La función anterior (Owens, 2008) solo produce un número primo; que al describirse como una función constante para cada valor de $n$, siempre producirá al mismo número primo 17.

Rowland (2008) afirma que es raro encontrar funciones que no hayan sido diseñadas para generar primos, y una de ellas es el polinomio de Euler, que es capaz de generar un conjunto finito de números primos partiendo del conjunto base de los números enteros positivos. Para el intervalo $0\le n\le 39$ la siguiente expresión genera cuarenta números primos: $f\left(n\right)=n^2+n+41$

En la siguiente lista se muestra los cuarenta números primos generados por el polinomio de Euler:

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601.

No obstante, este tipo de expresiones solo generan números primos para un intervalo pequeño. Morales (2013) afirma que no existen polinomios que den valores primos para todos los números naturales (excluyendo, evidentemente, a los polinomios constantes que sean igual a un número primo).

3. Propuesta de una función para generar Números Primos

El tema principal de este trabajo se centra en la propuesta de una fórmula basada en la función divisor para generar números primos. La fórmula se basa en la definición de número primo para construirla.

Un primer acercamiento a la fórmula propuesta se da en el verano de 2016 cuando la enciclopedia en línea de secuencias enteras (oeis.org) aprueba el alta de una fórmula como aporte a la entrada A061397 la cual lleva como título: “Secuencia de función característica de primos multiplicados por componentes N, los números naturales”, véase la figura 1.

La fórmula registrada en la enciclopedia en línea de secuencias enteras está relacionada con el concepto de divisores de un número entero, en particular, con otro registro de la misma enciclopedia de secuencias enteras cuyo identificador es A001065 y que lleva como título: “Suma de divisores propios (o partes alícuotas) de $n$ : suma de divisores de $n$ que son menores que $n$ ”.

Los primeros términos de la secuencia A001065 son:

0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13, 28, 1, 42, 1, 31, 15, 20, 13, 55, 1, 22, 17, 50, 1, 54, 1, 40, 33, …

Para entender la esencia de la secuencia A001065, se toma como ejemplo el caso$n=4$, que al sustituirlo en $a\left(n\right)$ se obtiene$a\left(4\right)=3$. Esto se deduce porque los divisores de 4 son: 4, 2, 1, pero solo se suman los menores a tal número (por la definición de la secuencia A001065), en este caso$a\left(4\right)=2+1=3$.

Observamos que la secuencia antes descrita produce al número uno cuando $n$ es primo, esto nos permite darle forma a una expresión como función prototipo para generar ceros y primos como se muestra en la expresión:

$a\left(n\right)=n·\left[\frac{1}{A001065\left(n\right)}\right]\mathrm{para\; toda},n>1$

La esencia de la fórmula de la figura 1 es realizar una división entre el uno y la suma de divisores de $n$ menores a$n$, para luego aplicar la función piso, esto conlleva a que se obtenga uno cuando $n$ sea un número primo y cero para un número compuesto. De esta manera la expresión produce a la secuencia:

0, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0, 0, 23, 0, 0, 0, 0, 0, 29, 0, 31, 0, 0, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 0, 0, 47, 0, 0, 0, 0, 0, 53, 0, ...

Asumiendo la esencia de la función prototipo: nuestro enfoque se centra en la construcción de una función para contabilizar al número de divisores propios de un entero positivo $n$ mayor que cero (función divisor) la cual será parte fundamental de la fórmula propuesta en este trabajo.

La función divisor fue estudiada por Ramanujan (Sloane, 2020), y se representa como $d\left(n\right)$ o $tau\left(n\right)$ y genera el número de divisores de$n$. Una lista parcial de los elementos que genera la función divisor es la siguiente:

1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, ...

4. Construcción de la fórmula propuesta

Primeramente se desarrolló una fórmula para la función divisor $d\left(n\right)$ la cual devuelve el número de divisores de$n$. Para ello se trabajó con la operación resta y división, y las funciones matemáticas: techo y parte fraccionaria, además de utilizar una sumatoria:

Como los números primos son los únicos que tienen dos divisores para toda$n>1$, se puede construir una expresión que genere números primos y ceros usando la ecuación (2), al implementar una multiplicación, una división y una función piso:

Así, al sustituir (2) en (3) el resultado final y propuesta como función $a\left(n\right)$ con $n>1$ se define como:

Por lo tanto tenemos:

$a\left(n\right)=\left\{\begin{array}{lr}0& \mathrm{si\; n\; es\; compuesto}\\ n& \mathrm{si\; n\; es\; primo}\end{array}\right.$

4.1. Demostración

Se toma en consideración la sumatoria de la fórmula (2) que se propuso en la sección: “Construcción de la fórmula propuesta: 4” , para expresarla en términos de la definición de la función parte fraccionaria (Weisstein, S.F.) que se denota como $n$.

Para $n\ge 0$ $\left\{n\right\}=n-⌊n⌋$

Se tiene entonces la ecuación:

La expresión o ecuación (5) se escribe en términos de la función característica (que también es llamada función indicatriz) y que se define mediante la siguiente regla (Maximenko, S.F.):

Sea $X$ un conjunto y sea $A$ un subconjunto de$X$. La función característica de $A$ con respecto a $X$ es la regla:

$\chi A:a\to ℝ,\chi A\left(n\right)=\left\{\begin{array}{lr}0& \mathrm{n\; pertenece\; a\; X\; excepto\; A;}\\ 1& \mathrm{n\; pertencece\; a\; A}\end{array}\right.$

Por lo tanto, al definir nuestra ecuación (5) en base a la función característica y en referencia al conjunto de los números reales ($ℝ$) como al conjunto de los números naturales ($\mathbb{N}$) se tiene:

$\sum _{i=1}^n⌈\left\{\frac{n}{i}\right\}⌉=\sum _{i=1}^n\lceil \frac{n}{i}-\lfloor \frac{n}{i}\rfloor \rceil =\sum _{i=1}^n\chi ℝ-\mathbb{N}\left(\frac{n}{i}\right)$

Se procede a despejar la sumatoria de la fórmula (2):

La función techo de la sumatoria de la ecuación (6) satisface que:

$⌈\left\{\frac{n}{i}\right\}⌉=\left\{\begin{array}{lr}0& \mathrm{si\; n\; es\; divisible\; entre\; i}\\ 1& \mathrm{de\; otra\; manera}\end{array}\right.$

La ecuación (6) se cumple porque $\chi ℝ-\mathbb{N}\left(\frac{n}{i}\right)=0$ si y solo si: la división $\frac{n}{i}$ pertenece a los números naturales ($\mathbb{N}$) y $n$ es divisible entre $i$.

Por lo tanto, la fórmula (4) que se propuso en la sección de: “Construcción de la fórmula propuesta: 4” se escribe en términos de la ecuación (6) como se aprecia a continuación:

$a\left(n\right)=n·⌊\frac{2}{n-(n-d(n\left)\right)}⌋$

Al simplificar la expresión anterior se llega a la fórmula (3); la cual también se propuso en la sección de: “Construcción de la fórmula propuesta: 4”:

$a\left(n\right)=n·⌊\frac{2}{d\left(n\right)}⌋$

Se delimita la función divisor$d\left(n\right)>=2$, y de la fórmula (3) se reconoce que la función piso que se aplica a la división genera:

$a\left(n\right)=⌊\frac{2}{d\left(n\right)}⌋=\left\{\begin{array}{lr}0& \mathrm{si\; n\; es\; compuesto;}\\ n& \mathrm{si\; n\; es\; primo}\end{array}\right.$

Se escribe la función piso que se aplica a la división en la fórmula (3) en términos de la función característica y del conjunto de los números primos $\mathbb{P}\left(n\right)$

$⌊\frac{2}{d\left(n\right)}⌋=\chi \mathbb{P}\left(n\right)$

Finalmente la expresión (3) queda como:

$a\left(n\right)=n\chi \mathbb{P}\left(n\right)$

La cual corresponde a la función característica o indicatriz de los números primos multiplicada por los números naturales.

Así demostramos que la fórmula (4) genera números primos y ceros.

5. Computación en el programa de Wolfram Mathematica

En la figura 2 se muestra el procesamiento en el programa de Mathematica de la fórmula propuesta en este trabajo en el intervalo$2\le n\le 700$.

Código para su procesamiento en Mathematica en forma de tabla:

Table [n*Floor [2/ (n - Sum [Ceiling [FractionalPart [n/i]], i, 1, n])], n, 2, 700 ]

5.1. Tiempo de procesamiento de la función a(n) mediante la función Timing de Mathematica

En base a la tabla 1 se elaboró una gráfica para interpretar los resultados de procesamiento y compararlos con la complejidad algorítmica de la tabla 2. La tabla de complejidad algorítmica (López, 2019) es una métrica teórica que nos ayuda a describir el comportamiento de un algoritmo en términos de tiempo de ejecución y mediante la cual interpretaremos la complejidad computacional de la función$a\left(n\right)$.

A partir del análisis de los tiempos de procesamiento y la gráfica (ver figura 3) obtenida de los datos computados, y tomando como referencia a la tabla de complejidad algorítmica; se visualiza un orden de tipo exponencial $O\left(a^n\right)$ para la función$a\left(n\right)$.

Esto nos permite concluir que a medida de que se computen valores para$n>10000$; el coste computacional tendrá un aumento considerable, por ejemplo: para los primeros 20,000 valores de $n$ el tiempo de procesamiento es de 563.218 segundos lo cual representa el 381.24% en comparación al tiempo que conlleva procesar los primeros 10,000 valores de$n$. La función $a\left(n\right)$ es entonces una expresión inviable en la práctica computacional, no obstante, tiene un orden de complejidad algorítmico menor al orden factorial $O(n!)$ como el que maneja la fórmula de Willans (1964); la cual se basa en el teorema de Wilson y por ende hace uso de la operación factorial.

6. Conclusiones

• Se encuentra una alternativa a las clases de funciones generadoras de primos de Ribenboim (1996) pues se obtuvo una expresión matemática $a\left(n\right)$ que produce únicamente primos y ceros con la característica de que si $a\left(n\right)=n$ entonces $n$ es primo, de lo contrario $a\left(n\right)=0$ si $n$ es compuesto.

• La fórmula propuesta no está basada en el teorema de Wilson como le sucede a la propuesta por Willans (1964), Por lo tanto; la expresión presentada en este trabajo excluye de su estructura a la operación factorial.

• La función presentada en este trabajo no genera al enésimo número primo de tal manera que$f\left(n\right)={\mathbb{P}}_n$, como le sucede a las expresiones de Willans (1964) o de Gandhi (1971) la cual depende de la función Möbius$\mu \left(n\right)$, sin embargo, se logra obtener una fórmula que corresponde a la función característica de números primos multiplicada por los números naturales:$a\left(n\right)=n_{\chi }\mathbb{P}\left(n\right)$.

• Se logra también desarrollar una fórmula para la función divisor$d\left(n\right)$; la cual arroja el número de divisores de$n$, y cuya estructura es simple, al manejar la operación resta, y las funciones: techo y parte fraccionaria.

• La función $a\left(n\right)$ maneja operaciones elementales como: resta, multiplicación, división y las funciones: piso, techo y parte fraccionaria.

• No es una tarea sencilla encontrar funciones matemáticas que arrojen valores primos y ceros como es el caso del trabajo expuesto, por ende se recomienda buscar mejoras y derivaciones de la función hallada con el firme objetivo de optimizar recursos computacionales al disminuir su complejidad algorítmica.

Referencias

[1] Gandhi, J. M. (1971) Formulae for the nth prime, Proc. Washington State Univ. Conf. on Number Theory, Washington State Univ., Pullman, Wash., 96–106.

[2] López, J. A. (2019). Análisis de la complejidad de los algoritmos. Universidad de Sevilla España. Recuperado el 27 de Enero de 2021 de: https://www.cs.us.es/~jalonso/cursos/i1m-19/temas/tema-28.html.

[3] Maximenko, E. (S.F.) Función Característica o Indicatriz. Apuntes y ejercicios de matemáticas, ESFM del IPN. Recuperado el 14 de Febrero de 2021 de: http://esfm.egormaximenko.com/analysis/indicator_function_review_es.pdf.

[4] Morales, M. (2013). ¿Existen Polinomios que den valores Primos para todo Número Natural?. Gaussianos: Porque todo tiende a infinito. Recuperado el 18 de junio de 2020: https://www.gaussianos.com/existen-polinomios-que-den-valores-primos-para-todo-numero-natural/.

[5] Owens, M. (2008). ¿Is There a Formula that Generates Prime Generates Prime Numbers? A Sonoma State Math Colloquium. Estados Unidos de Norteamérica. Recuperado el 15 de Junio de 2020: https://web.sonoma.edu/math/colloq/primes_sonoma_state_9_24_08.pdf.

[6] Prieto, C. (2013). Los Números Primos: Hechos y Conjeturas. Segundo Encuentro con los Números Antioquia Colombia. Recuperado el 15 de Junio de 2020: https://paginas.matem.unam.mx/cprieto/phocadownloadpap/presentaciones/p.pdf.

[7] Ribenboim, Paulo (1996), The New Book of Prime Number Records, third edition, Springer-Verlag New York Inc.

[8] Rowland E. (2008). A Natural Prime – Generating Recurrence. Recuperado de ArXiv el 14 de Junio de 2020: https://arxiv.org/abs/0710.3217v3.

[9] Ruiz, S. Mathb.; Sondow (2014). Formulas for π(x) and the nth Prime. International Journal of Mathematics and Computer Science, 9, no. 2, 95–98.

[10] Sloane, N. J. A. (2020) On-Line Encyclopedia of Integer Sequences. A000005, A000040, A001065, A061397, A202018. https://oeis.org

[11] Weisstein, Eric W. (S.F.) "Fractional Part" de MathWorld: A Wolfram Web Recuperado el 28 de Enero de 2021 de: https://mathworld.wolfram.com/FractionalPart.html.

[12] Weisstein, Eric W. (S.F.b) "Prime Formulas" de MathWorld: A Wolfram Web Recuperado el 26 de Enero de 2021 de: https://mathworld.wolfram.com/PrimeFormulas.html.

[13] Willans, C. P. (1964). On formulae for the nth prime number, Math. Gazette 48, 413– 415.

[14] Wolfram, Stephen (2002). A New Kind of Science, Wolfram Media, Inc., Champaign, IL.

[15] Xiao, K. (2015). The Prime Number Formulas. Recuperado de ViXra el 15 de junio de 2020: https://vixra.org/pdf/1501.0129v1.pdf.