Una función que devuelve el mayor primo menor o igual que $n$

Question

Visión general

Mientras jugaba con números en mis estudios matemáticos de aficionado, encontré una notable y hermosa función big delta que devuelve el mayor número primo igual o menor que un número natural dado. Iterando esta función con $n = 1$ à $x$ obtiene la lista de todos los números primos comprendidos entre $1$ et $x$ .

Las funciones delta grande y pequeño

Dado un número natural $x$ con representación $d_t...d_1d_0=\sum_{i=0}^t d_i\cdot b^i$ en base $b$ definimos: $$ \delta(x,b):=\sum_{i=0}^t d_i $$ para que $\delta(x,b)$ es la suma de dígitos de $x$ 's base $b$ representación. Basándonos en esto definimos: $$ f(x):=\sum_{b=2}^{x+1}\delta(x,b) $$ y finalmente $$ \Delta(n):=\max_{2\leq x\leq n}\left[f(x)-f(x-1)\right] $$ Entonces parece que $\Delta(n)$ es el mayor primo menor o igual que $n$ .

Las funciones delta grande y pequeño descritas

Representación visual de la función big delta

Representación visual de la función big delta

Prueba experimental

Para probar lo anterior experimentalmente, escribí una implementación de las funciones delta pequeña y grande anteriores en Python. Está disponible en el siguiente repositorio de GitHub: Repositorio GitHub de Big Delta

Muestra de resultados

Lamentablemente, aquí no puedo introducir grandes cantidades de texto. Así que aquí está un ejemplo de salida de la secuencia de comandos anterior para un conjunto muy pequeño de grandes y pequeñas funciones delta para números de hasta 15.

$$ \begin{array}{|c|ccc|cc|} \hline n&\Delta&df&f&\delta_2&\delta_3&\delta_4&\delta_5&\delta_6 &\delta_7&\delta_8&\delta_9&\delta_{10} &\delta_{11}&\delta_{12}&\delta_{13}&\delta_{14} &\delta_{15}&\delta_{16}\\ \hline 1 & - & - & 1 & 1 \\ 2 & 2 & 2 & 3 & 1 & 2 \\ 3 & 3 & 3 & 6 & 2 & 1 & 3 \\ 4 & 3 & 2 & 8 & 1 & 2 & 1 & 4 \\ 5 & 5 & 5 & 13 & 2 & 3 & 2 & 1 & 5 \\ 6 & 5 & 3 & 16 & 2 & 2 & 3 & 2 & 1 & 6 \\ 7 & 7 & 7 & 23 & 3 & 3 & 4 & 3 & 2 & 1 & 7 \\ 8 & 7 & 2 & 25 & 1 & 4 & 2 & 4 & 3 & 2 & 1 & 8 \\ 9 & 7 & 5 & 30 & 2 & 1 & 3 & 5 & 4 & 3 & 2 & 1 & 9 \\ 10 & 7 & 5 & 35 & 2 & 2 & 4 & 2 & 5 & 4 & 3 & 2 & 1 & 10 \\ 11 & 11 & 11 & 46 & 3 & 3 & 5 & 3 & 6 & 5 & 4 & 3 & 2 & 1 & 11 \\ 12 & 11 & 0 & 46 & 2 & 2 & 3 & 4 & 2 & 6 & 5 & 4 & 3 & 2 & 1 & 12 \\ 13 & 13 & 13 & 59 & 3 & 3 & 4 & 5 & 3 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 13 \\ 14 & 13 & 7 & 66 & 3 & 4 & 5 & 6 & 4 & 2 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 14 \\ 15 & 13 & 9 & 75 & 4 & 3 & 6 & 3 & 5 & 3 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 15 \\ \hline \end{array} $$ donde en esta tabla $df$ es la abreviatura de $f(n)-f(n-1)$ et $\delta_b$ es la abreviatura de $\delta(n,b)$ .

Resultados experimentales

Aquí subo mis resultados experimentales: Repositorio Github de Big Delta

Contiene varias salidas para [n]={1...31}, [n]={1...1024}, hasta ~132'000.

Pregunta 1

Lo anterior no es más que una conjetura porque no he aportado una prueba formal. En consecuencia, mi pregunta principal es: ¿cómo podemos demostrarlo?

Pregunta 2

¿Es esta relación encontrada entre las sumas de dígitos en bases múltiples y el conjunto de números primos una relación bien conocida o se trata de un descubrimiento original?

Answer 1

El crecimiento de $\delta_b$

Escribamos $\delta_b(n)$ en lugar de $\delta(n,b)$ para referirse a la suma de dígitos de la base $b$ representación de $n$ . Entonces resulta que tenemos $$ \delta_b(n)=n-\beta_b(n)\cdot(b-1)\tag1 $$ donde $\beta_b(n)$ cuenta el número de veces $b$ divide $1,2,...,n$ (contados por multiplicidad). Para verlo, utilicemos la notación $n=(d_t,...,d_1,d_0)$ es decir $n=\sum_{i=0}^k d_i\cdot b^i$ y, a continuación, considerar $n$ de la forma: $$ n=(d_t,...,d_k,0,...,0), \quad\text{where }d_k\neq 0 $$ para tal $n$ tenemos $$ n-1=(d_t,...,d_k-1,b-1,...,b-1) $$ Comparando los que tenemos: $$ \delta_b(n)=\delta_b(n-1)+1-k\cdot(b-1) $$ Por lo tanto $\delta_b(n)$ es $1$ superior a $\delta_b(n-1)$ menos $b-1$ veces la multiplicidad $k$ de la frecuencia $b$ divide $n$ . Si $b$ NO divide $n$ tenemos $$ \delta_b(n)=\delta_b(n-1)+1\tag2 $$ Por lo tanto, como $n$ aumenta en $1$ repetidamente, $\delta_b(n)$ se incrementa en $1$ cada vez (a partir de $\delta_b(1)=1$ ), pero siempre que $n$ es divisible por $b$ por una multiplicidad de $k$ entonces $k$ veces $b-1$ se resta. La demanda expresada en $(1)$ sigue. Obsérvese también que $$ \delta_b(b)=1\tag3 $$

Estos resultados conducen a la siguiente demostración:

---

Prueba de la corrección del algoritmo

Sea $p$ sea un número primo. Entonces $$ f(p)-f(p-1)=p\tag4 $$ Esto puede verse considerando en primer lugar $\delta_b(p)$ vs. $\delta_b(p-1)$ para $b\leq p-1$ . Puesto que tales $b$ no divide $p$ tenemos de $(2)$ que $$ \delta_b(p)=\delta_b(p-1)+1 $$ y por lo tanto $$ \sum_{b=2}^{p-1}\delta_b(p)=p-2+\sum_{b=2}^{p-1}\delta_b(p-1) $$ Ahora bien, puesto que $\delta_p(p)=1$ et $\delta_p(p-1)=p-1$ que de nuevo tiene una diferencia de $p-2$ se deduce que $$ \begin{aligned} f(p)-p&=f(p)-\delta_{p+1}(p)\\ &=\sum_{b=2}^p\delta_b(p)\\ &=\sum_{b=2}^p\delta_b(p-1)\\ &=f(p-1) \end{aligned} $$ y la demanda en $(4)$ sigue.

---

Si por el contrario $n$ es compuesto teniendo algún $2\leq q<n-1$ como factor, tenemos $$ \sum_{b=2}^{n-1}\delta_b(n)<n-2+\sum_{b=2}^{n-1}\delta_b(n-1) $$ porque $\delta_q(n)<\delta_q(n-1)+1$ por ecuación $(1)$ . De ahí que la conclusión esta vez sea $$ f(n)-n<f(n-1)\iff f(n)-f(n-1)<n $$ con lo que termina la demostración de la proposición.

---

Observación final: complejidad del algoritmo

Tenga en cuenta que su algoritmo propuesto no es muy eficiente como prueba de primalidad. Uno tiene que llevar a cabo $n$ base $b$ conversiones de $n$ et $n-1$ conversiones de $n-1$ para comprobar si $$ f(n)-f(n-1)=n $$ en cuyo caso $n$ es un número primo. En comparación, se podría calcular simplemente el dígito único $d_0$ de la representación de $n$ en todas las bases $b=2,...,\lfloor\sqrt n\rfloor$ y si ninguno de ellos fuera cero ya sabríamos que $n$ no es divisible por $1<b<n$ . Por lo tanto $n$ sería primordial. Así que en este sentido su algoritmo desperdicia mucho trabajo. Y hay algoritmos aún más rápidos que ese.

Si el objetivo es calcular $\Delta(n)$ el mayor número primo menor o igual que $n$ el proceso es aún más pesado, ya que entonces tenemos que calcular $f(x)$ para todos $1\leq x\leq n$ .

---

Así que veo tu algoritmo más como un curioso resultado de teoría de números que como una propuesta de una forma eficiente de abordar la generación de números primos.