Vier kwadraten

[efdee]

Lagrange: elk natuurlijk getal kan geschreven worden als de som van vier kwadraten. (of soms minder termen. 0^2 mag.)
Bestaat er een algoritme om die vier kwadraten te vinden? Zo ja, hoe werkt die?

[Math-E-Mad-X]

Gewoon: alle mogelijkheden één voor één uitproberen tot je het juiste viertal gevonden hebt.

Dit waarschijnlijk niet het beste of meest efficiënte algoritme, maar het is in elk geval duidelijk dat dit algoritme bestaat.

[Math-E-Mad-X]

Hier heb je een voorbeeld in Java:

Code: Selecteer alles

static int[] run(int valueToTest) {

    for(int i=0; i<Double.POSITIVE_INFINITY; i++) {
        for(int j=0; j<=i; j++) {
            for(int k=0; k<=j; k++) {
                for(int l=0; l<=k; l++) {
	  	    if(i*i + j*j + k*k + l*l == valueToTest) {
	     	        return new int[] {i,j,k,l};
	           }
                }
	    }
	}
    }
    return null; /*this can never happen.*/
}

[tempelier]

Ik weet weinig tot van Java.
Maar het zoeken van een reeks kan gestopt worden als de wortel uit G wordt overschreden.
Dan wordt het algoritme eindig en vindt men ook alle mogelijkheden.

Een formule om ze te vinden lijkt niet nog niet gevonden,
wel een formule om het aantal mogelijkheden te bepalen.

https://de.wikipedia.org/wiki/Vier-Quadrate-Satz

[RedCat]

Mogelijk heb je hier genoeg aan (= mogelijk is dit voldoende efficient):

Code: Selecteer alles

Lagrange(n)
  for(i=floor(sqrt(n)); i>=floor(sqrt(n/4)); i--)
    m=n-i^2
    for(j=floor(sqrt(m)); j>=floor(sqrt(m/3)); j--)
      t=m-j^2
      for(k=floor(sqrt(t)); k>=floor(sqrt(t/2)); k--)
        if(issquare(t-k^2))
          return/print (i, j, k, sqrt(t-k^2))

Het is een combinatie van Math-E-Mad-X en tempelier, met daaraan toegevoegd:
- als i ≥ j ≥ k ≥ l, dan hebben elk ook een ondergrens waar we boven kunnen blijven
- de laatste variabele hoef je alleen te testen op al dan niet kwadraat zijn
- begin het zoeken steeds bij de grootste waarde, dan heb sneller succes

Mocht je aan 1 oplossing per n voldoende hebben, dan kan je vooraf eerst kwadraten uit n delen:
als n = k^2 * m
en m = a^2 + b^2 + c^2 + d^2
dan is
n = k^2 * m = k^2 * (a^2 + b^2 + c^2 + d^2) = (ka)^2 + (kb)^2 + (kc)^2 + (kd)^2