Número entero positivo más pequeño no coprimo a una colección de números enteros consecutivos

Question

Sea $n\in\mathbb{N}$ . Defina $f(n)$ el menor valor positivo de entero $m$ tal que existe un número entero positivo $k$ f $k+i$ no es relativamente primo de $m$ para cada $i=0,1,2,\ldots,n-1$ . Por ejemplo, $f(1)=2$ , $f(2)=f(3)=6$ y $f(4)=f(5)=30$ . Lo que sé es que, si $g(n)$ es el producto de todos los primos positivos menores que o igual a $n+1$ entonces $f(n)\leq g(n)$ (y $k=2$ d conseguir $g(n)$ ).

¿Es cierto que $f(2k)=f(2k+1)$ y $f(k)\mid f(k+1)$ f $k\in\mathbb{N}$ ? Para todos los números enteros $n\geq4$ , does $f(n)>n^2$ ¿aguantar? ¿Cuál es el comportamiento asintótico de $f(n)$ ? I la afirmación de que $f=g$ las demás cuestiones son triviales.

EDITAR 1: Según el comentario de san más abajo, $f \neq g$ . ¿Cuál es entonces la fórmula para $f$ ? Si $h(n)$ es el número entero positivo mínimo $k$ tal que $k+i$ no es relativamente primo de $f(n)$ para cada $i=0,1,2,\ldots,n-1$ ¿tenemos una fórmula para $h$ ? Además, parece que, para cualquier $l\in\mathbb{N}$ existe $n\in\mathbb{N}$ tal que $f(n)=f(n+1)=f(n+2)=\ldots=f(n+l-1)$ .

EDITAR 2: Sea $p_i$ sea el $i$ -ésimo número primo positivo más pequeño para $i\in\mathbb{N}$ . Una conjetura de Will es que $f\big(\mathsf{A058989}[n]\big)=p_1p_2\cdots p_n$ y $h\big(\mathsf{A058989}[n]\big)=\mathsf{A049300}[n]$ para cada $n\in\mathbb{N}$ donde las secuencias enteras $\mathsf{A058989}$ y $\mathsf{A049300}$ se encuentran en http://oeis.org/A058989 y http://oeis.org/A049300 respectivamente.

Answer 1

Aquí se intenta responder a la mayoría de las preguntas planteadas:

¿Es cierto que $f(2k)=f(2k+1)$ ?

Esto parece ser cierto, bastaría con demostrar que $2|f(n)$ para todos $n$ . Todos los algoritmos algoritmos para cubrir enteros consecutivos con múltiplos de primos utilizan en un momento dado momento todos los primos "pequeños", por lo que utilizan en particular el primo $p=2$ . Sin embargo no prueba que $2|f(n)$ .

¿Es cierto que $f(k)∣f(k+1)$ para cada $k\in\Bbb{N}$ ?

Esto no es cierto, el contraejemplo de Hajdu y Saradha muestra que $$f(235)= J:=\frac{101.\# p_{24}}{83}$$ (tenga en cuenta que $p_{24}=89$ ) por lo que en algún momento necesariamente $f(k)$ no divide $f(k+1)$ . Yo diría que $f(233)=\# p_{24}$ y $f(234)= J$ , así que $f(233)$ probablemente no divide $f(234)$ . Esto es cierto, si el contraejemplo es el más pequeño que existe, sino lo obtendremos para el contraejemplo más pequeño (para algún $n<234$ ), es decir, para el menor $n$ tal que $f(n)$ no es un primorial.

En particular, $f(n)$ no tiene por qué ser un primorial (refutando la igualdad $f(A058989[n])=p_1.p_2...p_n$ conjeturado por la voluntad).

Para todos los números enteros $n\ge 4$ , does $f(n)>n^2$ ¿Sostener? ¿Cuál es el comportamiento asintótico de $f(n)$ ?

Aunque haya contraejemplos que demuestren $f(A058989[n])\ne f_1(A058989[n])=p_1.p_2...p_n$ Supongo que el comportamiento asintótico de $f(n)$ es la misma que la dada por $f_1$ . En ese caso se sabe que $a(n)<<n^2 \log(n)^2$ y por lo tanto $a(n)^2<< n^4 \log(n)^4<< p_n\#$ . Desde $f(a(n))\sim p_n\#$ y $f(a(n))> a(n)^2$ para los 49 primeros primos (excepto los dos primeros, 2 y 3), Es una apuesta muy segura que esta desigualdad se cumple para todos los $n\ge 4$ . Una demostración detallada implicaría las constantes en la demostración de la desigualdad $a(n)<<n^2 \log(n)^2$ .

${\bf{ Remark}}$ : En general, estas cuestiones implican resultados profundos en teoría de números que se utilizan para encontrar huecos primos, y son demostrables (casi) sólo utilizando teoría de tamices, los contraejemplos sólo se pueden encontrar con ordenadores. Según http://www.tcnj.edu/~hagedorn/papers/JacobPaper.pdf (página 5, proposición 1.1) "[...] el resultado más sólido demostrado algebraicamente sin métodos de tamizado es el resultado mucho más débil" refiriéndose a $f(2p_k−1)≤2.3.5...p_k.p_{k+1}$ que he (re)demostrado en un comentario.

Sin embargo veo una buena oportunidad para demostrar que $2|f(n)$ para todos $n$ con métodos elementales (¿se trataría de una pregunta complementaria?).

Answer 2

Utilizando la notación de Batominovski $g(n) :=$ producto de todos los primos menores o iguales que $n+1$ podemos demostrar que $f(n)|g(n)$ :

Existe al menos 1 pareja candidata, $m$ y $k$ para los que cada $1 < \gcd(k+i,m),\ \ i=0,\ldots,n-1.$ (Batominovski proporciona $m = g(n)$ y $k=2$ .)

Si $p^2|m'$ y $m'$ cubre $k,\ldots,k+n-1$ entonces $m'/p$ también cubre $k,\ldots,k+n-1$ y así cada $m', k$ se reduce a cuadrado_libre $(m'),k$ .

Hay un primer $\ p' \le n+1\ $ para qué candidato $m',k'$ satisface $\ \gcd(m',p') = 1$ o el candidato se reduce al candidato de límite superior, $m=g(n),k=2.$

Supongamos que hemos reducido el candidato $m'\not=g(n),k'$ con factor primo $p|m'$ , $\ n+1 < p$ . Porque $n < p,\ $ hay (1) $\ j\in\mathbb{Z}[0,n-1]\ $ para lo cual $\ 1 < \gcd(\frac{m'}{p},k'+i)\ $ para todos $i\in\mathbb{Z}[0,n-1]\setminus j.\ $ Porque $m'\not=g(n)$ hay primo $\ p',\ \ \gcd(p', m') = 1,\ \ p' \le n+1 < p.\ $ Porque $m'$ también podemos reducir $k = k'+d\frac{m'}{p}$ (para algún número entero positivo $d$ ) $\to \gcd(p',k+j) = p'.\ $ A continuación, para reducir aún más $\ m= p'\frac{m'}{p}\ $ tenemos $\ \gcd(m,k+j)=p\ $ y $\ 1 < \gcd(m,k+i)\ $ para todos $i\in\mathbb{Z}[0,n-1].\ $ Así que los factores de cada candidato $m'$ reducir a $\le n+1.$

Al principio esperaba que un argumento similar redujera $f(n)$ a un producto de los primeros ? números primos, pero hasta ahora sólo tenemos una débil sugerencia experimental de tal conjetura.

Exploración numérica

Considerando cada $m|g(n)$ y cada $k=2,\ldots,m+1-n$ es la forma de encontrar por fuerza bruta $f(n).\ $ Mi implementación de un solo hilo, gcc, funcionó con suficiente eficiencia en mi CPU Intel(R) Celeron(R) G1840 a 2,80 GHz, para los siguientes casos de prueba, que coinciden plenamente con los límites de san: $$ \begin{array}{rrrrc} n & \frac{g(n)}{f(n)} & \frac{f(n)}{f(n-1)} & (k) & \frac{s(n)}{f(n)} \\ 1 & 1 & 2 & (2) & 1 \\ 2 & 1 & 3 & (2) & 1 \\ 3 & 1 & 1 & (2) & 1 \\ 4 & 1 & 5 & (2) & 1 \\ 5 & 1 & 1 & (2) & 1 \\ 6 & 1 & 7 & (2) & 1 \\ 7 & 1 & 1 & (2) & 1 \\ 8 & 1 & 1 & (2) & 1 \\ 9 & 1 & 1 & (2) & 1 \\ 10 & 1 & 11 & (2) & 1 \\ 11 & 1 & 1 & (2) & 1 \\ 12 & 13 & 1 & (114) & 1 \\ 13 & 13 & 1 & (114) & 1 \\ 14 & 1 & 13 & (2) & 1 \\ 15 & 1 & 1 & (2) & 1 \\ 16 & 17 & 1 & (2184) & 1 \\ 17 & 17 & 1 & (2184) & 1 \\ 18 & 323 & 1 & (9440) & 1 \\ 19 & 323 & 1 & (9440) & 1 \\ 20 & 323 & 1 & (9440) & 1 \\ 21 & 323 & 1 & (9440) & 1 \\ 22 & 437 & 17 & (39470) & 1 \\ 23 & 437 & 1 & (39470) & 1 \\ 24 & 437 & 1 & (217128) & 1 \\ 25 & 437 & 1 & (217128) & 1 \\ 26 & 23 & 19 & (60044) & 1 \\ 27 & 23 & 1 & (60044) & 1 \end{array} $$

Aquí hemos tomado el límite de san, proporcionado en un comentario anterior, como la función $\ s(1) = 2,\ \ s(2p_{k-1}) = s(2p_k-1) = g(p_{k+1}-1).\ $ Este límite es probablemente una igualdad hasta $f(2.19) = f(38) \le g(22) < g(29-1) = s(2.19),\ $ (según los cálculos que figuran a continuación).

Exploración de la eficacia del primorial, $g(n-1)$ para cubrir alguna secuencia de enteros consecutivos, fue proporcionada por una implementación de gcc mucho más fea. Tras reflexionar, iterando a través de todas las combinaciones plausibles de cadenas de bits:

101010101010101010...
100100100100100100...
100001000010000100001
1000000100000010000001
10000000000100000000001
...

probablemente no fue una idea eficiente, pero pone a prueba lo rápido que mi núcleo de procesamiento de 22 nm puede retorcer bits. $$ \begin{array}{rrlc} product & = & \ldots & covers \\ 1!! = g(1) & f(1) = & f(1) & 1 \\ 2!! = g(2) & f(2) = & f(3) & 3 \\ 3!! = g(4) & f(4) = & f(5) & 5 \\ 4!! = g(6) & f(6) = & f(9) & 9 \\ 5!! = g(10) & f(10) = & f(13) & 13 \\ 6!! = g(12) & f(14) = & f(21) & 21 \\ 7!! = g(16) & f(22) = & f(25) & 25 \\ 8!! = g(18) & f(26) = & f(33) & 33 \\ 9!! = g(22) & ? & & 39 \\ 10!! = g(28) & ? & & 45 \\ 11!! = g(30) & ? & & 57 \\ 12!! = g(36) & ? & & 65 \end{array} $$ EDIT: cálculos mucho más profundos son proporcionados por el OEIS . Dado que f(n) es monotónicamente no decreciente, podemos extender $f(26) = f(33) = 2.3.5.7.11.13.17.19,\ $ donde $f(26)$ se encontró con la fuerza bruta y enumeró nuestra primera tabla.