Es un conocimiento antiguo que cada entero no negativo puede reescribirse como la suma de cuatro enteros al cuadrado. Por ejemplo, el número 1 se puede expresar como . O, en general, para cualquier número entero no negativo , existen números enteros tales que
Joseph-Louis Lagrange demostró esto en la década de 1700 y, por lo tanto, a menudo se le llama Teorema de Lagrange .
Esto a veces se discute en relación con los cuaterniones: un tipo de número descubierto por William Hamilton en el siglo XIX, representado como donde son números reales, y y son unidades imaginarias distintas que no se multiplican conmutativamente. Específicamente, se discute en relación con la cuadratura de cada componente del cuaternión Esta cantidad a veces se llama norma, o norma al cuadrado , o también cuadrante . Algunas pruebas modernas del Teorema de Lagrange usan cuaterniones.
Rudolf Lipschitz estudió cuaterniones con solo componentes enteros, llamados cuaterniones Lipschitz. Usando quadrance, podemos imaginar que se puede pensar que cada cuaternión de Lipschitz tiene un amigo en los enteros. Por ejemplo, se puede considerar que quaternion está asociado con el entero . Además, si retrocedemos, se puede pensar que cada número entero tiene un amigo en los cuaterniones de Lipschitz.
Pero hay un detalle interesante del teorema de Lagrange: la suma no es única. Cada número entero puede tener varios conjuntos diferentes de cuatro cuadrados que se pueden sumar para crearlo. Por ejemplo, el número 1 se puede expresar de 4 maneras usando enteros no negativos (consideremos solo no negativos para este desafío):
Los sumandos son siempre cuadrados de 0 o 1, pero pueden estar en diferentes posiciones en la expresión.
Para este desafío, también "clasifiquemos" nuestros sumandos de menor a mayor, para eliminar duplicados, de modo que podamos considerar, para este ejercicio, que 1 solo tiene una forma de ser representado como la suma de cuatro cuadrados:
Otro ejemplo es el número 42, que se puede expresar de cuatro maneras (de nuevo, solo teniendo en cuenta a, b, c, d no negativo y eliminando arreglos de componentes duplicados)
¿Qué pasa si imaginamos que cada una de estas diferentes formas de expresar un número entero está asociada a un cuaternión específico? Entonces podríamos decir que el número 42 está asociado con estos cuatro cuaterniones:
Si imaginamos la interpretación gráfica de computadora estándar de un cuaternión, donde , y son vectores en el espacio euclidiano tridimensional , y entonces los componentes , y del cuaternión son coordenadas cartesianas tridimensionales , entonces podemos imaginar que cada uno entero, a través de este proceso de pensamiento, puede asociarse con un conjunto de coordenadas tridimensionales en el espacio. Por ejemplo, el número 42 está asociado con las siguientes cuatro coordenadas :
Esto puede considerarse como una nube de puntos o un conjunto de puntos en el espacio. Ahora, una cosa interesante sobre un conjunto de puntos finitos en el espacio es que siempre puedes dibujar un cuadro delimitador mínimo a su alrededor, un cuadro que sea lo suficientemente grande como para caber todos los puntos, pero no más grande. Si imagina que el cuadro es un cuadro ordinario alineado con los ejes , se llama un cuadro delimitador alineado con el eje . El cuadro delimitador también tiene un volumen, calculable determinando su ancho, largo y alto, y multiplicándolos juntos.
Entonces podemos imaginar el volumen de un cuadro delimitador para los puntos formados por nuestros cuaterniones. Para el número entero 1, tenemos, usando los criterios de este ejercicio, un cuaternión cuyo cuadrante es 1, . Esta es una nube de puntos muy simple, solo tiene un punto, por lo que su cuadro delimitador tiene el volumen 0. Sin embargo, para el número entero 42 tenemos cuatro cuaterniones, y así cuatro puntos, alrededor de los cuales podemos dibujar un cuadro delimitador. El punto mínimo de la caja es y el máximo es resultando en un ancho, largo y alto de 2, 2 y 2, dando un volumen de 8.
Digamos que para un número entero , el volumen q es el volumen del cuadro delimitador alineado con el eje de todos los puntos 3D formados por cuaterniones que tienen un cuadrante igual a , donde las componentes del cuaternión no son negativos y .
Cree un programa o función que, dado un número entero no negativo , generará el volumen q de .
Ejemplos:
input -> output
0 -> 0
1 -> 0
31 -> 4
32 -> 0
42 -> 8
137 -> 96
1729 -> 10032
Este es el código de golf, gana el menor número de bytes.
fuente
Respuestas:
Wolfram Language (Mathematica) ,
6758 bytesPruébalo en línea!
fuente
Jalea , 17 bytes
Pruébalo en línea! (bastante lento, hazlo lo suficientemente rápido para todos los casos de prueba con un líder
½
)¿Cómo?
fuente
Haskell ,
132123 bytesPruébalo en línea!
Solución bastante sencilla. Fuerza bruta todas las soluciones posibles iterando sobre todos los valores de 0 a n (exageración pero recuento de bytes más corto). Saco el punto como una lista para que podamos usar el
(!)
operador mágico de @ Lynn . Ese operador colapsa cada dimensión con la función en el lado izquierdo, por lo quemax!p
devuelve una lista de tamaño 3 que consta de los máximos a lo largo de cada dimensión ymin!p
hace lo mismo para el mínimo. Luego, solo encontramos el tamaño mínimo en cada dimensión (restando el valor mínimo del máximo conz(-)
) y los multiplicamos juntos.¡Muchas gracias a @Lynn por despegar 9 bytes con un poco de magia zip plegable!
fuente
zipWith
lógica. 123 bytesAlmádena 0.2, 12 bytes
Úselo con Mathematica 11.2 y esta versión de Sledgehammer, que es anterior al desafío. Consulte el historial de edición para una versión que funciona en la versión 0.3, que tiene una GUI y genera una expresión de Mathematica.
Esto empuja la entrada a la pila y llama a la secuencia de comandos
que es equivalente a evaluar el siguiente código Wolfram derivado de mi respuesta Wolfram Language :
Pruébalo en línea!
fuente
Python 2 , 138 bytes
Pruébalo en línea!
Genera recursivamente los cuaterniones ordenados inversamente con la norma dada, luego toma el producto entre el máximo y el mínimo de todos los valores posibles en los primeros tres índices.
itertools
podría haber tenido una oportunidad si no usara nombres ridículamente largos comoitertools.combinations_with_replacement
Python 2 , 161 bytes
Pruébalo en línea!
Por eso
itertools
nunca es la respuesta .fuente
Javascript (ES6),
148143 bytesPruébalo en línea!
Comentado
Paso 1
Paso 2
fuente
C # (compilador interactivo de Visual C #) , 229 bytes
Pruébalo en línea!
fuente
05AB1E , 18 bytes
Pruébalo en línea!
Port of Jonathan Allan's Jelly respuesta .
fuente
Haskell , 108 bytes
Pruébalo en línea! (Tiempo de espera en los casos de prueba más grandes)
Hay algunas optimizaciones extrañas aquí. Para calcular
maximum l-minimum l
la listal
de elementos en una posición dada, resulta más corto en contexto convertirlos a los dos máximos al negar el segundo término:maximum l+maximum(map((-1)*))l
o equivalentesum[maximum$map(b*)l||b<-[-1,1]]
.Para multiplicar las tres dimensiones, resulta más corto escribir el producto
f n=n%0*n%1*n%2
que usar cualquier tipo de bucle. Aquín%i
está la diferencia entre el mínimo y el máximo de losi
'valores de coordenadas, que se extraen con la indexación!!i
.Para generar las cuatro tuplas válidas, tomamos listas de cuatro números
[0..n]
cuyos cuadrados sumann
y están en orden decreciente. Verificamos la ordenación inversa det
withscanr1 max t==t
, que ve si el máximo de ejecución de la inversión es en sí mismo, ya que Haskell no tiene una ordenación integrada sin una importación costosa. Intenté varias formas de generar recursivamente las cuatro tuplas como en mis respuestas de Python, pero todas fueron más largas que esta forma de generar y filtrar la fuerza bruta.fuente