Problem 43: Teilbare Teil-Zeichenketten

Gesucht wird die Summe aller pandigitalen Zahlen, deren Ziffergruppen durch die Primzahlen von 2 bis 17 teilbar sind! [ das englische Original ]

Die offensichtliche Lösung dieses Problems ist sicherlich, „einfach“ alle Ziffern von 0 bis 9 zu permutieren und die resultierenden Zahlen gegen die gewünschten Regeln zu testen. Allerdings weiß ich seit dem Problem 24, dass die dafür benötigte Zeit jenseits von gut und böse liegt. Daher versuchte ich – im wahrsten Sinne des Wortes – das Pferd von hin aufzusäumen:

  1. Für die letzten drei Stellen der gesuchten Ziffern ist gefordert, dass diese Vielfache von 17 sind. Damit gibt es nur 58 Zahlen (017, 034, … , 969, 986), die grundsätzlich in Frage kommen. Hier fallen bereits 14 Zahlen aus der Betrachtung raus, da sie nicht pandigital sind, z.B. 119 und 221.
  2. Im nächsten Schritt werden die 76 Vielfach der Zahl 13 geprüft, ob deren letzten beiden Stellen in einer der verbliebenen Kandidaten aus Schritt 1 die jeweils ersten beiden Stellen darstellt. Dies trifft auf 35 Zahlen zu, d.h.  9 Zahlen aus Schritt 1 starten nicht mit Ziffern, die durch Vielfach von 13 abbildbar sind. Unter den 35 Zahlen befinden sich nun noch weitere 9 Zahlen, die nicht pandigital sind. Daher bleiben nach diesem Schritt als nur noch 26 Kandidaten übrig.

Die nachfolgende Grafik veranschaulicht die ersten beiden Schritt:

Veranschaulichung am Beispiel der Vielfachen von 13 und 17, wie das Problem gelöst werden kann.
Veranschaulichung am Beispiel der Vielfachen von 13 und 17, wie das Problem gelöst werden kann.

Nun muss man nur noch den zweiten Schritt für alle anderen Vielfachen wiederholen, um so schlussendlich genau sechs Kombinationen zu finden, den gewünschten Regeln entsprechen. Da die erste Stelle mit keiner Regel überprüft wird, kann hier einfach die verbleibende Ziffer eingesetzt werden.

Um die verbliebenen Kandidaten zu summieren, wandele ich sie mit Hilfe eines neuen Konstruktors meiner Klasse für große Zahlen um und kann sie damit leicht addieren:

@Override
public String solve() {
   Integer[] current;

   /*** modulo 17 ***/
   IO.debugln( ">>>> mod 17 >>>>" );
   for( int k = 1; 1000 > k*17; k++ ) {
      int num = k * 17;
      int[] digits = Mathe.split( num, 3 );
      current = new Integer[]{ -1, -1, -1, -1, -1, -1, -1, digits[ 0 ], digits[ 1 ], digits[ 2 ] };
      IO.debug( "found: [ " + IO.join( current, ", " ) + " ] " );
      if( check( current ) ) {
         IO.debugln( " ... works!" );
         candidates.add( current );
      } else {
         IO.debugln( " ... fails!" );
      }
   }
 
   IO.debugln( "have " + candidates.size() + " candidates!" );
   ArrayList< Integer[] > addables = new ArrayList< Integer[] >();
 
   /*** modulo 13, 11, 7, 5, 3, 2 ***/
   int[] nums = new int[]{ 13, 11, 7, 5, 3, 2 };
   for( int i=0; i<nums.length; i++ ) {
      IO.debugln( ">>>> mod " + nums[ i ] + " >>>>" );
      for( int k = 1; 1000 > k * nums[ i ]; k++ ) {
         int[] digits = Mathe.split( k * nums[ i ], 3 );
         for( Integer[] candidate : candidates ) {
            if( digits[ 1 ] == candidate[ 7-i ] && digits[ 2 ] == candidate[ 8-i ] ) {
               current = candidate.clone();
               current[ 6-i ] = digits[ 0 ];
               IO.debug( "found: [ " + IO.join( current, ", " ) + " ] " );
               if( check( current ) ) {
                  IO.debugln( " ... works!" );
                  addables.add( current );
               } else {
                  IO.debugln( " ... fails!" );
               }
            }
         }
      }
 
      candidates = addables;
      IO.debugln( "have " + candidates.size() + " candidates!" );
      addables = new ArrayList< Integer[] >();
   }

   /*** find first digit ***/
   for( Integer[] candidate : candidates ) {
      int sum = 45;
      for( int i : candidate ) {
         sum -= i;
      }
      candidate[ 0 ] = sum - 1;
   }
 
   /*** calc the sum of all candidates ***/
   LargeNumber result = new LargeNumber();
   for( Integer[] candidate : candidates ) {
      LargeNumber tmp = new LargeNumber( candidate );
      result = result.add( tmp );
   }
 
   return result.toString();
}

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

<< Problem 42 Übersicht Problem 44 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: