Finde die größte Primzahl, die nach dem Löschen der Ziffern immer noch eine Primzahl ist

19

Drüben unter /math/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this wird die folgende Frage gestellt. Wie viele Primzahlen sind noch vorhanden, nachdem Sie eine der Ziffern gelöscht haben? Zum Beispiel 719ist so eine Primzahl wie Sie bekommen 71, 19und 79. Obwohl diese Frage ungelöst ist, hielt ich sie für eine nette Herausforderung beim Programmieren.

Aufgabe. Geben Sie die größte Primzahl an, die Sie finden können und die nach dem Löschen einer der Ziffern eine Primzahl bleibt. Sie sollten auch den Code bereitstellen, der es findet.

Ergebnis. Der Wert der von Ihnen angegebenen Primzahl.

Sie können eine beliebige Programmiersprache und Bibliotheken verwenden, solange diese frei sind.

Für den Anfang 99444901133ist die größte auf der verlinkten Seite angegeben.

Zeitlimit. Ich akzeptiere die größte richtige Antwort genau eine Woche nach der ersten richtigen Antwort, die größer ist als 99444901133in einer Antwort.

Scores soweit.

Python (primo)

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

J (randomra) (Diese Antwort hat den 1-Wochen-Timer am 21. Februar 2013 gestartet.)

222223333333
motl7
quelle
9901444133(eine Streichung von eins 9) ist nicht prime ( 7 x 1414492019). Ihr vorheriges Beispiel war jedoch richtig.
Primo
@primo Danke, behoben. Das war ein seltsamer Tippfehler von mir.
Motl7
1
Wenn es einen größten gibt - wie die Analyse zu zeigen scheint - frage ich mich, wie Sie einen Beweis anstellen können, wenn Sie glauben, ihn gefunden zu haben.
Gnibbler
1
Was ist mit anderen Basen? In Basis 2 konnte ich nichts höheres als 11 (2r1011), 11 auch in Basis 3 (3r102), 262151 in Basis 4 (4r1000000013), 17 in Basis 5 (5r32), 37 in Basis 7 (7r52), 47 finden in der Basis 9 (9r52).
aka.nice

Antworten:

17

274 Stellen

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

Das Auffinden dauerte ungefähr 20 Stunden CPU-Zeit und ungefähr 2 Minuten pro Prime, um es zu beweisen. Im Gegensatz dazu ist die 84-stellige Lösung in ca. 3 Minuten zu finden.

84 Stellen

444444444444444444444444444444444444444444444444441111111113333333333333333333333333

77777777999999999999999777777777 (32 Stellen)
66666666666666622222222222222333 (32 Stellen)
647777777777777777777777777 (27 Stellen)
44444441333333333333 (20 Stellen)
999996677777777777 (18 Stellen)
167777777777777 (15 Stellen)

Ich empfehle dieses Tool, wenn Sie die Ursprünglichkeit bestätigen möchten: D. Alperns ECM-Applet

Verwenden Sie auch einen Repdigit-Ansatz, der am wahrscheinlichsten große Werte zu finden scheint. Das folgende Skript überspringt algorithmisch die meisten Zahlen oder Kürzungen, was ein Vielfaches von 2, 3, 5 und jetzt 11 c / o PeterTaylor ergibt (sein Beitrag erhöhte die Effizienz um ungefähr 50%).

from my_math import is_prime

sets = [
 (set('147'), set('0147369'), set('1379')),
 (set('369'), set('147'), set('1379')),
 (set('369'), set('0369'), set('17')),
 (set('258'), set('0258369'), set('39')),
 (set('369'), set('258'), set('39'))]

div2or5 = set('024568')

for n in range(3, 100):
 for sa, sb, sc in sets:
  for a in sa:
   for b in sb-set([a]):
    bm1 = int(b in div2or5)
    for c in sc-set([b]):
     if int(a+b+c)%11 == 0: continue
     for na in xrange(1, n-1, 1+(n&1)):
      eb = n - na
      for nb in xrange(1, eb-bm1, 1+(~eb&1)):
       nc = eb - nb
       if not is_prime(long(a*(na-1) + b*nb + c*nc)):
        continue
       if not is_prime(long(a*na + b*(nb-1) + c*nc)):
        continue
       if not is_prime(long(a*na + b*nb + c*(nc-1))):
        continue
       if not is_prime(long(a*na + b*nb + c*nc)):
        continue
       print a*na + b*nb + c*nc

my_math.pyfinden Sie hier: http://codepad.org/KtXsydxK
Alternativ können Sie auch die gmpy.is_primeFunktion: GMPY Project verwenden

Einige kleine Geschwindigkeitsverbesserungen als Ergebnis der Profilerstellung. Die Primalitätsprüfung für den längsten der vier Kandidaten wurde an das Ende verschoben, xrangeersetzt rangeund longersetzt intTypumwandlungen.intscheint unnötigen Overhead zu haben, wenn der ausgewertete Ausdruck zu a führt long.


Teilbarkeitsregeln

Sei N eine postitive ganze Zahl der Form a ... ab ... bc ... c , wobei a , b und c sich wiederholende Ziffern sind.

Durch 2 und 5
- Um die Teilbarkeit durch 2 und 5 zu vermeiden , darf c nicht in der Menge [0, 2, 4, 5, 6, 8] enthalten sein . Wenn b ein Mitglied dieser Menge ist, darf die Länge von c nicht kleiner als 2 sein.

Mit 3
- Wenn N = 1 (mod 3) , dann darf N keines von [1, 4, 7] enthalten , da das Entfernen eines dieser Elemente trivial zu einem Vielfachen von 3 führen würde . Ebenso für N = 2 (mod 3) und [2, 5, 8] . Diese Implementierung verwendet eine leicht abgeschwächte Form davon: Wenn N eines von [1, 4, 7] enthält , darf es keines von [2, 5, 8] enthalten und umgekehrt. Außerdem darf N nicht nur aus [0, 3, 6, 9] bestehen . Dies ist größtenteils eine äquivalente Aussage, lässt jedoch einige triviale Fälle zu, z. B. a , b und cjedes wird ein Vielfaches von 3 Mal wiederholt .

Mit 11
- Wie PeterTaylor feststellt, ist N , wenn es die Form aabbcc ... xxyyzz hat , das heißt, es besteht nur aus Ziffern, die eine gerade Anzahl von Malen wiederholt werden, trivial durch 11 teilbar : a0b0c ... x0y0z . Diese Beobachtung beseitigt die Hälfte des Suchraums. Wenn N ungerade lang ist, muss auch die Länge von a , b und c ungerade sein (75% Reduzierung des Suchraums), und wenn N gerade lang ist, darf nur eine von a , b oder c gerade sein in der Länge (25% weniger Suchraum).
- Vermutung: Wenn abc ein Vielfaches von 11 ist , zum Beispiel 407 , dann sind alle ungeraden Wiederholungen von a , b und c auch Vielfache von 11 . Dies fällt aus dem Rahmen der obigen Teilbarkeit durch 11 - Regel; in der Tat sind nur ungerade Wiederholungen unter denen, die ausdrücklich erlaubt sind. Ich habe keinen Beweis dafür, aber systematische Tests konnten kein Gegenbeispiel finden. Vergleichen Sie: 444077777 , 44444000777 , 44444440000077777777777 usw. Jeder kann diese Vermutung beweisen oder widerlegen. aditsu hat inzwischen bewiesen, dass dies korrekt ist.


Andere Formen

2 Sätze wiederholter Ziffern
Zahlen der Form, die Randomra verfolgte, a ... ab ... b , scheinen viel seltener zu sein. Es gibt nur 7 Lösungen mit weniger als 10 1700 Stellen, von denen die größte 12 Stellen lang ist.

4 Sätze wiederholter Ziffern
Zahlen dieser Form, a ... ab ... bc ... cd ... d , scheinen dichter verteilt zu sein als die, nach denen ich gesucht habe. Es gibt 69 Lösungen mit weniger als 10 100 , verglichen mit den 32 Lösungen mit 3 Sätzen wiederholter Ziffern. Diese zwischen 10 11 und 10 100 sind wie folgt:

190000007777
700000011119
955666663333
47444444441111
66666622222399
280000000033333
1111333333334999
1111333333377779
1199999999900111
3355555666999999
2222233333000099
55555922222222233333
444444440004449999999
3366666633333333377777
3333333333999888883333
4441111113333333333311111
2222222293333333333333999999
999999999339999999977777777777
22222226666666222222222299999999
333333333333333333339944444444444999999999
559999999999933333333333339999999999999999
3333333333333333333111111111111666666666611111
11111111333330000000000000111111111111111111111
777777777770000000000000000000033333339999999999999999999999999
3333333333333333333333333333333333333333333333336666666977777777777777
666666666666666666611111113333337777777777777777777777777777777777777777
3333333333333333333888889999999999999999999999999999999999999999999999999933333333

Es gibt ein einfaches heuristisches Argument, warum dies der Fall sein sollte. Für jede digitale Länge gibt es eine Anzahl von Wiederholungssätzen (dh 3 Wiederholungssätze oder 4 Wiederholungssätze usw.), für die die erwartete Anzahl von Lösungen die höchste ist. Der Übergang erfolgt, wenn die Anzahl der zusätzlichen Lösungsmöglichkeiten, die als Verhältnis herangezogen werden, die Wahrscheinlichkeit überwiegt, dass es sich bei der zu überprüfenden zusätzlichen Zahl um eine Primzahl handelt. Angesichts der exponentiellen Natur der Überprüfungsmöglichkeiten und der logarithmischen Natur der Primzahlenverteilung geschieht dies relativ schnell.

Wenn wir zum Beispiel eine 300-stellige Lösung finden möchten, ist es weitaus wahrscheinlicher, dass eine Überprüfung von 4 Sätzen mit wiederholten Ziffern eine Lösung ergibt als von 3 Sätzen, und es ist immer noch wahrscheinlicher, dass 5 Sätze vorhanden sind. Mit der mir zur Verfügung stehenden Rechenleistung würde die Suche nach einer Lösung, die viel größer als 100 Stellen mit 4 Sätzen ist, meine Kapazität sprengen, geschweige denn 5 oder 6.

primo
quelle
3
Jede Lösung der Form d^x e^y f^zerfordert, dass mindestens zwei der Sequenzlängen ungerade sind, um die Teilbarkeit durch 11 zu vermeiden. Ich weiß nicht, ob is_primeVielfache von 11 schnell genug verworfen werden, damit dies nicht ausdrücklich in Betracht gezogen werden sollte.
Peter Taylor
Ich habe die gmp-Quelle nicht vor mir, aber es beginnt sehr wahrscheinlich mit der Testaufteilung über kleine Primzahlen. Trotzdem (na&1)+(nb&1)+(nc&1) > 1ist es einfach genug, dass es schneller sein sollte. Warten Sie eine Minute, dies kann volle Zweige kurzschließen! Obna gerade und nb + ncungerade ist, [nb, nc]muss einer unbedingt gerade sein, und Sie können einfach zum nächsten springen na.
Primo
Seien Sie vorsichtig, wenn Sie gmpy.is_prime () verwenden. Ab einem bestimmten Punkt ist dies probabilistisch, Sie müssen also überprüfen, ob a zurückgegeben wird 2. 1Das heißt, es ist wahrscheinlich nur ein Prime
Knabber
4
Ein direkter und genauer Test für die Teilbarkeit durch 11 besteht darin, alle Ziffern in geraden Positionen zu addieren und alle Ziffern in ungeraden Positionen zu subtrahieren (oder umgekehrt) und zu prüfen, ob das Ergebnis ein Vielfaches von 11 ist direkt abgeleitet) können Sie alle Sequenzen mit 2+ identischen Ziffern auf 0 oder 1 Ziffern reduzieren (unter Berücksichtigung der Sequenzlänge% 2). 44444440000077777777777 reduziert sich somit auf 407; 4 + 7-0 = 11. 4444444444444444444444444444444444444444444444441111111333333333333333333333333333 reduziert auf 13.
aditsu
1
"robust"! = bewährt. Der Unterschied ist für einige unwichtig, für andere von entscheidender Bedeutung. PrimeQ in Mathematica ist eine BPSW-Variante und ein zusätzlicher MR mit Basis 3, was natürlich nur ein paar Millisekunden dauert. Pari / GP überprüft die 274-stellige Nummer mit APR-CL in ca. 3 Sekunden auf einem 5 Jahre alten Computer, und Single-Core-Open-Source-ECPP benötigt ca. 2 Sekunden. Kein Wunder, dass es für Java länger dauert, aber es ist keine große Sache. Ich ließ meine Perl-Übersetzung von diesem BPSW auf allen 4 machen, dann einen Beweis auf allen 4 nur, wenn sie alle die billigen Tests bestanden haben.
DanaJ
5

222223333333 (12 Stellen)

Hier habe ich nur das Format aa..aabb..bb mit bis zu 100 Stellen durchsucht. Nur andere Treffer sind 23 37 53 73 113 311.

J-Code (aufgeräumt) (Entschuldigung, keine Erklärung):

a=.>,{,~<>:i.100
b=.>,{,~<i.10
num=.".@(1&":)@#~
p=.(*/"1@:((1&p:)@num) (]-"1(0,=@i.@#)))"1 1
]res=./:~~.,b (p#num)"1 1/ a
randomra
quelle
Eine erschöpfende Suche in diesem Formular mit bis zu 1560 Stellen (und Zählung) ergibt nichts Größeres als diese 12-stellige Lösung.
Primo
2

Edit: Jemand hat schon eine tiefere Analyse gemacht als ich hier.

Keine Lösung, sondern eine grobe Abschätzung der Anzahl n-stelliger Lösungen.

Geschätzte Anzahl von Lösungen

J-Code wird generiert

   ops=: 'title ','Estimated number of solutions by digits',';xcaption ','digits',';ycaption ','log10 #'
   ops plot 10^.((%^.)%(2&(%~)@^.@(%&10))^(10&^.))(10&^(2+i.100))
randomra
quelle
Vielen Dank. Die y-Achse ist etwas verwirrend. Meinen Sie wirklich 10 ^ -100 als geschätzte Anzahl von Lösungen mit ungefähr 86 Stellen?
Motl7
Ja. Wenn es endlich viele Lösungen gibt, ist das glaubwürdig. Obwohl diese Schätzung auf den vorhandenen Daten basiert, ist sie etwas falsch, da sich wiederholende Ziffern eine Korrelation zwischen den Zahlen mit einer Ziffer weniger herstellen.
Randomra
1
Jemand hat bereits eine tiefere Analyse durchgeführt als ich.
randomra
Ist die y-Achse der Anteil von Zahlen mit x Ziffern, die Lösungen sind? Das ist die Anzahl der Lösungen geteilt durch 10 ^ (# Ziffern)? Es kann nicht die Zahl sein, die wie 4, 11 usw. aussieht und deren Logbuch fast immer über 1 liegt.
motl7
1

Javascript (Brute Force)

Hat noch keine höhere Nummer gefunden

http://jsfiddle.net/79FDr/4/

Ohne eine Bigint-Bibliothek ist Javascript auf ganze Zahlen beschränkt <= 2^53 .

Da es sich um Javascript handelt, beschwert sich der Browser, wenn wir den Ausführungsthread nicht für die Aktualisierung der Benutzeroberfläche freigeben. Daher habe ich mich entschlossen, den Fortschritt des Algorithmus in der Benutzeroberfläche zu verfolgen.

function isPrime(n){
    return n==2||(n>1&&n%2!=0&&(function(){
        for(var i=3,max=Math.sqrt(n);i<=max;i+=2)if(n%i==0)return false;
        return true;
    })());
};

var o=$("#o"), m=Math.pow(2,53),S=$("#s");

(function loop(n){
    var s = n.toString(),t,p=true,i=l=s.length,h={};
    if(isPrime(n)){
        while(--i){
            t=s.substring(0,i-1) + s.substring(i,l); // cut out a digit
            if(!h[t]){   // keep a hash of numbers tested so we don't end up testing 
                h[t]=1;  // the same number multiple times
                if(!isPrime(+t)){p=false;break;}
            }
        }
        if(p)
            o.append($("<span>"+n+"</span>"));
    }
    S.text(n);
    if(n+2 < m)setTimeout(function(){
        loop(n+2);
    },1);
})(99444901133);
Shmiddty
quelle
@Schmiddty Es gibt große int-Bibliotheken für js, aber diese Brute-Force-Methode scheint zum Scheitern verurteilt.
Motl7
1
@ motl7 Bin einverstanden, habe es die ganze Nacht laufen lassen, und es wurden keine Antworten gefunden.
Shmiddty
1

Ein Link zu einer Analyse des Problems wurde gepostet, aber ich dachte, es fehlen ein paar Dinge. Lassen Sie uns Zahlen mit m Ziffern betrachten, die aus k Folgen von 1 oder mehr identischen Ziffern bestehen. Es wurde gezeigt, dass eine Lösung, wenn wir die Ziffern in die Gruppen {0, 3, 6, 9}, {1, 4, 7} und {2, 5, 8} aufteilen, keine Ziffern sowohl der zweiten als auch der dritten Gruppe enthalten kann , und es muss 3n + 2 Ziffern aus einer dieser Gruppen enthalten. Mindestens zwei der k Sequenzen müssen eine ungerade Anzahl von Ziffern haben. Von den Ziffern {1, 4, 7} können nur 1 und 7 die niedrigste Ziffer sein. Keiner von {2, 5, 8} kann die niedrigste Ziffer sein. Es gibt also entweder vier (1, 3, 7, 9) oder zwei (3, 9) Möglichkeiten für die niedrigste Ziffer.

Wie viele Kandidaten gibt es? Wir haben m Ziffern, die in k Folgen von mindestens einer Ziffer aufgeteilt sind. Es gibt (m - k + 1) über (k - 1) Möglichkeiten, die Länge dieser Sequenzen zu wählen, was ungefähr (m - 1,5k + 2) ^ (k - 1) / (k - 1) ist. Es gibt entweder 2 oder 4 Auswahlmöglichkeiten für die niedrigste Ziffer, insgesamt sechs. Für die anderen Ziffern gibt es sechs Auswahlmöglichkeiten, mit Ausnahme von 36/7 für die höchste Ziffer. die Summe ist (6/7) * 6 ^ k. Es gibt 2 ^ k Möglichkeiten, um auszuwählen, ob die Länge einer Sequenz gerade oder ungerade ist. k + 1 davon sind ausgeschlossen, weil keine oder nur eine ungerade ist; Wir multiplizieren die Anzahl der Auswahlen mit (1 - (k + 1) / 2 ^ k). Dies ist 1/4, wenn k = 2, 1/2, wenn k = 3, 11/16, wenn k = 4 usw. Die Anzahl Die Anzahl der Ziffern aus der Menge {1, 4, 7} oder {2, 5, 8} muss 3n + 2 sein, sodass die Anzahl der Auswahlmöglichkeiten durch 3 geteilt wird.

Multipliziert man alle diese Zahlen, ergibt sich die Anzahl der Kandidaten

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (6/7) * 6^k * (1 - (k + 1) / 2^k) / 3

oder

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k)

Der Kandidat selbst und k Zahlen, die durch Entfernen einer Ziffer erstellt werden, müssen alle Primzahlen sein. Die Wahrscheinlichkeit, dass eine zufällige ganze Zahl um N eine Primzahl ist, beträgt ungefähr 1 / in N. Die Wahrscheinlichkeit für eine zufällige m-stellige Zahl beträgt ungefähr 1 / (m in 10). Die Zahlen hier sind jedoch nicht zufällig. Sie wurden alle so ausgewählt, dass sie nicht durch 2, 3 oder 5 teilbar sind. 8 von 30 aufeinanderfolgenden ganzen Zahlen sind nicht durch 2, 3 oder 5 teilbar. Daher ist die Wahrscheinlichkeit, eine Primzahl zu sein, (30/8) / (m in 10) oder ungefähr 1,6286 / m.

Die erwartete Anzahl von Lösungen ist ungefähr

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k) * (1.6286 / m)^(k + 1)

oder für große m über

(1 - (1.5k - 2) / m)^(k - 1) / (k - 1)! * 0.465 * 9.772^k * (1 - (k + 1) / 2^k) / m^2

Für k = 2, 3, 4, ... erhalten wir Folgendes:

k = 2: 11.1 * (1 - 1/m) / m^2
k = 3: 108 * (1 - 2.5/m)^2 / m^2 
k = 4: 486 * (1 - 4/m)^3 / m^2


k = 10: 10,065 * (1 - 13/m)^9 / m^2

Ab k = 10 wird die Zahl wieder kleiner.

gnasher729
quelle
5
Willkommen bei PPCG! Dies ist eine hervorragende Analyse; Wir suchen jedoch nach Antworten als legitime Antworten auf die Frage. Mit anderen Worten: Code. Leider lässt dies in unserer Struktur nur wenig Platz für Kommentare, die auf die Post-Kommentare verweisen. Ich würde es jedoch hassen, wenn solch eine gründliche Anstrengung in unseren Slush-Haufen verbannt würde. Daher möchte ich darauf hinweisen, dass ein Computerprogramm, das die Herausforderungsanforderungen für Ihren Posten erfüllt, mit größerer Wahrscheinlichkeit beibehalten wird um.
Jonathan Van Matre
1
Außerdem empfehle ich Ihnen dringend, unsere Schwesterseiten zu besuchen : math.stackexchange.com und mathoverflow.net
Jonathan Van Matre