Pares pequeños a, b, cada entero hasta k que divide al menos uno de ellos

Question

Mi pregunta es esencialmente la siguiente $m=2$ caso de esta pregunta .

Dado un número entero positivo $k$ Me interesan los pares (pequeños) de enteros positivos $a,b$ tal que todo número entero positivo hasta (e incluyendo) $k$ es un factor de al menos uno de ellos. Por ejemplo, para $k=10$ Uno de estos pares es $a=70$ , $b=72$ cada número entero hasta 10 es un factor de al menos uno de estos dos números.

Es fácil ver que el producto de cualquier par de este tipo debe ser un múltiplo del mínimo común múltiplo, llámese $L(k)$ de $1,2,3,\dots,k$ . Se sabe que $L(k)$ es asintótica a $e^k$ . Además, es trivial encontrar un par cuyo producto sea exactamente $L(k)$ ; sólo toma $a=1$ , $b=L(k)$ . Esto me dice que, para este problema, el producto, $ab$ no es una buena medida de lo pequeño que es el par $a,b$ es. Otras dos medidas que se sugieren son la suma, $a+b$ y el máximo. Como el producto es al menos $L(k)$ la suma debe ser al menos $2\sqrt{L(k)}$ y el máximo debe ser como mínimo $\sqrt{L(k)}$ . Mi pregunta es, ¿qué tan agudos son estos límites?

Hice un pequeño cálculo a mano durante una reciente reunión de la comisión, y llegué a estas cifras, dadas sin ninguna garantía de que sean, de hecho, mínimas: $$\matrix{k&a&b&a+b&ab/L\cr3&2&3&5&1\cr4&3&4&7&1\cr5&5&12&17&1\cr6&5&12&17&1\cr7&12&35&47&1\cr7&28&30&58&2\cr8&24&35&59&1\cr9&35&72&107&1\cr10&70&72&142&2\cr11&77&360&437&1\cr12&77&360&437&1\cr13&360&1001&1361&1\cr}$$ Tenga en cuenta que para $k=7$ He dado dos $a,b$ pares, uno con una suma menor, el otro con un máximo menor.

He consultado la Enciclopedia en línea de las secuencias de números enteros para $a$ , $b$ y $a+b$ sin encontrar nada.

Supongo que se podría hacer la misma pregunta para los triples $a,b,c$ tal que cada número entero hasta $k$ es un factor de uno de ellos, o cuadruplica, o....

La relación con la pregunta 98330 es la siguiente. Con la notación utilizada aquí, los conjuntos $A=\lbrace a+1,b+1\rbrace$ y $B=\lbrace 1,a+b+1\rbrace$ son indistinguibles modulo $m$ para todos $m$ hasta $k$ .

Answer 1

Reclamación: Entre las parejas $a$ y $b$ para que $GCD(a,b)=2$ y cada número entero hasta $n$ divide $a$ o $b$ el valor mínimo de $\max(a,b)$ es $\sqrt{2 L(n)}(1+o(1))$ .

Esto deja abierta la cuestión de cuándo podría ser mejor con $(a,b)=1$ . Como he comentado, si $(a,b)=1$ entonces $L(n/2) \prod p$ divide el factor par, donde el producto es sobre todos los primos con una potencia entre $n/2$ y $n$ , incluyendo $p=2$ . En algunas pruebas numéricas, $L(n/2) \gt \sqrt {L(n)}$ . Si esto ocurre para grandes $n$ entonces $\max(a,b)$ se minimiza con $(a,b)=2$ .

Además, para un número finito de $n$ podría ser que $\max(a,b)$ se minimiza cuando $GCD(a,b) \gt 2$ .

Para encontrar un par con $\max(a,b)$ cerca de $\sqrt{2L(n)}$ consideramos una gran colección de pares con $(a,b)=2$ para que $3|a$ Desde los que tienen $a$ mucho menos que $b$ a los que tienen $a$ mucho mayor que $b$ para que la relación entre cada uno y el siguiente más grande sea $1+o(1)$ .

Dejemos que $a_0 = L(n)/\prod_{n/3 \lt \text{prime}~p \le n} p = L(\lfloor n/3 \rfloor) 2^\alpha \prod p$ donde el producto es sobre primos Impares $p$ para que haya un poder de $p$ entre $n/3$ y $n$ y $2^\alpha$ es el cociente de la mayor potencia de $2$ hasta $n$ por el mayor poder de $2$ hasta $n/3$ Así que $2^\alpha$ es $2$ o $4$ . Desde $L(n) \approx \exp(n)$ , $L(n/3) \approx \sqrt[3]{L(n)} \ll \sqrt{L(n)}$ . Además, para los grandes $n$ , $a_0 \ll \sqrt{L(n)}$ por la fórmula de Stirling, por ejemplo. $a_0$ se ha elegido de forma que no sólo cada número entero de $1$ a $n$ dividir $a_0$ o $2L(n)/a_0$ pero cada conjunto $S$ de primos entre $n/3$ y $n$ se puede "añadir" a $a_0$ y seguirá siendo el caso que cada número entero hasta $n$ divide $a_S = a_0 \prod_{p \in S}p$ o $2L(n)/a_S$ . Queremos elegir $S$ para que $a_S$ está cerca de $\sqrt{2L(n)}$ .

Necesitamos algunos resultados de densidad suaves sobre los primos entre $n/3$ y $n$ . (Edición: Antes tenía una condición de densidad más débil, pero creo que era insuficiente). Basta con decir que para una densidad suficientemente grande $x$ hay un primo entre $x$ y $x+x^{2/3}$ . Utilizando esto, construye conjuntos de primos $U$ y $V$ de igual tamaño para que cada proporción $u/v$ entre un primo en $U$ y un primo en $V$ está entre $1$ y $1+f(n)$ , donde $f(n)$ es $o(1)$ el producto de todos los primos en $U$ dividido por el producto de todos los primos en $V$ es mayor que $n$ y $a_V \lt \sqrt{2L(n)}$ . La cuestión es que si empezamos con todos los elementos de $V$ en $S$ y ningún elemento de $U$ en $S$ podemos aumentar $a_S$ por un factor inferior a $1+f(n)$ añadiendo un elemento de $U$ a $S$ y eliminar un elemento de $V$ de $S$ y repetir para aumentar la magnitud en más de un factor de $n$ . Entonces podemos añadir un primo a $S$ que no está en $U$ o $V$ , eliminar todos los elementos de $U$ y volver a poner todos los elementos de $V$ lo que disminuye la magnitud a un máximo de $n$ veces el original. A su vez, sumamos cada primo entre $n/3$ y $n$ en el exterior $V$ y $U$ y esto nos da una secuencia de magnitudes de $a_{S(i)}$ que comienza a continuación $\sqrt{2L(n)}$ y termina por encima de ella sin dar un paso hacia arriba de un factor mayor que $1+f(n)$ por lo que existe un conjunto de primos $T$ para que $a=a_T$ está entre $\sqrt{2L(n)}$ y $\sqrt{2L(n)}(1+f(n))$ y $b = 2L(n)/a \lt a$ .

Answer 2

Para $n=27$ o $n=28$ se tiene el posible caso $(a,b)=(10810800,7429)=(16\cdot27\cdot25\cdot7\cdot11\cdot13,17\cdot19\cdot23)$ Eso parece lo mejor que se puede hacer con $ab=L.$ Lanzar un $2$ a la derecha permite $(831600,193154)=(16\cdot27\cdot25\cdot7\cdot11,2\cdot13\cdot17\cdot19\cdot23)$

Un enfoque codicioso para $n=29$ con $ab=2L$ da $(a,b)=(831600,5601466)=(16\cdot27\cdot25\cdot7\cdot11,2\cdot13\cdot17\cdot19\cdot23\cdot29)$ Pero aún mejor es $(2192400,2124694)=(16\cdot27\cdot25\cdot7\cdot29,2\cdot13\cdot17\cdot19\cdot23\cdot11)$

Es difícil decir lo que se considera casi óptimo. Una versión refinada del método de @Gerhard es

• elige una pequeña $s$ ( probablemente sólo $1$ o $2$ ) y que $\ell$ sea el lcm de $1,2,\cdots,s$

• empezar con $b=\ell P$ con $P$ el producto de todos los primos $\frac{n}{s+1} \lt p \le n$ y $a$ el lcm de todos $p^i \le n$ con $p \le \frac{n}{s+1}$ .

• si $a \ge b$ entonces no se puede hacer mejor con eso $s$ (Creo que esto siempre ocurre cuando $s=1$ dejé de comprobarlo después de un tiempo). . Si no, encuentra un divisor $Q$ de $P$ que es lo más parecido a $\sqrt{\frac{b}{a}}$ y utilizar $(aQ,\frac{b}{Q})$

• ver si se puede hacer mejor con un poco más pequeño o más grande $s$ .

MÁS TARDE Estoy bastante seguro de que sólo vemos $s=1$ y $s=2$ . Para $s=2$ y $n$ no demasiado pequeño es posible conseguir $\frac{b}{a}$ muy cerca de $1$ .

Si mi programa y mi razonamiento son correctos, entonces hasta $7 \le n \le 129$ es mejor tener $s=1$ cuando $n=8-12, 17, 18, 22-26, 31-34, 43-46, 53-58, 61, 62, 71, 72, 81, 82, 119, 120$

es mejor tener $s=1$ para $a+b$ pero mejor tener $s=2$ para $\max(a,b)$ cuando $n=7, 13, 14, 75-80, 103-106$

Para el otro $76$ casos $n=15, 16, 19-21, 27-30, 35-42, 47-52, 59, 60$$ 63-70, 73, 74, 83-102, 107-118, 121-129 $ it is best to have $ s=2$

Por supuesto, el mismo $a,b$ puede funcionar para una carrera de $n$ valores como $113-118$

Answer 3

No es una respuesta definitiva, pero la siguiente pareja debería marcar el listón para encontrar parejas pequeñas.

En los comentarios anteriores he intentado definir un par en términos de productos de primos (primoriales $P_k$ ) y lcm, pero en realidad es más sencillo hacer lo siguiente:

Set a = 1 and b = L = lcm(1,...,n)
While p is the largest prime dividing b do
   a = a*p
   b = b/p
   if (one is happy with the pair (a,b)) then stop
   if 2*p' <= n then stop # p' is the largest prime less than p
   if (b is 1) then stop

Por supuesto, para n grande se termina con (L/q, q) donde q es un producto de bastantes primos, todos ellos mayores que n/2. Imagino que q está cerca de sqrt(L), pero no tengo la asintótica a mano. Dejando n=30, se tiene q=215441 y L/q = 10810800, por lo que se pregunta si hay que dividir un número por 13 y multiplicar el menor por 26. Me sorprendería me sorprendería si se pudiera demostrar que q es asintóticamente malo para la tarea, en lugar de sólo asintóticamente subóptimo.

Gerhard "Ask Me About System Design" Paseman, 2012.05.31

Answer 4

He aquí una asíntota rápida. Sea $A(k)$ sea el producto de todos los $k/2>p\leq k$ . Entonces $(L(k)/A(k),A(k))$ forman un par, como ha señalado Gerhard Paseman en los comentarios, con una notación diferente. Esto se debe a que cada $i\leq k$ es un primo que divide a $A(k)$ o coprima a $A(k)$ .

Así, si $A(k)$ está cerca de $\sqrt{L(k)}$ entonces los límites son nítidos.

$A(k)$ es fácil de calcular con el teorema de los números primos. $\ln A(k)$ es una suma sobre los primos entre $k/2$ y $k$ del logaritmo de ese primo, que es aproximadamente $k-k/2=k/2$ .

$L(k)=e^{(1+o(1))k}$ . $A(k)=e^{(1/2+o(1))k}$ . Por lo tanto, el máximo de $a$ y $b$ no es más que $e^{(1/2+o(1))k}$ y la suma no es superior a $2e^{(1/2+o(1))k}$ . Conseguir que los límites sean más estrechos parece difícil.