El volumen q de un entero

31

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 que0 02+0 02+0 02+12norteuna,si,do,re

norte=una2+si2+do2+re2

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.

w+Xyo+yj+zk
w,X,y,zyo,jk
w2+X2+y2+z2

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.0 0+0 0yo+0 0j+1k1=0 02+0 02+0 02+12

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):

1=0 02+0 02+0 02+12
1=0 02+0 02+12+0 02
1=0 02+12+0 02+0 02
1=12+0 02+0 02+0 02

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:

1=0 02+0 02+0 02+12

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)

42=0 02+12+4 42+5 52
42=12+12+22+6 62
42=12+32+4 42+4 42
42=22+22+32+5 52

¿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:

0 0+1yo+4 4j+5 5k
1+1yo+2j+6 6k
1+3yo+4 4j+4 4k
2+2yo+3j+5 5k

Si imaginamos la interpretación gráfica de computadora estándar de un cuaternión, donde yo , j y k son vectores en el espacio euclidiano tridimensional , y entonces los componentes X , y y z 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 (X,y,z) :

(1,4,5),(1,2,6),(3,4,4),(2,3,5)

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 x,y,z , 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, 0+0i+0j+1k . 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 (1,2,4 4) y el máximo es (3,4 4,6 6) resultando en un ancho, largo y alto de 2, 2 y 2, dando un volumen de 8.

Digamos que para un número entero norte , 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 norte , donde las componentes del cuaternión w+Xyo+yj+zk no son negativos y w<=X<=y<=z .

Cree un programa o función que, dado un número entero no negativo norte , generará el volumen q de norte .

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.

don brillante
fuente
¿Qué necesito agregar? Quise decir que ganaría el menor número de bytes
don brillante
3
Olvidaste la etiqueta de código de golf, te ayudé a agregarla
Encarnación de la ignorancia
1
Este es un buen desafío, pero sería aún mejor en mi humilde opinión si fuera un poco menos detallado. Además, tenga cuidado con los enlaces irrelevantes (no digo que todos sus enlaces sean irrelevantes, pero solo algunos de ellos realmente aportan información significativa para el desafío, mientras que los otros solo distraen).
Arnauld
1
Sí, pero ¿por qué tomar solo i, j, k como espacio 3D pero no como espacio 4D?
TSH
1
@tsh porque los Cuaterniones no representan necesariamente un espacio euclidiano de 4 dimensiones. Hamilton los descubrió mientras buscaba una forma de trabajar con el espacio tridimensional. Sería posible hacer una versión 4d pero estaba reflexionando sobre su uso en el espacio 3d cuando hice la pregunta
don bright

Respuestas:

13

Wolfram Language (Mathematica) , 67 58 bytes

Volume@BoundingRegion[Rest/@PowersRepresentations[#,4,2]]&

Pruébalo en línea!

                         ...&   Pure function:
PowersRepresentations[#,4,2]    Get the sorted reprs. of # as sums of 4 2nd powers
Rest/@                         Drop the first coordinate of each
BoundingRegion[...]            Find the bounding region, a Cuboid[] or Point[].
                               By default Mathematica finds an axis-aligned cuboid.
Volume                         Find volume; volume of a Point[] is 0.
lirtosiast
fuente
44
wow, no tenía idea de que algo como PowersRepresentations estaría integrado en un idioma. De hecho, pensé en hacer un desafío para mostrar las diferentes formas de sumar un número entero como cuatro cuadrados, pero me alegro de no haberlo hecho.
Don brillante
44
Lol, Mathematica incluso tiene una función incorporada para determinar las cabras en una imagen , por lo que tener una función integrada para esto realmente no me sorprende. xD
Kevin Cruijssen
8

Jalea , 17 bytes

Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P

Pruébalo en línea! (bastante lento, hazlo lo suficientemente rápido para todos los casos de prueba con un líder½ )

¿Cómo?

Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P - Link: non-negative integer, n    e.g. 27
Ż                 - zero-range                            [0,1,2,...,27]
   4              - literal four                          4
 œċ               - combinations with replacement         [[0,0,0,0],[0,0,0,1],...,[0,0,0,27],[0,0,1,1],[0,0,1,2],...,[27,27,27,27]]
        Ƈ         - filter keep those for which:          e.g.: [0,1,1,5]
       ɗ          -   last three links as a dyad:
    ²             -     square (vectorises)                     [0,1,1,25]
     S            -     sum                                     27
      ⁼  ⁸        -     equal to? chain's left argument, n      1
                  -                                       -> [[0,1,1,5],[0,3,3,3],[1,1,3,4]]
          Z       - transpose                             [[0,0,1],[1,3,1],[1,3,3],[5,3,4]]
           Ḋ      - dequeue                               [[1,3,1],[1,3,3],[5,3,4]]
            Ṣ€    - sort each                             [[1,1,3],[1,3,3],[3,4,5]]
              I   - incremental differences (vectorises)  [[ 0,2 ],[ 2,0 ],[ 1,1 ]]
               §  - sum each                              [2,2,2]
                P - product                               8
Jonathan Allan
fuente
6

Haskell , 132 123 bytes

z=zipWith
(!)=foldr1.z
h n=[0..n]
f n|p<-[[c,b,a]|a<-h n,b<-h a,c<-h b,d<-h c,a^2+b^2+c^2+d^2==n]=product$z(-)(max!p)$min!p

Prué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 que max!pdevuelve una lista de tamaño 3 que consta de los máximos a lo largo de cada dimensión y min!phace 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 con z(-)) y los multiplicamos juntos.

¡Muchas gracias a @Lynn por despegar 9 bytes con un poco de magia zip plegable!

usuario1472751
fuente
1
Afeité algunos bytes al renunciar a la transposición a favor de alguna zipWithlógica. 123 bytes
Lynn
5

Almá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

{intLiteral[4], intLiteral[2], call["PowersRepresentations", 3], call["Thread", 1], call["Rest", 1], call["Thread", 1], call["BoundingRegion", 1], call["Volume", 1]}

que es equivalente a evaluar el siguiente código Wolfram derivado de mi respuesta Wolfram Language :

Volume[BoundingRegion[Thread@Rest@Thread@PowersRepresentations[#, 4, 2]]]&

Pruébalo en línea!

lirtosiast
fuente
¿Requiere esto Mathica para probarlo?
Don brillante
@don bright Sí, el repositorio tiene instrucciones. Es un trabajo en progreso, por lo que aún no es muy fácil de usar. Después de ejecutar setup.wls, puede probar con wolframscript o interactive_app.wls.
lirtosiast
2
@Downgoat Sí. Planeo implementar una biblioteca de golf, pero actualmente se descomprime a Mathematica simple.
lirtosiast
2
@pipe La versión anterior debería funcionar (ahora que lo pienso, el código es exactamente el mismo en una versión anterior), pero tendría que descargarlo y volver a ejecutar la configuración. (Los cambios desde entonces han estado escribiendo principalmente la GUI y el código de refactorización sin cambios importantes en la funcionalidad). Dado que esta respuesta es más breve, parece importante probar la elegibilidad, así que lo haré mañana por la mañana.
lirtosiast
1
¿Alguien más puede ejecutar esto? me gustaría verificar que funciona antes de darle la marca de verificación anterior.
Don brillante
4

Python 2 , 138 bytes

q=lambda n,x=0,*t:[t]*(n==0)if t[3:]else q(n-x*x,x,x,*t)+q(n,x+1,*t+(0,)*(x>n))
p=1
for l in zip(*q(input()))[:3]:p*=max(l)-min(l)
print p

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 como itertools.combinations_with_replacement

Python 2 , 161 bytes

from itertools import*
n=input();p=1
for l in zip(*[t[1:]for t in combinations_with_replacement(range(n+1),4)if sum(x*x for x in t)==n]):p*=max(l)-min(l)
print p

Pruébalo en línea!

Por eso itertoolsnunca es la respuesta .

xnor
fuente
3

Javascript (ES6),  148  143 bytes

n=>(r=[[],[],[]]).map(a=>p*=a.length+~a.indexOf(1),(g=(s,k=0,a=[])=>a[3]?s||r.map(r=>r[a.pop()]=p=1):g(s-k*k,k,[...a,++k],k>s||g(s,k,a)))(n))|p

Pruébalo en línea!

Comentado

r

r = [ [], [], [] ]

X1X+1yz

1

Paso 1

rsol

g = (              // g is a recursive function taking:
  s,               // s   = current sum, initially set to the input n
  k = 0,           // k   = next value to be squared
  a = []           // a[] = list of selected values
) =>               //
  a[3] ?           // if we have 4 values in a[]:
    s ||           //   if s is equal to zero (we've found a valid sum of 4 squares):
      r.map(r =>   //     for each array r[] in r[]:
        r[a.pop()] //       pop the last value from a[]
        = p = 1    //       and set the corresponding value in r[] to 1
                   //       (also initialize p to 1 for later use in step 2)
      )            //     end of map()
  :                // else:
    g(             //   do a recursive call:
      s - k * k,   //     subtract k² from s
      k,           //     pass k unchanged
      [...a, ++k], //     increment k and append it to a[]
      k > s ||     //     if k is less than or equal to s:
        g(s, k, a) //       do another recursive call with s and a[] unchanged
    )              //   end of outer recursive call

Paso 2

pags

r.map(a =>         // for each array a[] in r[]:
  p *=             //   multiply p by:
    a.length +     //     the length of a[]
    ~a.indexOf(1)  //     minus 1, minus the index of the first 1 in a[]
) | p              // end of map(); return p
Arnauld
fuente
2

C # (compilador interactivo de Visual C #) , 229 bytes

a=>{uint b=0,c=~0U,d,e,f=0,g=0,h=0,i=c,j=c,k=c;for(;b*b<=a;b++)for(c=b;c*c<=a;c++)for(d=c;d*d<=a;d++)for(e=d;e*e<=a;e++)if(b*b+c*c+d*d+e*e==a){f=c>f?c:f;g=d>g?d:g;h=e>h?e:h;i=c<i?c:i;j=d<j?d:j;k=e<k?e:k;}return(f-i)*(g-j)*(h-k);}

Pruébalo en línea!

Encarnación de la ignorancia
fuente
1

Haskell , 108 bytes

n%i=sum[maximum[t!!i*b|t<-mapM([0..n]<$f)[0..3],sum(map(^2)t)==n,scanr1 max t==t]|b<-[-1,1]]
f n=n%0*n%1*n%2

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 lla lista lde 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)*))lo equivalente sum[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%2que usar cualquier tipo de bucle. Aquí n%iestá la diferencia entre el mínimo y el máximo de los i'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 suman ny están en orden decreciente. Verificamos la ordenación inversa de twith scanr1 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.

xnor
fuente