En una práctica para la programación de la competencia, uno de los problemas frecuentes con nosotros para encontrar el número más pequeño de pirámides, que puede ser construido usando exactamente $n$ bloques, donde las pirámides tienen $k\times k, (k-1)\times (k-1),\ldots,1\1$ de bloques en cada nivel o $2k\times 2 k 2(k-1)\times 2(k-1),\ldots,2\times 2$ de bloques en cada nivel. Tenga en cuenta que el primer tipo de pirámide tiene $$\sum\limits_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$$ los bloques mientras que la segunda tiene $$\sum\limits_{i=1}^k (2i)^2 = \frac23 k(k+1)(2k+1).$$ Equivalentemente, queremos escribir $$ n como suma de los números de esta forma, utilizando como pocos como sea posible. El oficial solución a este problema que se ha tenido un incremento exponencial en tiempo de ejecución en el mínimo número de pirámides, pero indicó que esto no era problemático, ya que el número mínimo de las pirámides está siempre a más de $6 dólares. No veo ninguna razón obvia para este, o incluso una razón obvia por la que el número mínimo de pirámides debe ser acotada. Alguien puede dar una prueba?
Respuestas
¿Demasiados anuncios?
Esta preocupación que muestra el número mínimo de pyramaids está acotada. No sé el valor eficaz de la envolvente, ya que depende de un teorema de Hua lo que implica que cada suficientemente grande entero es la suma de nueve o diez cubos de los números primos.
Vamos $s(n)=n(n+1)(2n+1)$ que es de $6$ veces el número de bloques de un tipo $1$ pirámide. Luego tenemos a la identidad $$s(n+1)+22s(n)+s(n-1)=6(2n+1)^3. \etiqueta{1}$$ Ahora suponiendo que tenemos un número extenso $M,$ escribimos $M=6k+r$ con $0 \le r <6$. El resultado de Hua dice entonces podemos escribir $k$ como una suma de nueve o diez cubos de los números primos. Si $2$ es uno de los primos que podemos obtener los $6*2^3$ el uso de un acotado número de pirámides. Otro de los números primos son impares cubos de $p^3$ y cada $6p^3$ cada uno puede ser obtenida por un acotado número de pyramaids usando $(1)$. El resto $r$ sólo se necesita un número finito de más.
EDIT: me di cuenta de que $(1)$ puede ser dividido por $6$ y a continuación se da la misma relación entre los números $t(n)=n(n+1)(2n+1)/6$, que son los que cuenta para el tipo 1 de las pirámides. Entonces no hay necesidad de escribir $M=6k+r$ y se puede aplicar Hua resultado directamente. Dado que el coeficiente de $22=5\cdot 4 +2$ cada $t(n+1)+22t(n)+t(n-1)$ de verdad presenta sólo nueve pirámides, que luego lleva a la cuenta abajo un poco más. Pero esto no es mucho mejor, ya que un atado de decir $81$ para suficientemente grande $M$ es mucho mayor que la probabilidad obligado de $6 dólares.
El sitio que he encontrado discutiendo el Hua resultado es un documento por Koichi Kawada. El Hua resultado es a partir de 1938. Kawada de papel
ACTUALIZACIÓN
No es el resultado de la R. D. James, que implica que uno puede conseguir lo suficientemente grande enteros como una suma de nueve de los de tipo 1 piramidal números, anteriormente llamado $t(n)$. Esta es mucho mejor obligado que la implícita en la suma de los cubos de consecuencias trabajado anteriormente, a pesar de que todavía sólo se aplica para los suficientemente grandes enteros. Si alguien quiere comprobar la correspondencia, es que $t(x)$ coincide con el polinomio $P(x)$ de James papel $a=2,\ b=c=1.$
Jame del papel es en JSTOR, con el siguiente enlace. Se obtiene una vista previa de la página, que contiene lo suficiente para ver el resultado, y parece que uno puede leer en línea de forma gratuita si uno tiene un JSTOR cuenta. El enlace:
No se muy bien la respuesta, pero un inicio: Es fácil mostrar que hay infinitamente muchos enteros n que requieren al menos cuatro pirámides: El número de bloques en una pirámide es siempre 0 (módulo 5), 1 (modulo 5) o 4 (modulo 5). De hecho, uno de cada cinco números es 1 (modulo 5), uno de cada cinco es de 4 (módulo 5) y 3 5 0 (módulo 5). Para obtener una suma que es 2 (modulo 5), tenemos que añadir 0 + 1 + 1 (modulo 5) o 4 + 4 + 4 (modulo 5).
k(k+1)(2k+1)/6 es sobre k^3/3, por lo que hay cerca (3n)^(1/3) de los que tiene menos de n. k(k+1)(2k+1)*2/3 es acerca de 4k^3/3, por lo que sobre (3n/4)^(1/3) de los que están a menos de n. El número total de valores < n es acerca de 2.351 n^(1/3). 0,47 n^(1/3) 1 (modulo 5), del 0,47 n^(1/3) 4 (módulo 5), acerca de 1.41 n^(1/3) 0 modulo 5.
Hay aproximadamente (0.47 * 0.47 * 1.41 / 2)n sumas de la forma 0 + 1 + 1 (modulo 5), y acerca de (0.47 * 0.47 * 0.47 / 6)n sumas de la forma 4 + 4 + 4 (modulo 5). Esto se suma a alrededor 0.173 n sumas de dinero igual a 2 (modulo 5); muchos de estos son > n, entonces el número de sumas menor que n son menos que eso. Pero hay 0.2 números <= n 2 modulo 5, por lo que muchos de estos no puede ser la suma de las tres pirámides.
He comprobado que hasta n = 1 mil millones de dólares, alrededor del 69% de todos los números son la suma de a lo más tres pirámides. Lo mismo es cierto para n = 100 millones, por lo que el porcentaje de números que necesitan cuatro pirámides parece bastante constante. Todos los números hasta 1 mil millones de dólares es la suma de las cuatro pirámides con las excepciones n = 108, n = 247 y n = 1007 que necesitan de 5.
Algunas más de las estadísticas: De los números de 1 a 1 mil millones de dólares,
69.58% are the sum of three pyramids
89.48% are the sum of three pyramids and the number 1
97.47% are the sum of three pyramids and the number 1 or 4
98.78% are the sum of three pyramids and the number 1, 4 or 5
99.36% are the sum of three pyramids and the number 1, 4, 5 or 20
99.77% are the sum of three pyramids and the number 1, 4, 5, 20 or 14
All but the three mentioned above are the sum of three pyramids, and a pyramid up to 650.
Esto hace que sea muy poco probable que cualquier otros números de 108, 247 y 1007 requeriría más de cuatro pirámides, pero no ayuda un poco para probarlo.
