Benutzer:Madbros/Perfekte Primzahl

Eine perfekte Primzahl ist eine Primzahl, deren sämtliche Anfangsziffernfolgen im Dezimalsystem ebenfalls Primzahlen sind, die sich jedoch nicht mehr durch Anfügen einer weiteren Ziffer am Ende zu einer Primzahl verlängern lässt.

Beispiele

317 ist eine perfekte Primzahl, denn ihre Anfangsziffernfolgen 3, 31 und 317 sind Primzahlen, aber keine Verlängerung um eine Dezimalziffer (3170 bis 3179) ist eine.
Dagegen ist 2 keine perfekte Primzahl, denn die Verlängerungen 23 und 29 sind auch Primzahlen.

Liste

Es existieren 27 perfekte Primzahlen:

53
317
599
797
2.393
3.793
3.797
7.331
23.333
23.339
31.193
31.379
37.397
73.331
373.393
593.993
719.333
739.397
739.399
2.399.333
7.393.931
7.393.933
23.399.339
29.399.999
37.337.999
59.393.339
73.939.133

Berechnung

Perfekte Primzahlen lassen sich mit einfachen Algorithmen (hier ein Beispiel in Java) relativ leicht berechnen:

   public class PerfectPrime {
       public static void main (String[] args) {
           test();
       }
       /**
        * Testet eine übergebene Zahl, ob sie eine Primzahl ist.
        * Dazu Teilung der Zahl von 2 bis sqrt(Zahl), da 1 immer
        * Teiler ist und ganzzahlige Lösungen von Teilern größer
        * als sqrt(Zahl) immer kleiner als sqrt(Zahl) sind und somit
        * bereits getestet wurden. Eine übergebene Primzahl kleiner
        * 2 liefert den Wert false, da Primzahlen positive Zahlen
        * >= 2 sind.
        */
       public static boolean prime(int zahl) {
           boolean test = true;
           if (zahl < 2) {
               test = false;
           } else {
               for (int i = 2; i * i <= zahl; i++) {
                   if (zahl % i == 0) {
                       test = false;
                   } // end if
               } //end of for
           }
           return test;
       }
   
       /**
        * Testet die Zahlen des übergebenen Zahlbereiches per
        * Übergabe an prime(), ob sie Primzahlen sind. Wird eine
        * Primzahl gefunden, wird sie um eine Stelle verlängert
        * und von 1 bis 9 wieder durchgetestet, bis alle Verlängerungen der Zahl
        * um eine Stelle keine Primzahlen mehr sind. Diese Zahl ist dann eine
        * perfekte Primzahl und wird ausgegeben.
        */
       public static void generate(int vonZahl, int bisZahl) {
           int i = 0;
           for (i = vonZahl; i <= bisZahl; i++) {
               if (prime(i) && !prime(i * 10 + 1) && !prime(i * 10 + 3)
                   && !prime(i * 10 + 7) && !prime(i * 10 + 9)) {
                   System.out.println(i);
               } else {
                   if (prime(i)) {
                       generate(i * 10 + 1, i * 10 + 9);
                   }
               }
           }
       }
       public static void test() {
           long estimatedTime = 0;
           long startTime = System.currentTimeMillis();
           generate(1, 9);
           long endTime = System.currentTimeMillis();
           estimatedTime += (endTime - startTime);
           System.out.println();
           System.out.println(estimatedTime + " Millisekunden für die Berechnung der 27 perfekten Primzahlen");
       }
   }

Literatur

David Wells: Prime Numbers: The Most Mysterious Figures in Math. Wiley, USA 2005, ISBN 0-471-46234-9

Weblinks

The Prime Glossary: right-truncatable prime (englisch)