Problem 23: Nicht-abundante Summen

Gesucht ist die Summe aller positiven ganzen Zahlen, die jeweils nicht als Summe von zwei abundanten Zahlen darstellbar sind! [ das englische Original ]

Glücklicher Weise wird bereits in der Aufgabenstellung darauf hingewiesen, dass alle Zahlen größer als 28123 immer als Summe zweier abundanter Zahlen berechnet werden kann. Somit begrenzt sich die Laufzeit des Algorithmus deutlich.

Zum Testen, ob eine Zahl abundant ist, konnte ich die Methode zur Berechnung der Summe aller Teiler aus Problem 21 wiederverwenden:

public static boolean isAbundantNumber( int num ) {
   return ( num < getSumOfDivisors( num ) );
}

Auf dieser Grundlage lässt sich die gewünschte Summe recht schnell berechnen:

@Override
public String solve() {
   for( int i=1; i<=AbundantSums.length; i++ ) {
      if( Mathe.isAbundantNumber( i ) ) {
         // IO.debugln( "found new abundant number: " + i );
         AbundantNumbers.add( i );
         for( int n : AbundantNumbers )
            if( i + n <= AbundantSums.length )
               AbundantSums[ i+n-1 ] = i+n;
      }
   }

   long res = 0;
   for( int i=0; i<AbundantSums.length; i++ )
      if( AbundantSums[ i ] == 0 )
         res += i+1;

   return IO.l2s( res );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 23 kann man sich hier anschauen!

<< Problem 22 Übersicht Problem 24 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: