Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
.
Conteo de los números primos en sucesiones aritméticas
122
https://doi.org/10.47460/minerva.v4i10.111
Conteo de los números primos en sucesiones
aritméticas
Recibido (
1
3/07/2022), Aceptado (
09/01/2023)
Resumen.
-
En el presente
trabajo
se presentan los elementos teóricos que fundamentan el cálculo de la
función contadora de números primos, π(x), basados en propiedades de las sucesiones (6n
-
1) y (6n+1), n ≥ 1.
Como resultado se exponen criterios suficientes
de
primalidad
para
los términos de ambas sucesiones que
sustentan un algoritmo computacional determinístico que reduce la cantidad de operaciones en el cálculo de
la función π(x) al exonerar del análisis a todos los múltiplos de 3
;
y en el proceso de análisis de primalidad de
un término particular, se excluyen las divisiones por el factor 3. Tal algoritmo es posible aplicarlo en la
búsqueda de números primos en cada sucesión por separado, posibilidad que permite reducir
aproximadamente a la mitad el tiempo de búsqueda de números en aplicaciones prácticas.
Palabras clave:
Función
contadora de números primos, criterio de primalidad, algoritmo determinístico,
términos puros en sucesiones aritméticas, términos mezclados en sucesiones
aritméticas
.
Counting prime numbers in arithmetic sequences
Abstract
.
-
This paper presents the theoretical elements that support the calculation of the prime number
counting function,
π
(x), based on properties of the sequences (6n
-
1) and (6n+1), n
≥ 1. As a result
,
Sufficient
primality criteria are exposed for the terms of both sequences that support a deterministic computational
algorithm that reduces the number of operations in
calculating
the function
π
(x) by exonerating all multiples
of 3 from the analysis. In analyzing the primality of a particular term, the divisions by factor 3 are excluded.
Such an algorithm can be applied to the search for prime numbers in each sequence separately, a possibility
that allows approximately
half
the time of number search in practical applications.
Keywords:
C
ounting function of prime numbers, primality criterion, deterministic algorithm, pure terms in
arithmetic seq
uences,
mixed terms in arithmetic sequences.
Pedro R. Suárez Surí
https://orcid.org/0000-0002-5237-7606
pedro1951rivero@gmail.com
Investigador independiente
Quito, Ecuador
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
123
I.
I
NTRODUCCIÓN
La función
(
)
que cuenta la cantidad de números primos hasta el número real x, ha motivado a muchos
investigadores a buscar una solución que permita calcular este número con exactitud. Este empeño ha
impulsado el desarrollo de la teoría de los números abordando el problema por distintos enfoques y se han
establecido algoritmos determinísticos
o
probabilísticos
, entre los cuales se encuentran los siguientes:
a)
El algoritmo de AKS (Manindra Agrawal
,
Neeraj Kayal
y
Nitin Saxena) establecido en el 2002
[1],
es un
algoritmo de primalidad determinista en tiempo polinomial. Es el primer criterio de primalidad con
estas características, a pesar de lo cual no es lo suficientemente eficiente para ser utilizado
ampliamente en aplicaciones prácticas.
b)
El test de primalidad probabilístico de Miller
-Rabin
[2]
, por su naturaleza probabilística
,
tiene la
insuficiencia que puede proporcionar resultados erróneos con una probabilidad pequeña, a pesar de
lo cual es el test que más se
ha
utilizado
en aplicaciones criptográficas.
c)
El test de primalidad determinista de
Goldwasser-
Killian basado en curvas elípticas
[3]
, es una solución
con otro enfoque para el problema de primalidad. Según el
autor,
se
considera
uno de los métodos
más rápidos para probar primalidad de números naturales
.
d)
El test de primalidad determinista de secuencia de raíz digital tesla
Z
ollner es otro intento para resolver
el problema de primalidad parte de las sucesiones (6n
-
1) y (6n+1) y está basado en la teoría de la raíz
digital de Tesla Zollner. En este sentido
, “e
l Algoritmo de Primalidad desarrollado, tiene un
comportamiento funcional de orden cuatro
,
O (n4), el cual puede ser optimizado, mejorando las
condiciones iniciales de la estructura secuencial del algoritmo, ya que los procedimientos de cálculos
son sencillos, con simples operaciones aritméticas básicas”
[4].
Además de estas pruebas de primalidad existe
n
otros algoritmos y variantes de algunos de los mencionados
que aportan avances en este campo
,
sin e
mbargo,
hasta la fecha no se ha encontrado una solución
satisfactoria a tal problema.
En el presente artículo se presenta el resultado de otro intento de solución a esta problemática, basado en
propiedades elementales de las sucesiones aritméticas
(
6−1
)
y
(
6+1
)
.
En b
ase
a
propiedades
de estas
sucesiones
, se ha
n
establecidos
criterios suficientes para la primalidad de cualquiera de sus términos y
establecido
algoritmos computaciona
les
determinísticos
para calcular con exactitud la cantidad de números
primos en cada una de estas sucesiones hasta cualquier número x, en consecuencia
,
para la función contadora
de primos
(
)
.
Sin pretender comparar en
eficien
cia esta solución con los algoritmos existentes, se presenta
como otro camino en que se puede trabajar en la
búsqueda
de la solución al problema
.
En la exposición de los resultados de esta investigación se presentan las secciones: conceptos básicos y
propiedades, criterios de primalidad, fórmulas computacionales para el cálculo de la función
(
ℎ
)
,
algoritmos
computacionales
, resultados y conclusiones.
II.
D
ESARROLLO
A.
Conceptos básicos y propiedades
En este ep
ígrafe
se presentan algunas propiedades de las sucesiones enunciadas que permiten justificar
los criterios de primalidad que se
exponen
posteriormente.
Proposición 1.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
124
Todo número primo mayor que 3 es un término de la sucesión
(
)=();
o de la sucesión
(
)=
();∈
;≥
.
Demostración
Sea p>3 un número primo cualesquiera, entonces solo tiene los factores 1 y p, luego como p es impar y el
factor tres no está en p, entonces el factor 3 estará en
o en
y como
y
son
números pares entonces resulta:
Si
es múltiplo de tres entonces es múltiplo de 6 (par y divisible por 3) entonces
=
;
∈
;
luego
=
.
Si
es múltiplo de 3 entonces es múltiplo de 6 (par y divisible por 3) entonces
=
;
∈
;
luego
=.
En lo que sigue, los términos de las sucesiones
(
)=(
)
y
(
)=()
con n ≥ 1 se
denominan candidatos a primo de tipo A y tipo B respectivamente.
Algunas notaciones que se utilizan en este trabajo son
:
La cantidad de candidatos a primos menores o iguales a un número real x se denota por los símbolos Cp(x)
o Cp
a
(x) o Cp
b
(x), para referirse respectivamente al total de términos en ambas sucesiones hasta el número x,
a los términos de la sucesión (a
n
) hasta x, términos tipo A, o a los términos de la sucesión (b
n
), tipo B, hasta x.
La cantidad de candidatos a primos que son menores o iguales a un número real x se calculan por las
fórmulas:
(
ℎ
)
=[
]
,
(
ℎ
)
=
[
]
y
(
)
=
(
)
()=[
][
]
(1)
Estas fórmulas se obtienen directamente de las inecuaciones
≤
y
≤
, teniendo en
cuenta que los términos de estas sucesiones son números naturales.
La expresión [x] indica parte entera del número x o función piso de x.
De la proposición 1 se deriva que el conjunto de los candidatos a primos está constituido por los números
impares mayores o iguales a 5, que no son múltiplos de 3.
Otras notaciones:
(
)
indica la cantidad de candidatos a primos compuestos menores o iguales a x.
(
)
indica la cantidad de candidatos a primo del tipo
A
menores o iguales a
x,
que son
compuestos; de
igual forma
(
)
indica la cantidad de compuestos de tipo
B
menores o iguales a x.
∗
(
)
es la cantidad de números primos de tipo
A
y tipo
B,
menores o iguales a
x
excluyendo a 2 y 3. Y
∗
(
)
∗
(
)
indican la cantidad de primos en x, de tipo
A
o tipo
B
respectivamente.
De lo visto hasta aquí podemos afirmar que un candidato primo es un número primo o un número
compuesto
que no es par ni múltiplo de tres, luego si se puede calcular la cantidad de candidatos a primos
hasta un número real x que son compuestos, por diferencia con Cp(x) podemos determinar la cantidad de
primos hasta ese número x mediante las ecuaciones siguie
ntes:
(
)
=
∗
(
)
(
)
,
(
)
=
∗
(
)
(
)
(
)
=
∗
(
)
(
)
(2)
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
125
Veamos algunas propiedades de las sucesiones
(
)
(
)
.
B.
Propiedades de los términos de las sucesiones
(
)=(6−1)
y
(
)=(6+1
)
con n ≥ 1.
Pr
oposición 2
El producto de dos términos de la sucesión (
)
es un término de la sucesión (
)
.
Demostración
Sean n y m números naturales cualesquiera, luego
6−1
y
6−1
son dos términos cualesquiera de la
sucesión (
)
.
(
6−1
)(
6−1
)
=36−6−6+1=6
(
6−−
)
+1
(
)
(3)
Las proposiciones que siguen se demuestran de forma semejan
te
o
aplicando reiteradamente las
proposiciones planteadas con anterioridad.
Prop
osición 3
El producto de un término de la sucesión (
)
y un término de la sucesión (
)
es un término de la sucesión
(
)
Proposición 4
El producto de dos términos de la sucesión
(
)
es un término de la sucesión
(
)
.
Proposición 5
El producto de cualquier cantidad de términos de la sucesión
(
)
es un término de la sucesión
(
)
.
Proposición 6
El producto de una cantidad impar de términos de la sucesión
(
)
,tipo A, es un término tipo A.
Proposición 7
El producto de una cantidad par de términos tipo A es un término tipo B.
Proposición 8
Todo término compuesto de la sucesión (
)
puede ser representado como el producto de una cantidad
impar de factores primos tipo A y de cualquier cantidad de factores primos tipo B, pudiendo ser cero la
cantidad de factores tipo B.
Propiedad 9
Un término h de la sucesión
(
)
es compuesto si y solo si se puede expresar como producto de un término
tipo A y un término tipo B.
C.
Clasificación de los términos de las sucesiones (
)
(
)
según el tipo de sus factores primos
Los términos de las sucesiones (
)
(
)
se pueden agrupar en conjuntos disjuntos según el tipo de
factores que contienen:
Definición: Un término de las sucesiones
(
)
(
)
se denomina puro cuando solo contiene factores
primos tipo A o tipo B respectivamente.
Ejemplo:17, 125 =5
3
y 5
2
.11=275 son términos puros tipo A y 7, 49=7.7 y 91=7.13 son términos puros tipo B.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
126
Los términos compuestos de estas sucesiones que no son puros le denominamos mezclados.
Ejemplo: 35=5.7 es un término mezclado de
y 175=25. 7 es un término mezclado de
.
Los términos de la sucesión
que solo contienen factores primos tipo A, se denominan bpuroa.
Ejemplos:
=
,=∙11
Al conjunto de términos de la sucesión
que no son puros tipo B se denominan términos mezclados
tipo B.
Proposición 10
Todo término compuesto de la sucesión
se puede expresar como producto de dos términos tipo A
o como producto de dos términos puros tipo
B.
D.
Criterios para determinar si un término de las sucesiones
o
es un número primo
La forma más simple para determinar si un término h de estas sucesiones es compuesto es dividirlo por
todos los números primos menores o iguales a su raíz cuadrada; pero esto tiene el inconveniente del costo
computacional que genera el espacio necesario para guardar los números primos conocidos y luego recuperar
la información sobre la primalidad de los términos necesarios de estas sucesiones para utilizarlos en las
operaciones requeridas; por tal motivo en este trabajo se presenta una solución que no necesita de la
condición de primalidad de los términos de estas sucesiones; pero basta
ría
guardar los primos encontrados
hasta
√
y llamarlos en el algoritmo cuando se necesiten, es decir
,
los criterios son válidos si se divide solo por
los números primos, cuestión que será conveniente cuando se trabaje con números grandes.
Al menos para números pequeños (menores a 32 401) resulta más ventajoso trabajar con todos los
términos de las sucesiones
que son menores que
√
, que recuperar la información de los primos
encontrados para dividir solo por ellos; comportamiento que pudiera cambiar con números grandes.
Presentamos continuación algunos criterios que permiten determinar con exactitud si un término de las
sucesiones anteriores es primo o compuesto.
E.
Primos en la sucesión
=
1
;
∈ℕ
En base a las propiedades de los términos de las sucesiones
y
, se pueden establecer los criterios
siguientes:
Criterio 1
Criterio suficiente para la condición de compuesto de un término de la sucesión
en base a los
candidatos a primo de tipo
B.
Sea
=1;∈ℕ
. Si
∃
≤
∶
=1
entonces h es
compuesto de tipo A.
Demostración
Supongamos que
∃
≤
:
=1
, esto significa que en
los
c
andidatos a primo tipo B se incrementan en una unidad, es decir, entre
y
existe un candidato
primo
,
tipo B, tal que
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
127
<
, multiplicando por
se obtiene
<
, como los términos consecutivos de la
sucesión
se diferencian en 6 unidades y h es un término de
y por la propiedad 2,
también es
un término de
entonces
es un compuesto de la sucesión
.
La suma de las diferencias
∑
(4) del criterio anterior indica la cantidad de
factores primos tipo A distintos que existen en la descomposición en factores del número h, lo cual determina
cuántos productos distintos de dos factores originan al mismo número h, es decir, si queremos contar cuántos
compuestos existe en la sucesión
hasta h, se
contaría
T-
1 compuestos de más; sin embargo si se suma el
signo(T) para todos los términos de la sucesión
hasta h, se obtendría la cantidad exacta de compuestos
hasta H. Pero esta solución tiene un costo computacional mucho mayor que los criterios que se presentan a
continuación.
El contrarrecíproco del criterio 1 es una condición suficiente de primalidad para los términos de
:
Criterio 2
Criterio de primalidad
Sea
1;∈ℕ.
Si
∀
con
se cumple
0
entonces h es un
número primo.
El Criterio 1 para la condición de compuesto de un término de la sucesión
, se ha
plante
ado utilizando
los Cpb, un criterio semejante también se puede plantear en función de los Cpa.
Criterio 3
Sea
1;∈ℕ
. Si
∃
7
∶
1
entonces h es compuesto
de tipo A.
Demostración
S
upongamos que
∃
7
:
1
, esto significa que en
los
candidatos a primo tipo A se incrementan en una unidad, es decir, entre
y
existe un candidato
primo
,
tipo A, tal que
<
, multiplicando por
se obtiene
<
, como los términos consecutivos de la
sucesión
se diferencian en 6 unidades y h es un término de
y por la propiedad 2,
también es
un término de
ent
onces
es un compuesto de la sucesión
.
Mediante la aplicación de estos criterios se puede elaborar un algoritmo para determinar la condición de
compuesto o primo de un término h de la sucesión
.
Para el caso de los términos de la sucesión
, la diferencia
se puede transformar aplicando las fórmulas para el cálculo de los candidatos a
primo; permitiendo de este modo operar con números más pequeños para reducir la complejidad de los
cálculos en el algoritmo correspondiente.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
128
=
ℎ
ℎ
=
ℎ
/
ℎ
=
ℎ
ℎ
=
=
=
(5)
Propiedad 11
Si el cociente
∈
ℕ
entonces la diferencia
=
=.
Demostración
Para cada
∈
se tiene una sucesión aritmética
donde
y
son términos
consecutivos con una diferencia
tal que 0<
<
Supongamos que
∈
ℕ
. En este caso
=
; pero
=
luego
==
De forma semejante se cumple:
Propie
dad 12
Si el cociente
∈
ℕ
entonces la diferencia
=
=.
La d
emostración
sigue la misma vía que en la propiedad 11
De acuerdo con este resultado las diferencias
=
=
se puede sustituir en los criterios
enunciados anteriormente por
=
⌊
⌋=0
(En este caso si
=0
el término h es compuesto y si
para todos los
se cumple que
≠0
entonces h es primo.
)
También se puede sustituir por la expresión
equivalente
=
=0
o
=
=0
que son expresiones respectivamente
equivalen
tes a
∈
ℕ
y
∈
ℕ
.
S
i se aplica la propiedad 9, que plantea que todo término compuesto h de
se puede expresar como
ℎ=
, se puede reducir la cantidad de operaciones. En lugar de calcular todas las divisiones por los
con
≤
7
o por los
con
≤
5
, es posible calcular los cocientes solo para
≤
√
ℎ
y los
≤
√
ℎ
debido
a que si
≤
√
ℎ
entonces
≥
√
ℎ
, y viceversa, si
≤
√
ℎ
entonces
≥
√
ℎ
, de acuerdo con esto y la
transformación realizada a la diferencia d, el criterio para la condición de compuesto de un término de la
sucesión
, se puede expresar de la forma siguiente:
Criterio 4
Un término h de la sucesión
es compuesto si
∃
con
≤
√
ℎ
tal que
=0
o
∃
con
≤
√
ℎ
se cumple
=0
.
Este criterio se puede expresar utilizando las expresiones equivalentes
=0
y
=0
respectivamente.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
129
Criterio 4.1
Un término h de la sucesión
es compuesto si
∃
con
≤
√
tal que
=0
o
∃
con
≤
√
=0
.
Criterio 5
Un término h de la sucesión
es primo si y solo si
∀
con
≤
√
se cumple
≠
0
y
∀
con
≤
√
se cumple
≠0
.
F.
Primos en la sucesión
=
1
;
∈ℕ
Para determinar si un término de la sucesión
es compuesto se tiene en cuenta que todo término
compuesto de esta sucesión es un término mezclado o es un término puro tipo B.
C
riterio para los términos de la sucesión
Todo término mezclado h de
se obtiene como el producto cada término
de
por todos los
Cpa
≤
. Estos generan los términos mezclados de
, que pueden ser términos Bapuros, que son aquellos
que solo contienen factores primos tipo A o términos tipo B mezclados que contienen factores primos tipo A
y factores primos tipo B.
Criterio 6
Sea
=1;∈ℕ
. Si
∃
≤
5
∶
=1
o
∃
≤
7
∶
=1
entonces h es compuesto.
Demostración
Caso 1
Sea h un término de la sucesión
.
Supongamos que
∃
≤
5
:
=1
, esto significa que entre
y
existe un candidato primo
tipo A, tal que
<
≤
, multiplicando por
se obtiene
<
≤
, como los términos consecutivos de la
sucesión
se diferencian en 6 unidades y h es un término de
y
también es un término de
entonces
=
es un compuesto mezclado de la sucesión
.
(
≠
porque la diferencia
=
≤1,2
∀
luego si
≤
resulta que
=0
)
Caso 2
Supongamos que
∃
≤
7
:
=1
, esto significa que entre
y
existe un candidato primo
tipo B, tal que
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
130
<
≤
, multiplicando por
se obtiene
<
≤
, como los términos consecutivos de la
sucesión
se diferencian en 6 unidades y h es un término de
y
también es un término de
entonces
=
es un compuesto de la sucesión
.
El contrarrecíproco del criterio anterior es el criterio de primalidad para un término de la sucesión
.
Criterio 7
Sea
=;∈ℕ
. Si
∀
≤
5
∶
=0
y
∀
≤
7
∶
=0
entonces h es un número primo.
Para el caso de los términos de la sucesión
la primera proposición del criterio 6 se transforma en:
=
=
/
/=
=
=
(6)
La segunda condición del criterio 6 se transforma en:
=
=
/
/=
=
=
(7)
La
primera
condición del criterio 7 es equivalente a la propiedad 1
2.
Propiedad 12
Si el cociente
∈
ℕ
entonces la diferencia
=
=
.
(La d
emostración
es semejante a la realizada en el criterio 11.)
La segunda condición del criterio 7 es equivalente a la propiedad 13.
Propiedad 13
Si el cociente
∈
ℕ
entonces la diferencia
=
=
.
(La d
emostración
es semejante a la realizada en el criterio 11.)
El criterio de primalidad de un término de la sucesión
resulta de la negación del criterio 4 y el empleo
de las siguientes equivalencias:
La expresión
∈
ℕ
es equivalente a
=0
o
=0
La expresión
∈
ℕ
es equivalente a
=0
o
=0
Criterio de primalidad de los términos de la sucesión
Criterio 5
Un término h de la sucesión
es primo si
∀
con
≤
√
resulta
=0
y
∀
con
≤
√
resulta
=0
.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
131
III.
M
ETODOLOGÍA
La metodología empleada ha consistido en el análisis de las sucesiones
y
en cuanto a sus
propiedades y su relación con los números compuestos hasta encontrar la regularidad de la formación de los
números compuestos a partir de los términos de estas sucesiones
y
establecer criterios suficientes de
primalidad sustentados en propiedades elementales. Posteriormente se procede a la implementación
computacional de los criterios y análisis de los resultados.
IV.
R
ESULTADOS
A.
Fórmulas computacionales para el cálculo de la función
Según estos resultados se puede definir la función
med
iante una fórmula computacional exacta;
antes se definen las funciones
y
que determinan la cantidad de primos acumulados las
sucesiones
y
respectivamente
hasta el número h.
Sea
∑
∑
√
∑
√
8
(8)
Donde
;
Sea
∑
∑
∑
√
√
8
(9)
Donde
;
;
El 1 q
ue
se resta de K corresponde al compuesto que existe en cada sucesión hasta 43.
La sumatoria indica la cantidad de compuestos acumulados desde 47 hasta h.
Función
2
(10)
El sumando 2 se refiere a los primos 2 y 3 que no se calculan en las fórmulas anteriores.
Las diferencias de las partes enteras que aparecen en estas fórmulas solo pueden tomar valores 1 o 0, lo
que permite, en su implementación computacional, abandonar el ciclo correspondiente cuando aparece el
primer 1; en tal caso no es necesario utilizar la función signo.
B.
Implementación de los criterios expuestos en el cálculo de la función
La implementación de los criterios presentados anteriormente para calcular la función
se ha
realizado mediante programación en
VBA
de Excel y se ha repetido el algoritmo para todos los términos de
las sucesiones
y
desde 47 hasta 32401.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
132
Para
la implementación del procedimiento para cualquier número real
≥3
basta entrar el valor de x y
calcular k mediante las ecuaciones
=
[
]
o
=
[
]
según se busque los valores de
(
ℎ
)
o
(
ℎ
)
respectivamente.
A
lgoritmo de primalidad
para
los términos de la sucesi
ón
(
)
H,l,k,m,n,a,b (enteros); d (double)
1-En
trar el valor de k y calcular
ℎ=
.
2-
Calcular
=
=
(
)
en un ciclo desde
=
hasta
=((
(
ℎ
)
)/)
.
Si
=
salir del ciclo y se pasa a 3.
3-
Si
=
se concluye: h es compuesto; Si
≠
se pasa a 4.
4-
Calcular
=
=
(
)
en un ciclo desde
=
hasta
=((
(
ℎ
)
)/)
.
Si
=
salir del ciclo y se pasa a 5.
5-
Si
=
se concluye: h es compuesto; Si
≠
se concluye: h es primo.
Algoritmo de primalidad
para
los términos de la sucesión
(
)
H,l,k,m,n,a,b (enteros); d (double)
1-
Entrar el valor de k y calcular
ℎ=
.
2-
Calcular
=
=
(
)
en un ciclo desde
=
hasta
=((
(
ℎ
)
)/)
.
Si
=
salir del ciclo y se pasa a 3.
3-
Si
=
se concluye: h es compuesto; Si
≠
se pasa a 4.
4-
Calcular
=
=
(
)
en un ciclo desde
=
hasta
=((
(
ℎ
)
)/)
.
Si
=
salir del ciclo y se pasa a 5.
5-
Si
=
se concluye: h es compuesto; Si
≠
se concluye: h es primo.
La implementación práctica de los algoritmos se realizó en una computadora Intel i3 4ta generación CPU
1.70 GHz 1.70 GHz con memoria RAM 12gb y HDD ssd sata 3.0
.
Sin pretender considerar los resultados siguientes como un análisis de la complejidad computacional, sí
pueden servir para valorar el comportamiento del tiempo del algoritmo analizado.
E
n el caso del algoritmo para los primos de la sucesión
(
=
)
se midió el tiempo para los valores
de K desde 8 hasta 5400 a intervalos de 166
términos
(términos desde 47 hasta 32399). A partir de la medición
de
los
tiempos
acumulados se establecieron modelos de regresión, resultando un modelo lineal (
=
(,8,,
estadísticamente significativo (p=0,000; R
2
=0,998) y un modelo potencial
(
=
,2
, estadísticamente significativo (p=0,000; R
2
=0
,998. Un modelo logarítmico resultó
significativo con R
2
=0,84.
La estimación del tiempo del modelo potencial, para valores de K aproximadamente
superiores a 4000 tienden a ser menores que en el modelo lineal.
Considerando
lo planteado
en
[5],
pág. 210
sobre la comprobación del análisis de un algoritmo se observó que los cocientes Tiempo/K y Tiempo/(kln(k))
resultaron decrecientes por lo que se considera que ambos modelos sobreestiman el tiempo real, mientras
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
133
que el cociente
Tiempo/(k
^0,927)
es creciente, lo que indica que el modelo potencial
subestima
el tiempo
real.
C
ONCLUSIONES
El algoritmo anterior tiene la ventaja que para determinar el valor de
(
)
solo hay que considerar los
números impares
ℎ≥5
no divisibles por 3, que reduce
n,
aproximadamente en 1/6
la cantidad de
repeticiones del algoritmo y en cada h se excluye la división por 3 y sus múltiplos.
Los criterios presentados conducen a un algoritmo que calcula de forma exacta las funciones
(
ℎ
)
,
(
ℎ
)
y
(
ℎ
)
=2+
(
ℎ
)
+
(
ℎ
)
.
A
l realizar las divisiones utilizando el valor de k se disminuye el tamaño de los números objeto de análisis y
con ello se reduce el tiempo de cálculo
,
cuestión probada empíricamente para números pequeños (menores
a 32401). El algoritmo en su implementación, además de
realizarse
calculando los cocientes de todos los
términos de ambas sucesiones menores o iguales a
√
ℎ
,
se puede implementar utilizando solo los números
primos menores o iguales a
√
ℎ
encontrados en el proceso de análisis de ambas sucesiones
.
Para el uso práctico de est
os
algoritmos
en la búsqueda de números primos
,
se puede trabajar con
algoritmos separados
de
búsqueda
para
primos tipo A y tipo B, disminuyendo aproximadamente a la mitad el
tiempo de análisis de prima
lidad.
El algoritmo no se ha implementado para números grandes.
No se ha analizado la complejidad computacional de
los
algoritmos
asociados
a los criterios enunciados;
pero con independencia de la eficiencia que pueda tener el algoritmo, el enfoque presentado puede
representar otro sendero a explorar en la búsqueda de la solución al cálculo de la función
(
)
de forma
exacta y eficiente.
La combinación del análisis de primalidad sobre estas sucesiones con otros criterios de primalidad pudiera
incrementar la eficiencia de
los
algoritmos
en aplicaciones prácticas
.
Referencias
[1]
V. Arroyo, «Estudio sobre primalidad con el algoritmo AKS,» Madrid, 2020.
[2]
R. Martínez Zocón, L. Ortiz Céspedes, J. Horna Mercedes y A. Zavaleta Quipuscoa, «Algoritmos para pruebas de
primalidad,»
Selecciones Matemáticas,
vol. 1, nº 02, p. 8, agosto
-
diciembre 2014.
[3]
S. A. Ramírez Gajardo, Y. F. Vasquez Cea y C. Zenteno Acuña, «Curvas elípticas y test de primalidad,» Chillan, 2019.
[4]
Z. Castellanos y Á. SandoVal, «Test de primalidad de secuencia de raíz digital Tesla Zollner,»
ResearchGate,
p. 8,
septiembre 2022.
[5]
M. Allen Weiss, Estructuras de datos en Java, cuarta edición ed., Pearson Educación, S.A., 2013, 2013, p. 945.
Minerva Journal
ISSN-
e:
2697-3650
Vol.4
, Núm. 10, (pp.
122-134)
Suárez
P
. Conteo de los números primos en sucesiones aritméticas
134
P
edro Suárez
es
de
nacionalidad cubana, residente en Ecuador es
licenciado en educación en la especialidad de Matemática y
es
Magister
en Matemática aplicada, ha sido docente durante 53 años.