Sumas pares son cuadrados perfectos.

Question

He pensado en este problema como una simplificación de Euler-Ladrillo problema .

$1)$Que $n$ es posible encontrar la $n$ distintos números enteros positivos $a_1,a_2,\ldots,a_n$ tal que todos sus pares sumas , es decir,$a_i+a_j$ , son cuadrados perfectos .

Por ejemplo, cuando se $n=3$, se puede elegir : $4$,$21$ y $60$ (con las sumas $25$,$64$ y $81$ ) . Otro ejemplo es $1$ , $24$ y $120$ .

Si no es posible para todos los $n$ a continuación, vamos a $f(n)$ ser el número más grande de las sumas que pueden ser cuadrados perfectos simultáneamente. Por lo $f(3)=3$ .

También puede conseguir $f(4) \geq 4$$1,3,35,46$ .

Mi otra pregunta es :

$2)$ ¿Qué límites podemos lograr para $f(n)$ ? (incluso para valores particulares es bueno ) . Lo que yo quiero es una mejor que la 'lineal' atados .

La motivación para preguntar esto de Euler Ladrillo problema que pide a encontrar tres números enteros positivos $x,y,z$ tal que $x^2+y^2$ , $y^2+z^2$ , $x^2+z^2$ todos son cuadrados perfectos .

Hay paramétrica de soluciones para este problema, pero para el $4$D ladrillo problema ni siquiera una solución se conoce (ver aquí https://en.wikipedia.org/wiki/Euler_brick)

Este duro $4$D versión me hicieron hacer esta versión simplificada .

Estoy (casi) seguro de que no soy el primer considerando de este problema por lo que no puede ser conocida de los resultados en la literatura de investigación , pero no he encontrado todavía.

Gracias por todos los que me puedan ayudar con este problema . Les agradezco a todos sus esfuerzos .

EDIT : he añadido la distinta condición , de lo contrario el problema es fácil . Aquí están los detalles :

Elija algunas de $x=2a^2$ y, a continuación, elija todos los números para ser $x$ . Todos los importes son ahora los cuadrados perfectos para $f(n)=\binom{n}{2}$ por cada $n$ .

Answer 1

Mi Última Respuesta

He descubierto un menos trivial aproximación de la tasa de crecimiento de $f(n)$. Pero primero quiero ser rigurosos acerca de exactamente lo $f(n)$ está contando. Estoy haciendo esto en el caso que he interpretado mal la pregunta. Mi entendimiento es que el $f(n)$ es el número máximo de distintos pares de $(i, j)$ $1 \leq i < j \leq n$ de manera tal que exista un conjunto de $n$ enteros positivos $\{a_1, a_2, \dots, a_n\}$ $a_i + a_j = s^2$ algunos $s$. Claramente, $f(n) \leq {n \choose 2}$, ya que podemos elegir en la mayoría de las ${n \choose 2}$ pares de $n$ objetos.

Ahora, para encontrar un límite inferior para $f(n)$, sólo tenemos que encontrar un conjunto de pares y de un correspondiente conjunto de valores, de tal manera que todos los valores indexados por los pares de la suma de los cuadrados perfectos. Vamos a considerar el conjunto de $\{1, 2, 3, \dots, n\}$ y definen $h(n)$ como el número de los distintos pares de elementos de este conjunto, que se agregan a los cuadrados perfectos. Claramente $h(n) \leq f(n)$. Ahora voy a plantear una muy simple prueba de demostración de que:

$$n^{\frac32} \sim h(n)$$

Considerar la adición de $n+1$ para el conjunto de $\{1, 2, 3, \dots, n\}$. Ahora nos forma a todos los pares de $(1, n+1), (2, n+1), \dots, (n, n+1)$ cuyo importe correspondiente se $n+2, n+3, \dots, 2n+1$. Ahora, vamos a $s(a, b)$ denotar el número de cuadrados perfectos en el intervalo de $[a, b]$. Entonces tenemos:

$$h(n+1) = h(n) + s(n+2, 2n+1)$$

Ahora, ¿cuántos cuadrados perfectos se encuentran en el intervalo de $[n+2, 2n+1]$? Así, aproximadamente hay:

$$\sqrt{2n+1} - \sqrt{n + 2} \approx \sqrt{2n} - \sqrt{n} = \sqrt{n}(\sqrt{2} - 1)$$

Así, a grandes rasgos, tenemos:

$$h(n+1) \approx h(n) + \sqrt{n}(\sqrt{2} - 1)$$

La expansión de la recursividad y factorizando los $(\sqrt{2} - 1)$ entonces tenemos:

$$h(n) \sim \sqrt{1} + \sqrt{2} + \dots + \sqrt{n} \sim \int_1^n \sqrt{x}\,dx \sim n^{\frac32}$$

A mi las matemáticas aquí no es de mi costumbre estándar de rigor, pero creo que es el sonido. Esto implicaría que la tasa de crecimiento de $f(n)$ está en algún lugar entre el$n^{\frac32}$$n^2$.

---

Actualización: podemos llegar a un límite inferior para $h(n)$ de una manera diferente, evitando el uso de la integración. Consideremos el conjunto a $\{1, 2, 3, \dots, n\}$. Hay $\lfloor\sqrt{n}\rfloor$ cuadrados perfectos en este conjunto. Para cada cuadrado perfecto,$k^2$, podemos formar con $\lfloor\dfrac{k^2 - 1}{2}\rfloor \geq \dfrac{k^2}{2} - 1$ único pares:

$$(1, k^2 - 1), (2, k^2 - 2), \dots, (\lfloor\dfrac{k^2 - 1}{2}\rfloor, \lceil\dfrac{k^2 + 1}{2}\rceil)$$

Estos no son todos los cuadrados que se pueden formar, pero todos ellos son posibles, por lo que son válidos para un menor enlazado argumento. Deje $R=\lfloor\sqrt{n}\rfloor$ para la facilidad de la notación. El límite inferior es entonces:

$$\sum_{i=1}^{R}\left(\dfrac{i^2}{2} - 1\right) = \frac12\sum_{i=1}^{R}i^2 - R = \dfrac{R(R+1)(2R+1)}{12} - R$$

Es evidente que esto es de la orden de $n^{\frac32}$.

Mi Aburrido Respuesta Original

Voy a dar una muy trivial respuesta a $(2)$. Hemos enlazado:

$$n - 1 \leq f(n)$$

Para ver por qué, elija $a_1 = 1$, y para todos los $i \neq 1$ elija $a_i = i^2 - 1$. Entonces tenemos que para todos los $i \neq 1$, $a_i + a_1 = i^2$. Desde allí se $n - 1$ valores de $i \neq 1 \leq n$, se obtiene el límite inferior.

---

Actualización: rindiendo homenaje a la comentarista Crostul y el OP ComplexPhi, que han hecho más trabajo de lo que yo, podemos mejorar este límite inferior:

$$f(n) \geq f(k) + n - k$$

para cualquier $k \leq n$.

Destacar el descubrimiento de la entidad Zander anterior, tenemos que $f(4) = 6$, y así tenemos los siguientes obligado:

$$f(n) \geq n + 2 \;\;\; \mathrm{where} \;\;\; (n \geq 4)$$