Problem 49: Primzahlpermutationen

Gesucht wird eine Sequenz von 3 vierstelligen Primzahlen, die sowohl Permutationen von einander sind, als auch den selben Abstand untereinander haben! [das englische Original]

Auch wenn die gesuchten Primzahlen zwischen 1000 und 9999 liegen müssen, habe ich meine Klasse für große Zahlen eingesetzt. Diese konnte ich um eine Methode ergänzen, mit der man prüfen kann, ob zwei Zahlen Permutationen von einander sind.

Die eigentliche Lösung des Problems erfolgt dann in drei Schritten:

1) Alle Primzahlen zwischen 1000 und 10000 finden:

@Override
public void prepare() {
   super.prepare();
 
   candidates = new ArrayList< LargeNumber >();
   Sieve sieve = new Sieve( 10000 );
 
   for( int next : sieve ) {
      if( next > 1000 ) {
         candidates.add( new LargeNumber( next ) );
      }
   }
}

2) Alle Permutationen suchen:

@Override
public String solve() {
   IO.infoln( candidates.size() + " candidates have to be tested!" );

   Hashtable< LargeNumber, ArrayList< LargeNumber > > mem = new Hashtable< LargeNumber, ArrayList< LargeNumber > >();
 
   for( LargeNumber candidate : candidates ) {
      boolean found = false;
      Enumeration< LargeNumber > keys = mem.keys();

      while( keys.hasMoreElements() && !found ) {
         LargeNumber key = keys.nextElement();
         if( candidate.isPermutationOf( key ) ) {
            mem.get( key ).add( candidate );
            // IO.infoln( "found next " + candidate + " for " + key + " [ " + mem.get( key ).size() + " ] => " + mem.get( key ) );
            found = true;
         }
      }
 
      if( !found ) {
         mem.put( candidate, new ArrayList< LargeNumber >() );
         mem.get( candidate ).add( candidate );
      }
   }
}

3) Die gefundenen Sequenzen müssen auf gleiche Abstände geprüft werden:

   Hashtable< LargeNumber, ArrayList< LargeNumber[] > > result;
   Enumeration< LargeNumber > keys = mem.keys();

   String ret = ""; 
   while( keys.hasMoreElements() ) {
      LargeNumber key = keys.nextElement();
      if( mem.get( key ).size() > 2 ) {
         IO.infoln( "found potential series: " + mem.get( key ) );
         candidates = mem.get( key );
         result = new Hashtable< LargeNumber, ArrayList< LargeNumber[] > >();
         for( int i=0; i<candidates.size()-1; i++ ) {
            for( int j=i+1; j<candidates.size(); j++ ) {
               LargeNumber diff = candidates.get( j ).sub( candidates.get( i ) );
               if( !result.containsKey( diff ) ) {
                  result.put( diff, new ArrayList< LargeNumber[] >() );
               }
               result.get( diff ).add( new LargeNumber[]{ candidates.get( i ), candidates.get( j ) } );
            }
         }
 
         Enumeration< LargeNumber > diffs = result.keys();
 
         while( diffs.hasMoreElements() ) {
            LargeNumber diff = diffs.nextElement();
            if( result.get( diff ).size() > 1 ) {
               LargeNumber last = new LargeNumber();
               for( LargeNumber[] cur : result.get( diff ) ) {
                  if( last.equals( new LargeNumber() ) ) {
                     last = cur[ 1 ];
                  } else {
                     if( last.equals( cur[ 0 ] ) ) {
                        IO.infoln( "\thit for " + diff + ": " + last.sub( diff ) + " - " + cur[ 0 ] + " - " + cur[ 1 ] );
                        ret = last.sub( diff ) + "" + cur[ 0 ] + "" + cur[ 1 ];
                     }
                  }
               }
            }
         }
      }
   }
 
   return ret;
}

 

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

<< Problem 48 Übersicht Problem 50 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: