Le qvolume d'un entier

31

C'est une connaissance ancienne que chaque entier non négatif peut être réécrit comme la somme de quatre entiers carrés. Par exemple, le nombre 1 peut être exprimé comme . Ou, en général, pour tout entier non négatif , il existe des entiers tels que02+02+02+12nune,b,c,

n=une2+b2+c2+2

Joseph-Louis Lagrange l'a prouvé dans les années 1700 et c'est ce qu'on appelle souvent le théorème de Lagrange .

Ceci est parfois discuté en relation avec les quaternions - un type de nombre découvert par William Hamilton dans les années 1800, représenté par où sont des nombres réels, et et sont des unités imaginaires distinctes qui ne se multiplient pas commutativement. Plus précisément, elle est discutée en relation avec la quadrature de chaque composant du quaternion Cette quantité est parfois appelée la norme, ou la norme au carré , ou aussi la quadrance . Certaines preuves modernes du théorème de Lagrange utilisent des quaternions.

w+Xje+yj+zk
w,X,y,zje,jk
w2+X2+y2+z2

Rudolf Lipschitz a étudié les quaternions avec uniquement des composants entiers, appelés quaternions de Lipschitz. En utilisant quadrance, nous pouvons imaginer que chaque quaternion de Lipschitz peut être pensé comme ayant un ami dans les nombres entiers. Par exemple, quaternion peut être considéré comme associé à l'entier . De plus, si nous reculons, chaque entier peut être considéré comme ayant un ami dans les quaternions de Lipschitz.0+0i+0j+1k1=02+02+02+12

Mais il y a un détail intéressant du théorème de Lagrange - la sommation n'est pas unique. Chaque entier peut avoir plusieurs ensembles différents de quatre carrés qui peuvent être additionnés pour le créer. Par exemple, le nombre 1 peut être exprimé de 4 façons en utilisant des entiers non négatifs (considérons uniquement les non négatifs pour ce défi):

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

Les sommets sont toujours des carrés de 0 ou 1, mais ils peuvent se trouver à différentes positions dans l'expression.

Pour ce défi, «trions» aussi nos sommets du plus bas au plus haut, pour éliminer les doublons, afin que nous puissions considérer, pour cet exercice, que 1 n'a qu'une seule façon d'être représenté comme la somme de quatre carrés:

1=02+02+02+12

Un autre exemple est le nombre 42, qui peut être exprimé de quatre façons (encore une fois, en ne considérant que les a, b, c, d non négatifs et en éliminant les arrangements de composants en double)

42=02+12+42+52
42=12+12+22+62
42=12+32+42+42
42=22+22+32+52

Et si nous imaginions chacune de ces différentes manières d'exprimer un entier comme étant associée à un quaternion spécifique? On pourrait alors dire que le nombre 42 est associé à ces quatre quaternions:

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

Si nous imaginons l'interprétation graphique standard d'un quaternion, où , et sont des vecteurs dans l'espace euclidien tridimensionnel, et donc les composantes , et du quaternion sont des coordonnées cartésiennes tridimensionnelles , alors nous pouvons imaginer que chaque entier, à travers ce processus de pensée, peut être associé à un ensemble de coordonnées tridimensionnelles dans l'espace. Par exemple, le nombre 42 est associé aux quatre :ijk x y z ( x , y , z ) ( 1 , 4 , 5 ) , ( 1 , 2 , 6 ) , ( 3 , 4 , 4 ) , ( 2 , 3 , 5 )xyz(x,y,z)

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

Cela peut être considéré comme un nuage de points ou un ensemble de points dans l'espace. Maintenant, une chose intéressante à propos d'un ensemble de points finis dans l'espace est que vous pouvez toujours dessiner une boîte englobante minimale autour d'eux - une boîte qui est assez grande pour contenir tous les points, mais pas plus grande. Si vous imaginez la boîte comme étant une boîte ordinaire alignée sur les axes , elle est appelée boîte englobante alignée sur l'axe . La boîte englobante a également un volume, calculable en déterminant sa largeur, sa longueur et sa hauteur, et en les multipliant ensemble.x,y,z

On peut alors imaginer le volume d'une boîte englobante pour les points formés par nos quaternions. Pour l'entier 1, nous avons, en utilisant les critères de cet exercice, un quaternion dont la quadrance est 1, . Ceci est un nuage de points très simple, il n'a qu'un seul point, donc sa boîte englobante a le volume 0. Pour l'entier 42, cependant, nous avons quatre quaternions, et donc quatre points, autour desquels nous pouvons dessiner une boîte englobante. Le point minimum de la boîte est et le maximum est ce qui donne une largeur, une longueur et une hauteur de 2, 2 et 2, ce qui donne un volume de 8.0+0i+0j+1k(1,2,4)(3,4,6)

Disons que pour un entier , le qvolume est le volume de la boîte englobante alignée sur l'axe de tous les points 3D formés par des quaternions qui ont une quadrance égale à , où les composants du quaternion sont non négatifs et .nnw+xi+yj+zkw<=X<=y<=z

Créez un programme ou une fonction qui, étant donné un seul entier non négatif , produira le volume de .nn

Exemples:

input -> output
0 -> 0
1 -> 0
31 -> 4
32 -> 0
42 -> 8
137 -> 96
1729 -> 10032

C'est le code-golf, le plus petit nombre d'octets gagne.

don lumineux
la source
que dois-je ajouter? je voulais dire que le plus petit nombre d'octets gagnerait
don bright
3
Vous avez oublié la balise code-golf, je vous ai aidé à l'ajouter
Embodiment of Ignorance
1
C'est un beau défi mais ce serait encore mieux à mon humble avis s'il était un peu moins bavard. Méfiez-vous également des liens non pertinents (je ne dis pas que tous vos liens ne sont pas pertinents, mais seuls quelques-uns apportent vraiment des informations significatives pour le défi, tandis que les autres sont juste distrayants).
Arnauld
1
Oui, mais pourquoi ne prendre que i, j, k comme espace 3D mais pas 4D?
tsh
1
@tsh car les Quaternions ne représentent pas nécessairement un espace euclidien à 4 dimensions. Hamilton les a découvertes en cherchant un moyen de travailler avec l'espace tridimensionnel. Il serait possible de faire une version 4d mais je réfléchissais à leur utilisation dans l'espace 3D quand j'ai posé la question
Don Bright

Réponses:

13

Wolfram Language (Mathematica) , 67 58 octets

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

Essayez-le en ligne!

                         ...&   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
la source
4
wow, je n'avais aucune idée que quelque chose comme PowersRepresentations serait intégré dans une langue. J'ai pensé à faire un défi pour montrer les différentes façons de additionner un entier à quatre carrés, mais je suis content de ne pas l'avoir fait.
Don Bright
4
Lol, Mathematica a même une fonction intégrée pour déterminer les chèvres dans une image , donc avoir une fonction intégrée pour cela ne me surprend vraiment pas. xD
Kevin Cruijssen
8

Gelée , 17 octets

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

Essayez-le en ligne! (assez lent - faites-le assez vite pour tous les cas de test avec un interligne½ )

Comment?

Żœċ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
la source
6

Haskell , 132 123 octets

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

Essayez-le en ligne!

Solution assez simple. Brute force toutes les solutions possibles en itérant sur toutes les valeurs de 0 à n (manière exagérée mais nombre de bits plus court). Je produis le point sous forme de liste afin que nous puissions utiliser l' (!)opérateur magique de @ Lynn . Cet opérateur réduit chaque dimension avec la fonction sur le côté gauche et max!prenvoie donc une liste de taille 3 qui se compose des maximums le long de chaque dimension et min!pfait de même pour le minimum. Ensuite, nous trouvons simplement la taille minimale dans chaque dimension (en soustrayant la valeur min du max avec z(-)) et les multiplions ensemble.

Merci beaucoup à @Lynn pour avoir décollé 9 octets avec une magie de zip pliable!

user1472751
la source
1
J'ai rasé quelques octets en renonçant à la transposition au profit d'une zipWithlogique. 123 octets
Lynn
5

Sledgehammer 0,2, 12 octets

⡌⢎⣟⡊⢘⣚⡏⡨⠍⠁⡇⠨

À utiliser avec Mathematica 11.2 et cette version de Sledgehammer, qui est antérieure au défi. Voir l'historique des modifications pour une version qui fonctionne dans la version 0.3, qui a une interface graphique et génère une expression Mathematica.

Cela pousse l'entrée dans la pile et appelle la séquence de commandes

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

ce qui équivaut à évaluer le code Wolfram suivant dérivé de ma réponse Wolfram Language :

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

Essayez-le en ligne!

lirtosiast
la source
cela nécessite-t-il mathématique pour le tester?
Don Bright
@don bright Oui, le référentiel contient des instructions. C'est un travail en cours donc pas encore très convivial. Après avoir exécuté setup.wls, vous pouvez tester avec wolframscript ou interactive_app.wls.
lirtosiast
2
@Downgoat Oui. Je prévois d'implémenter une bibliothèque de golf, mais actuellement elle se décompresse en simple Mathematica.
lirtosiast
2
@pipe L'ancienne version devrait fonctionner (maintenant que j'y pense, le code est exactement le même sur une ancienne version), mais je devrais la télécharger et relancer l'installation. (Les changements depuis lors ont principalement consisté à écrire l'interface graphique et à refactoriser le code sans changement majeur de fonctionnalité.) Étant donné que cette réponse est la plus courte, il semble important de prouver l'admissibilité, alors je le ferai demain matin.
lirtosiast
1
quelqu'un d'autre peut-il exécuter cela? je voudrais en quelque sorte vérifier que cela fonctionne avant de lui donner la coche ol '.
Don
4

Python 2 , 138 octets

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

Essayez-le en ligne!

Génère récursivement les quaternions triés inversement avec la norme donnée, puis prend le produit entre le max et le min de toutes les valeurs possibles dans les trois premiers indices.

itertools aurait pu avoir un coup de feu s'il n'a pas utilisé des noms ridiculement longs comme itertools.combinations_with_replacement

Python 2 , 161 octets

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

Essayez-le en ligne!

C'est pourquoi itertoolsn'est jamais la réponse .

Xnor
la source
3

JavaScript (ES6),  148  143 octets

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

Essayez-le en ligne!

Commenté

r

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

X1X+1yz

1

Étape 1

rg

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

Étape 2

p

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
la source
2

C # (Visual C # Interactive Compiler) , 229 octets

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);}

Essayez-le en ligne!

Incarnation de l'ignorance
la source
1

Haskell , 108 octets

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

Essayez-le en ligne! (expire sur les plus grands cas de test)

Il y a quelques optimisations étranges ici. Pour calculer maximum l-minimum lla liste ldes éléments à une position donnée, il s'avère plus court dans le contexte de les convertir tous les deux en maxima en annulant le deuxième terme:, maximum l+maximum(map((-1)*))lou de manière équivalente sum[maximum$map(b*)l||b<-[-1,1]].

Pour multiplier les trois dimensions, il s'avère plus court de simplement écrire le produit f n=n%0*n%1*n%2que d'utiliser n'importe quelle sorte de boucle. Ici, n%ic'est la différence entre le min et le max des ivaleurs de coordonnées th, qui sont extraites avec l'indexation !!i.

Pour générer les quatre tuples valides, nous prenons des listes de quatre nombres [0..n]dont les carrés totalisent net sont en ordre décroissant. Nous vérifions le tri inverse de twith scanr1 max t==t, qui voit si le maximum courant de l'inverse est lui-même, car Haskell n'a pas de tri intégré sans importation coûteuse. J'ai essayé différentes façons de générer récursivement les quatre tuples comme dans mes réponses Python, mais elles étaient toutes plus longues que cette méthode de génération et de filtrage par force brute.

Xnor
la source