¿Es una función teórica numérica conocida?

Question

Me pregunto si existe un nombre para una determinada función y/o una bibliografía al respecto.

Para $x=1,2,3,4,5,6,\ldots$ , dejemos que $f(x)$ sea la longitud de la secuencia más corta de enteros consecutivos que incluya $x$ para el que todos los números primos $\le\sqrt{x}$ ocurren como factores de números en la secuencia.

Por ejemplo, considere $f(1350)$ . Sabemos que $36^2<1350<37^2$ . En la secuencia de $1349=19\cdot71$ a través de $1364=2\cdot2\cdot11\cdot31$ se encuentra la primera $11$ números primos $2,3,5,7,11,13,17,19,23,29,31$ y el siguiente es $37$ que es mayor que la raíz cuadrada de todos los números de $\{1349,\ldots,1364\}$ . Por lo tanto, $f(1350)=16$ .

$$ \begin{array}{crlc} \text{count} & & \text{factorization} & \text{small primes seen so far} \\ \hline 1 & 1349 & = 19\cdot71 & 19 \\ 2 & 1350 & = 2\cdot3\cdot3\cdot3\cdot5\cdot5 & 2,3,5,19 \\ 3 & 1351 & = 7\cdot191 & 2,3,5,7,19 \\ 4 & 1352 & = 2\cdot2\cdot2\cdot13\cdot13 & 2,3,5,7,13,19 \\ 5 & 1353 & = 3\cdot11\cdot41 & 2,3,5,7,11,13,19 \\ 6 & 1354 & = 2\cdot677 & \text{ditto (no new ones this time)} \\ 7 & 1355 & = 5\cdot271 & \text{ditto} \\ 8 & 1356 & = 2\cdot2\cdot3\cdot113 & \text{ditto} \\ 9 & 1357 & = 23\cdot59 & 2,3,5,7,11,13,19,23 \\ 10 & 1358 & = 2\cdot7\cdot97 & \text{ditto} \\ 11 & 1359 & = 3\cdot3\cdot151 & \text{ditto} \\ 12 & 1360 & =2\cdot2\cdot2\cdot2\cdot5\cdot17 & 2,3,5,7,11,13,17,19,23 \\ 13 & 1361 & = 1361 & \text{ditto} \\ 14 & 1362 & = 2\cdot3\cdot227 & \text{ditto} \\ 15 & 1363 & = 29\cdot27 & 2,3,5,7,11,13,17,19,23,29 \\ 16 & 1364 & = 2\cdot2\cdot11\cdot31 & 2,3,5,7,11,13,17,19,23,29,31 \end{array} $$ El " $\text{count}$ " es $16$ , por lo que es $f(1350)$ . Así de larga tuvo que ser la secuencia para conseguir todo $11$ de los primos "pequeños", es decir, de los primos no mayores que $\sqrt{1350}$ .

Una razón para preocuparse por esto es que si uno quiere factorizar un entero en este rango, uno mira sus distancias desde cada uno de esos primeros $11$ primos para decidir si es divisible por alguno de ellos, y si no, entonces es primo. Así que no es necesario buscar más allá de esa secuencia.

Me inclino por tomar $f(1)$ , $f(2)$ y $f(3)$ para ser $0$ ya que ningún número primo es $\le$ las raíces cuadradas de esos números. Pero eso requeriría una ligera reformulación de la definición de $f$ y no estoy seguro de cuál es la mejor manera de hacerlo.

Así que esta es mi pregunta: ¿Es una función conocida? ¿Tiene un nombre estándar? ¿Son interesantes los teoremas relativos a ella? ¿Qué libros dan cuenta de ella? (Confesión: aún no la he buscado en OEIS).

Answer 1

Quiero dar un comentario para la sección de propiedades interesantes.

Pero en primer lugar una fórmula (no efectiva): para todos los primos $p\leq \sqrt{x}$ dejar $$\begin{eqnarray}\delta_1(p) &=& -( x \bmod p), \\ \delta_2(p)&=&p+\delta_1(p). \end{eqnarray}$$ Estas son las distancias a los múltiplos de $p$ que están más cerca de $x$ . Entonces

$$f(x) = \min_{a,b \in \Bbb Z}\{b-a+1 \mid \forall p:a\leq\delta_1(p) \text{ or } \delta_2(p)\leq b\}$$

porque $x+a$ y $x-b$ son límites para la secuencia mínima.

Esto demuestra que la secuencia $(f(n))_{n \in \Bbb N}$ tiene la propiedad $|f(n)-f(n+1)|\leq 1$ $\forall n$ .

Prueba: Sea $n \in \Bbb N$ y seleccione $a(n), b(n)$ minimizando la ecuación anterior (la elección no es única en general), es decir $f(n)$ se determina por $a(n),b(n)$ . Hay dos casos:

• No hay ninguna prima $\sqrt{n} < p \leq \sqrt{n+1}$ : Entonces, si $n+1 \leq b(n)$ los dos límites son ya de la forma requerida (pero no necesariamente mínima) y si $n+1>b(n)$ elija $b(n)+1$ como límite. Esto muestra $f(n+1)-f(n)\leq 1$ . La misma consideración funciona también a la inversa (con $a$ en lugar de $b$ ) que muestra $f(n)-f(n-1)\leq 1$ .

• Hay un primer $\sqrt{n} < p \leq \sqrt{n+1}$ . Entonces $p^2 = n+1$ Por lo tanto $p \mid n+1$ y no tenemos que preocuparnos de la divisibilidad por $p$ para nuestros límites. Así que podemos elegir los límites como los elegidos en la primera parte de la prueba.

Esto sugiere investigar la secuencia $(f(n+1)-f(n))_{n\in \Bbb N}$ en lugar de $f$ .