Vier kwadraten

Moderators: dirkwb, Xilvo

Reageer
Berichten: 626

Vier kwadraten

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?

Gebruikersavatar
Berichten: 2.906

Re: Vier kwadraten

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.

Gebruikersavatar
Berichten: 2.906

Re: Vier kwadraten

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.*/
}

Gebruikersavatar
Berichten: 4.312

Re: Vier kwadraten

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

Berichten: 463

Re: Vier kwadraten

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

Reageer