Ayer polaco Olimpiada de Ciencias de la Información de composición, una de las preguntas era puramente matemático, Squares (PL).
En la tarea, hemos definido la plaza de factorización como la representación de un número natural positivo como la suma de los cuadrados de diferentes positivo, con los números enteros. Por ejemplo, 30 tiene dos representaciones, 9 o 5 solo tiene uno y 8 no tiene ninguna: $$ 30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2 \\ 5 = 1^2 + 2^2 \\ 9 = 3^2 $$ Y la función $k$ devuelve el menor de las plazas más grandes de todas las representaciones. Para el ejemplo anterior tenemos: $$k(30) = \min\lbrace \max\lbrace1, 2, 5 \rbrace, \max\lbrace1,2,3,4\rbrace\rbrace= \min\lbrace5,4\rbrace = 4 \\ k(5) = \min\lbrace\max\lbrace1, 2\rbrace\rbrace = 2 \\ k(9) = \min\lbrace\max\lbrace3\rbrace\rbrace = 3 $$
We assume $k(x) = \infty^{+}$, if the factorisation for x is not possible.
$$k(8) = \infty^{+}$$
We call number x inter-grown if $\a la izquierda(\existe y \in \mathbb{Z}_{+}\right)\left(y > x \wedge k(y) < k(x) \right) $. For example $k(378) = 12$, $k(380) = 10$, so 378 is inter-grown ($378 < 380~\cuña~k(378) > k(380)$). 8 is too: $(8 < 9 \cuña k(8) > k(9))$
The question was two-part. First was the value of $k(n)$, el segundo fue: ¿cuántos existe más pequeños de n números, la bruja se inter-crecido? Restricción para $n$ era débil. $n \in \mathbb{Z}_{+} \wedge n \leq 10^{18}$.
He hecho esta tarea absolutamente no-matemáticamente. Escribí el programa en python, la bruja me proporciona gran cantidad de información. Me di cuenta de función y comprobado por muchos ejemplos (uso de la computadora, por supuesto). Luego yo estaba pensando acerca de la prueba. De hecho, escribí algo se parece a la prueba, pero no estoy satisfecho. Es confuso, ilegible y no estoy seguro de si es correcto. Afortunadamente no tenemos que hacer pruebas.
Sin embargo, después de finalizado el certamen empecé a preguntarme, ¿cómo debería de apariencia simple y clara prueba de ello. Y me pregunte acerca de la evidencia de la corrección de la primera y segunda parte de la pregunta. Le pido dos cosas en una sola pregunta, porque es fuertemente relacionados (al menos en mi intento). Todo mi conocimiento pongo a continuación. Una gran parte se considera que el caso lo suficientemente grandes $n$, porque era más fácil. Pequeño $n$ I calculan por separado y colocado en la mesa.
Entre crecido
El número de indecomposable números es finito, y es bien conocido el hecho. Acerca de los demás, se puede leer menos.
-
Sobre la base de programa, a partir de 522 entre crecido números se producen regularmente en grupos. Cada uno contiene 31 números, y no se encuentran en los mismos lugares, como indecomposable números. Por lo
2, 3, 6, 7,..., si el grupo comienza dos números antes de puño entre crecido. Supongo que el comenzar de grupo es la primera inter-crecido, por lo que no se encuentra en0, 1, 4, 5,...posiciones en el grupo.Yo creo, que los grupos son de $n$ más pequeño que el 522 y se superponen, pero no cambia nada.
-
Grupos comenzó en posiciones
691, 887, 1112, 1368,..., las distancias entre ellos son196, 225, 256,..., las diferencias aquí son29, 31, 33, 35, .... Och! Es una progresión aritmética. Así, es fácil calcular principio de n-ésimo grupo. Creo, no tengo que escribir de transformación de aquí. Obtenemos que, enésimo grupo comienza a partir de$$887+\frac{1261 n}{6}+\frac{29 n^2}{2}+\frac{n^3}{3} \wedge n \in \mathbb{N}$$
Podemos calcular diferentes entre n y el siguiente grupo. Si yo no cometen el error es $(n+14)^2$.
Valor de $k(n)$
$k(n)$ no puede ser más pequeño que el más pequeño de x, para la bruja $\sum_{i=1}^{x} i^{2} = \frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6} \geq n$. Pero es obvio.
He observado, si el número no está entre crecido, y él es lo suficientemente grande ($n > 522$ es suficiente), que es el número más pequeño, la bruja satisface la desigualdad en el párrafo anterior...
... de lo contrario, es que el número aumentado en uno.
Claro es que todo puede ser calculado en $O(lg~n)$ del tiempo. Es magnífico!
Naturalmente, es sólo de cálculos sobre datos pequeños, sin ninguna prueba, y por encima de los patrones (de la bruja de hecho son correctos) son tesis. Si alguien tiene una clara y bonita idea, de cómo debería verse (la prueba!) Voy a estar agradecido por la descripción.
