Kubikzahlen

Aus ProgrammingWiki
maximaleZahl = 20000
maximalKubikzahl = Math.ceil(Math.pow(20000,(1.0/3.0)));

liste = {};

function naechsteIteration(bisherige,Summe,letzterSummand){
  if(Summe > maximaleZahl) return;
  liste[Summe] = bisherige;
  // wir müssen nur noch grössere Summanden suchen, als die, die wir bislang verwendet haben
  for(var i=letzterSummand+1; i < maximalKubikzahl; i++){
    // bisherige Summanden kopieren und einen weiteren an die Liste anfügen
    var a = Array.from(bisherige);
    a.push(i);
    // Summe um die gerade angefügte Zahl^3 erhöhen
    naechsteIteration(a,Summe+(i*i*i),i);
  }
}

naechsteIteration([0],0,0);

// liste enthält nun alle Zahlen und für jede Zahl die Summanden (Basen) als Liste
// liste[9] = [0, 1, 2] = 0^3+1^3+2^3 = 9
// liste[12758] = null nicht in M
// liste[12759] = [0, 5, 6, 7, 11, 14, 20]
// liste[12760] = [0, 12, 14, 15, 17]

// aus allen Liste nur noch Zahlen verwenden als einzelnes Array (Menge M)
M = Object.keys(liste);

console.log("Es folgen alle Zahlen bis "+maximaleZahl+". Per Copy&Paste der Zeile kopierbar.");
console.log(M);

// Suche nach der ersten Zahl k, bei der alle darauffolgenden Zahlen in M sind
var gefunden = false;
for(var k=1; k < maximaleZahl; k++){
  var q = (k+1)*(k+1)*(k+1);
  for(var z=k; z <= q; z++){
    // gibt es eine Zahl z NICHT in M, innerhalb von k bis q, dann können wir aufhören
    if(!liste[z]) break;    

    // wenn wir von k bis q durchgelaufen sind, oder wir am Ende der Liste sind 
    // können wir sagen, es gibt kein z mehr, was nicht mehr in der Liste ist.    
    if(z >= maximaleZahl) {
      console.log("K = "+k+" hatte nur noch aufeinanderfolgende Elemente in M bis "+maximaleZahl);
      gefunden = true;
      break;
    }
    // theoretisch müssten wir das bis q machen, jedoch ist 
    // 12759^3 = 2077064161479, was wir für maximaleZahl wählen müssten, 
    // das dauert wieder zu lange. Deshalb testen wir nur bis maximaleZahl
    if(z == q) {
      console.log("K = "+k+" hatte "+q+" aufeinanderfolgende Elemente in M");
      gefunden = true;
      break;
    }
  }
  if(gefunden) break;
}