Betrachten Sie die Funktion Remove(n, startIndex, count), mit der countZiffern nvon der Ziffer an der Position entfernt werden startIndex. Beispiele:

Remove(1234, 1, 1) = 234
Remove(123456, 2, 3) = 156
Remove(1507, 1, 2) = 07 = 7
Remove(1234, 1, 4) = 0

Wir werden die Primzahl X als fragil bezeichnen, wenn jede mögliche RemoveOperation sie zu einer Nicht-Primzahl macht. Beispielsweise ist 80651 eine fragile Primzahl, da alle folgenden Zahlen keine Primzahlen sind:

651, 51, 1, 0, 8651, 851, 81, 8, 8051, 801, 80, 8061, 806, 8065

Tor

Schreiben Sie ein Programm, das die größte fragile Primzahl findet. Bearbeiten: Das Zeitlimit wurde entfernt, da es einen relativ fairen Weg gab, es zu umgehen.

Die Punktzahl ist die fragile Primzahl, die von Ihrem Programm gefunden wurde. Bei einem Gleichstand gewinnt die frühere Einreichung.

Regeln

• Sie können eine beliebige Sprache und Bibliotheken von Drittanbietern verwenden.
• Sie führen das Programm auf Ihrer eigenen Hardware aus.
• Sie können probabilistische Primalitätstests verwenden.
• Alles ist in der Basis 10.

Führende Einträge

• 6629 Ziffern von Qualtagh (Java)
• 5048 Ziffern von Emil (Python 2)
• 2268 Stellen von Jakube (Python 2)

Bearbeiten: Ich habe meine eigene Antwort hinzugefügt.

• 28164 Ziffern von Suboptimus Prime, basierend auf dem Qualtagh-Algorithmus (C #)

Java - 3144 3322 6629 Stellen

6 0{3314} 8969999

6 0{6623} 49099

Diese Lösung basiert auf der Antwort von FryAmTheEggman .

1. Die letzte Ziffer ist 1 oder 9.
2. Wenn die letzte Ziffer 1 ist, ist eine vorherige 0, 8 oder 9.
3. Wenn die letzte Ziffer 9 ist, ist eine vorherige 0, 4, 6 oder 9.
4. ...

Was ist, wenn wir tiefer graben?

Es wird eine Baumstruktur:

                        S
             -----------------------
             1                     9
    ------------------         ----------------
    0           8    9         0    4    6    9
---------     -----
0   8   9      ...

Nennen wir die Zahl R rechts zusammengesetzt, wenn R und alle seine Endungen zusammengesetzt sind.

Wir werden alle richtigen zusammengesetzten Zahlen in der Breite zuerst durchlaufen: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901 usw.

Zahlen, die mit Null beginnen, werden nicht auf Primalität geprüft, sondern zum Aufbau weiterer Zahlen benötigt.

Wir werden nach einer Zielnummer N in der Form X00 ... 00R suchen, wobei X eine von 4, 6, 8 oder 9 ist und R die richtige Zusammensetzung ist. X kann keine Primzahl sein. X kann nicht 0 sein. Und X kann nicht 1 sein, denn wenn R mit 1 oder 9 endet, würde N 11 oder 19 enthalten.

Wenn XR nach dem Entfernen Primzahlen enthält, enthält XYR diese auch für jedes Y. Wir sollten also keine Zweige ab R durchlaufen.

Sei X eine Konstante, sagen wir 6.

Pseudocode:

X = 6;
for ( String R : breadth-first-traverse-of-all-right-composites ) {
  if ( R ends with 1 or 9 ) {
    if ( remove( X + R, i, j ) is composite for all i and j ) {
      for ( String zeros = ""; zeros.length() < LIMIT; zeros += "0" ) {
        if ( X + zeros + R is prime ) {
          // At this step these conditions hold:
          // 1. X + 0...0 is composite.
          // 2. 0...0 + R = R is composite.
          // 3. X + 0...0 + R is composite if 0...0 is shorter than zeros.
          suits = true;
          for ( E : all R endings )
            if ( X + zeros + E is prime )
              suits = false;
          if ( suits )
            print R + " is fragile prime";
          break; // try another R
                 // because ( X + zeros + 0...0 + R )
                 // would contain prime ( X + zeros + R ).
        }
      }
    }
  }
}

Wir sollten die Anzahl der Nullen begrenzen, da es zu lange dauern kann, eine Primzahl in der Form X + Nullen + R zu finden (oder für immer, wenn alle zusammengesetzt sind).

Der wahre Code ist ziemlich ausführlich und kann hier gefunden werden .

Primalitätstests für Zahlen im Long-Int-Bereich werden mit der deterministischen Variante des Miller-Tests durchgeführt. Für BigInteger-Nummern wird zuerst eine Testdivision und dann ein BailliePSW-Test durchgeführt. Es ist wahrscheinlich, aber ziemlich sicher. Und es ist schneller als der Miller-Rabin-Test (wir sollten viele Iterationen für so große Zahlen in Miller-Rabin durchführen, um eine ausreichende Genauigkeit zu erzielen).

Bearbeiten: Der erste Versuch war falsch. Wir sollten auch Zweige ignorieren, die mit R beginnen, wenn X0 ... 0R Primzahl ist. Dann wäre X0 ... 0YR keine zerbrechliche Primzahl. Daher wurde eine zusätzliche Prüfung hinzugefügt. Diese Lösung scheint richtig zu sein.

Bearbeiten 2: Optimierung hinzugefügt. Wenn (X + R) durch 3 teilbar ist, ist (X + Nullen + R) auch durch 3 teilbar. Daher kann (X + Nullen + R) in diesem Fall keine Primzahl sein, und solche Rs können übersprungen werden.

Edit 3: Es war nicht notwendig, Primzahlen zu überspringen, wenn sie sich nicht an der letzten oder ersten Position befanden. Endungen wie 21 oder 51 sind also in Ordnung. Aber es ändert sich nicht viel.

Schlussfolgerungen:

1. Meine letzte Antwort war, 100 Minuten lang zu prüfen, ob sie zerbrechlich sind. Die Suche nach der Antwort (Prüfung aller vorhergehenden Varianten) dauerte ca. 15 Minuten. Ja, es macht keinen Sinn, die Suchzeit einzuschränken (wir können die Suche ab der Zielnummer starten, also wäre die Zeit Null). Es kann jedoch sinnvoll sein, die Überprüfungszeit wie in dieser Frage zu beschränken .
2. Die Antwort 60 ... 049099 hat die Ziffer 4 in der Mitte. Wenn die "Entfernen" -Operation es berührt, wird die Zahl durch 3 teilbar. Wir sollten also die Entfernungsoperationen auf der linken und rechten Seite überprüfen. Die rechte Seite ist zu kurz. Die Länge der linken Seite beträgt fast n = Länge (N).
3. Primalitätstests wie BPSW und Miller-Rabin verwenden eine konstante Menge modularer Exponentiationen. Seine Komplexität ist gemäß dieser Seite O (M (n) * n) , wobei M (n) die Multiplikationskomplexität ist. Java verwendet Toom-Cook- und Karatsuba-Algorithmen, der Einfachheit halber nehmen wir den Scholar-Algorithmus. M (n) = n ² . Die Komplexität der Primärtests ist also O (n ³ ).
4. Wir sollten alle Zahlen von Länge = 6 bis 6629 überprüfen. Nehmen wir für die Gemeinsamkeit min = 1 und max = n. Die gesamte Prüfkomplexität ist O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. Emils Antwort hat die gleiche prüfende Asymptotik. Der konstante Faktor ist jedoch niedriger. Die Ziffer "7" steht in der Mitte der Zahl. Linke und rechte Seite können fast gleich sein. Es ergibt (n / 2) ⁴ * 2 = n ⁴ / 8. Beschleunigung: 8X. Zahlen in der Form 9 ... 9Y9 ... 9 können 1,7-mal länger sein als in der Form X0 ... 0R mit der gleichen Prüfzeit.

Python 2 - 126 1221 1337 1719 2268 Ziffern

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

'9' * 1944 + '7' + '9' * 323

Es gibt bei ungefähr len (n) ^ 2 resultierende Zahlen von Remove (n, startIndex, count). Ich habe versucht, diese Zahlen zu minimieren. Wenn viele Ziffern nebeneinander gleich sind, können viele dieser resultierenden Zahlen ignoriert werden, da sie mehrfach vorkommen.

Also habe ich es bis zum Äußersten genommen, nur 9s und ein wenig Blüte in der Mitte. Ich habe mir auch die fragile Primzahl unter 1 Million angesehen und festgestellt, dass es solche fragilen Primzahlen gibt. Die Suche nach Zahlen mit 2 9s am Ende funktioniert wirklich gut, ich weiß nicht warum. 1 Zahl, 3 oder 4 9s am Ende ergeben kleinere fragile Primzahlen.

Es wird das Pyprimes-Modul verwendet . Ich bin mir nicht sicher, ob es etwas Gutes ist. Es verwendet den miller_rabin-Test, ist also probabilistisch.

Das Programm findet diese 126-stellige fragile Primzahl in ungefähr 1 Minute und sucht für den Rest der Zeit erfolglos.

biggest_found = 80651

n = lambda a,b,c: '9'*a + b + '9'*c

for j in range(1000):
   for digit in '124578':
      for i in range(2000):
         number = int(n(i,digit,j))
         if is_prime(number):
            if (number > biggest_found):
               if all(not is_prime(int(n(i,digit,k))) for k in range(j)):
                  biggest_found = number
                  print(i+j+1, biggest_found)
            break

bearbeiten:

Hab gerade gesehen, dass du das Zeitlimit entfernt hast. Ich werde das Programm über Nacht laufen lassen, vielleicht tauchen einige wirklich große zerbrechliche Primzahlen auf.

2 bearbeiten:

Habe mein Originalprogramm schneller gemacht, also doch noch keine Lösung mit mehr als 126 Stellen. Also bin ich in den Zug gesprungen und habe nach x 9s + 1 Digit + y 9s gesucht. Der Vorteil ist, dass Sie O (n) -Nummern auf Primalität prüfen müssen, wenn Sie y korrigieren. Es findet einen 1221 ziemlich schnell.

3 bearbeiten:

Für die 2268-stellige Nummer verwende ich das gleiche Programm, nur die Arbeit auf mehrere Kerne aufgeteilt.

Python 2.7 - 429623069 99993799

Bisher keine Optimierungen. Nur ein paar triviale Beobachtungen zu fragilen Primzahlen (dank Rainbolt im Chat):

1. Fragile Primzahlen müssen mit 1 oder 9 enden (Primzahlen sind nicht gerade und die letzte Ziffer darf keine Primzahl sein)
2. Fragile Primzahlen, die mit 1 enden, müssen mit 8 oder 9 beginnen (die erste Zahl darf keine Primzahl sein und 11, 41 und 61 sind Primzahlen).
3. Fragile Primzahlen, die mit 9 enden, müssen mit 4,6 oder 9 beginnen (siehe Begründung für 1, aber nur 89 sind Primzahlen)

Ich versuche nur, den Ball ins Rollen zu bringen :)

Dies dauert technisch gesehen etwas länger als 15 Minuten, prüft aber in der Verlängerung nur eine einzige Zahl.

is_primewird von hier genommen (isaacg hat es hier benutzt ) und ist probabilistisch.

def substrings(a):
    l=len(a)
    out=set()
    for i in range(l):
        for j in range(l-i):
            out.add(a[:i]+a[len(a)-j:])
    return out

import time

n=9
while time.clock()<15*60:
    if is_prime(n):
        if not any(map(lambda n: n!='' and is_prime(int(n)), substrings(`n`))):
            print n
    t=`n`
    if n%10==9 and t[0]=='8':n+=2
    elif n%10==1 and t[0]!='8':n+=8
    elif t[0]=='1' or is_prime(int(t[0])):n+=10**~-len(t)
    else:n+=10

Nur eine Anmerkung, wenn ich damit anfange, stehe n=429623069ich auf 482704669. Die zusätzliche Ziffer scheint wirklich diese Strategie zu töten ...

Python 2, 828 Stellen, 5048 Stellen

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
155*'9'+'7'+4892*'9'

Wie @Jakube hervorhob, war die erste von mir eingereichte Primzahl aufgrund eines Fehlers in meinem Code nicht wirklich zerbrechlich. Das Beheben des Fehlers war einfach, aber der Algorithmus wurde dadurch erheblich langsamer.

Ich beschränkte mich auf eine leicht durchsuchbare Untermenge der fragilen Primzahlen, nämlich jene, die nur aus der Ziffer 9 und genau einer Ziffer 7 bestehen.

def fragile_prime_generator(x, b_max):
  bs, cs = set(), set()
  prime = dict()

  def test_prime(b,c):
    if (b,c) not in prime:
      prime[(b,c)] = is_prime(int('9'*b+`x`+'9'*c))
    return prime[(b,c)]

  def test_frag(b,c):
    for b2 in xrange(b):
      if test_prime(b2,c):
        bs.add(b2)
        return False
    for c2 in xrange(c):
      if test_prime(b,c2):
        cs.add(c2)
        return False
    return True

  a = 1
  while len(bs)<b_max:
    for b in xrange(min(a, b_max)):
      c = a-b
      if b not in bs and c not in cs and test_prime(b,c):
        bs.add(b)
        cs.add(c)
        if test_frag(b,c): yield b,c
    a += 1
  print "no more fragile primes of this form"

for b,c in fragile_prime_generator(7, 222):
  print ("%d digit fragile prime found: %d*'9'+'%d'+%d*'9'"
          % (b+c+1, b, x, c))

Ich habe dieselbe is_primeFunktion (von hier aus ) wie @FryAmTheEggman verwendet.

Bearbeiten:

Ich habe zwei Änderungen vorgenommen, um den Algorithmus zu beschleunigen:

• Ich versuche, so viele Primalitätsprüfungen wie möglich zu überspringen und erst dann zurückzukehren, wenn eine potenzielle fragile Primzahl gefunden wurde, um sicherzustellen, dass sie wirklich fragil ist. Es gibt eine kleine Anzahl von doppelten Schecks, deshalb habe ich die Funktion zur Prüfung der Primzahlen grob auswendig gelernt.

• Für die Anzahl der Formulare habe b*'9' + '7' + c*'9'ich die Größe von begrenzt b. Je niedriger die Grenze, desto weniger Zahlen müssen überprüft werden, aber die Wahrscheinlichkeit steigt, dass keine großen fragilen Primzahlen gefunden werden. Ich habe 222 willkürlich als Grenze gewählt.

Bei ein paar tausend Stellen kann eine einzelne Primzahlprüfung bereits einige Sekunden dauern. Daher kann ich mit diesem Ansatz wahrscheinlich nicht viel besser umgehen.

Bitte zögern Sie nicht, die Richtigkeit meiner Angaben zu überprüfen. Aufgrund der probabilistischen Primalitätsprüfung könnte meine Zahl theoretisch keine Primzahl sein, aber wenn ja, sollte sie fragil sein. Oder ich habe etwas falsch gemacht. :-)

C #, 10039 28164 Ziffern

6 0{28157} 169669

Bearbeiten: Ich habe ein anderes Programm basierend auf dem Qualtagh-Algorithmus mit einigen geringfügigen Änderungen erstellt:

• Ich suche nach den Zahlen der Form L000 ... 000R, wobei L links zusammengesetzt ist, R rechts zusammengesetzt ist. Ich habe zugelassen, dass die linke zusammengesetzte Zahl L mehrere Stellen hat, obwohl dies meist eine stilistische Änderung ist und die Effizienz des Algorithmus wahrscheinlich nicht beeinträchtigt.
• Ich habe Multithreading hinzugefügt, um die Suche zu beschleunigen.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Threading;
using System.Threading.Tasks;
using Mpir.NET;

class Program
{
    const int PrimeNotFound = int.MaxValue;

    private static BitArray _primeSieve;
    private static HashSet<Tuple<int, int>> _templatesToSkip = new HashSet<Tuple<int, int>>();

    static void Main(string[] args)
    {
        int bestDigitCount = 0;
        foreach (Tuple<int, int> template in GetTemplates())
        {
            int left = template.Item1;
            int right = template.Item2;
            if (SkipTemplate(left, right))
                continue;

            int zeroCount = GetZeroCountOfPrime(left, right);
            if (zeroCount != PrimeNotFound)
            {
                int digitCount = left.ToString().Length + right.ToString().Length + zeroCount;
                if (digitCount >= bestDigitCount)
                {
                    string primeStr = left + " 0{" + zeroCount + "} " + right;
                    Console.WriteLine("testing " + primeStr);
                    bool isFragile = IsFragile(left, right, zeroCount);
                    Console.WriteLine(primeStr + " is fragile: " + isFragile);

                    if (isFragile)
                        bestDigitCount = digitCount;
                }

                _templatesToSkip.Add(template);
            }
        }
    }

    private static int GetZeroCountOfPrime(int left, int right)
    {
        _zeroCount = 0;

        int threadCount = Environment.ProcessorCount;
        Task<int>[] tasks = new Task<int>[threadCount];
        for (int i = 0; i < threadCount; i++)
            tasks[i] = Task.Run(() => InternalGetZeroCountOfPrime(left, right));
        Task.WaitAll(tasks);

        return tasks.Min(task => task.Result);
    }

    private static int _zeroCount;

    private static int InternalGetZeroCountOfPrime(int left, int right)
    {
        const int maxZeroCount = 40000;
        int zeroCount = Interlocked.Increment(ref _zeroCount);
        while (zeroCount <= maxZeroCount)
        {
            if (zeroCount % 1000 == 0)
                Console.WriteLine("testing " + left + " 0{" + zeroCount + "} " + right);

            if (IsPrime(left, right, zeroCount))
            {
                Interlocked.Add(ref _zeroCount, maxZeroCount);
                return zeroCount;
            }
            else
                zeroCount = Interlocked.Increment(ref _zeroCount);
        }

        return PrimeNotFound;
    }

    private static bool SkipTemplate(int left, int right)
    {
        for (int leftDiv = 1; leftDiv <= left; leftDiv *= 10)
            for (int rightDiv = 1; rightDiv <= right; rightDiv *= 10)
                if (_templatesToSkip.Contains(Tuple.Create(left / leftDiv, right % (rightDiv * 10))))
                    return true;

        return false;
    }

    private static bool IsPrime(int left, int right, int zeroCount)
    {
        return IsPrime(left.ToString() + new string('0', zeroCount) + right.ToString());
    }

    private static bool IsPrime(string left, string right, int zeroCount)
    {
        return IsPrime(left + new string('0', zeroCount) + right);
    }

    private static bool IsPrime(string s)
    {
        using (mpz_t n = new mpz_t(s))
        {
            return n.IsProbablyPrimeRabinMiller(20);
        }
    }

    private static bool IsFragile(int left, int right, int zeroCount)
    {
        string leftStr = left.ToString();
        string rightStr = right.ToString();

        for (int startIndex = 0; startIndex < leftStr.Length - 1; startIndex++)
            for (int count = 1; count < leftStr.Length - startIndex; count++)
                if (IsPrime(leftStr.Remove(startIndex, count), rightStr, zeroCount))
                    return false;

        for (int startIndex = 1; startIndex < rightStr.Length; startIndex++)
            for (int count = 1; count <= rightStr.Length - startIndex; count++)
                if (IsPrime(leftStr, rightStr.Remove(startIndex, count), zeroCount))
                    return false;

        return true;
    }

    private static IEnumerable<Tuple<int, int>> GetTemplates()
    {
        const int maxDigitCount = 8;
        PreparePrimeSieve((int)BigInteger.Pow(10, maxDigitCount));
        for (int digitCount = 2; digitCount <= maxDigitCount; digitCount++)
        {
            for (int leftCount = 1; leftCount < digitCount; leftCount++)
            {
                int rightCount = digitCount - leftCount;
                int maxLeft = (int)BigInteger.Pow(10, leftCount);
                int maxRight = (int)BigInteger.Pow(10, rightCount);

                for (int left = maxLeft / 10; left < maxLeft; left++)
                    for (int right = maxRight / 10; right < maxRight; right++)
                        if (IsValidTemplate(left, right, leftCount, rightCount))
                            yield return Tuple.Create(left, right);
            }

        }
    }

    private static void PreparePrimeSieve(int limit)
    {
        _primeSieve = new BitArray(limit + 1, true);
        _primeSieve[0] = false;
        _primeSieve[1] = false;

        for (int i = 2; i * i <= limit; i++)
            if (_primeSieve[i])
                for (int j = i * i; j <= limit; j += i)
                    _primeSieve[j] = false;
    }

    private static bool IsValidTemplate(int left, int right, int leftCount, int rightCount)
    {
        int rightDigit = right % 10;
        if ((rightDigit != 1) && (rightDigit != 9))
            return false;

        if (left % 10 == 0)
            return false;

        if ((left + right) % 3 == 0)
            return false;

        if (!Coprime(left, right))
            return false;

        int leftDiv = 1;
        for (int i = 0; i <= leftCount; i++)
        {
            int rightDiv = 1;
            for (int j = 0; j <= rightCount; j++)
            {
                int combination = left / leftDiv * rightDiv + right % rightDiv;
                if (_primeSieve[combination])
                    return false;

                rightDiv *= 10;
            }

            leftDiv *= 10;
        }

        return true;
    }

    private static bool Coprime(int a, int b)
    {
        while (b != 0)
        {
            int t = b;
            b = a % b;
            a = t;
        }
        return a == 1;
    }
}

Alte Antwort:

8 0{5436} 4 0{4600} 1

Dies sind einige bemerkenswerte Muster für fragile Primzahlen:

600..00X00..009
900..00X00..009
800..00X00..001
999..99X99..999

wobei X 1, 2, 4, 5, 7 oder 8 sein kann.

Für solche Zahlen müssen wir nur (Länge - 1) mögliche RemoveOperationen berücksichtigen . Die anderen RemoveOperationen erzeugen entweder Duplikate oder offensichtlich zusammengesetzte Zahlen. Ich habe versucht, nach solchen Zahlen mit bis zu 800 Ziffern zu suchen, und festgestellt, dass 4 Muster häufiger auftreten als die anderen: 8007001, 8004001, 9997999 und 6004009. Da Emil und Jakube das Muster 999X999 verwenden, habe ich mich für 8004001 entschieden etwas Abwechslung hinzufügen.

Ich habe dem Algorithmus die folgenden Optimierungen hinzugefügt:

• Ich beginne mit der Suche nach Zahlen mit 7000 Stellen und erhöhe die Länge jedes Mal um 1500, wenn eine fragile Primzahl gefunden wird. Wenn es keine fragile Primzahl mit einer bestimmten Länge gibt, dann erhöhe ich sie um 1. 7000 und 1500 sind nur willkürliche Zahlen, die angemessen schienen.
• Ich verwende Multithreading, um gleichzeitig nach Zahlen mit unterschiedlicher Länge zu suchen.
• Das Ergebnis jeder Prüfung wird in einer Hash-Tabelle gespeichert, um Doppelprüfungen zu vermeiden.
• Ich verwende die Miller-Rabin-Implementierung von Mpir.NET , die sehr schnell ist (MPIR ist ein Fork von GMP).

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;
using Mpir.NET;

class Program
{
    const string _template = "8041";

    private static ConcurrentDictionary<Tuple<int, int>, byte> _compositeNumbers = new ConcurrentDictionary<Tuple<int, int>, byte>();
    private static ConcurrentDictionary<int, int> _leftPrimes = new ConcurrentDictionary<int, int>();
    private static ConcurrentDictionary<int, int> _rightPrimes = new ConcurrentDictionary<int, int>();

    static void Main(string[] args)
    {
        int threadCount = Environment.ProcessorCount;
        Task[] tasks = new Task[threadCount];
        for (int i = 0; i < threadCount; i++)
        {
            int index = i;
            tasks[index] = Task.Run(() => SearchFragilePrimes());
        }
        Task.WaitAll(tasks);
    }

    private const int _lengthIncrement = 1500;
    private static int _length = 7000;
    private static object _lengthLock = new object();
    private static object _consoleLock = new object();

    private static void SearchFragilePrimes()
    {
        int length;
        lock (_lengthLock)
        {
            _length++;
            length = _length;
        }

        while (true)
        {
            lock (_consoleLock)
            {
                Console.WriteLine("{0:T}: length = {1}", DateTime.Now, length);
            }

            bool found = false;
            for (int rightCount = 1; rightCount <= length - 2; rightCount++)
            {
                int leftCount = length - rightCount - 1;
                if (IsFragilePrime(leftCount, rightCount))
                {
                    lock (_consoleLock)
                    {
                        Console.WriteLine("{0:T}: {1} {2}{{{3}}} {4} {2}{{{5}}} {6}",
                            DateTime.Now, _template[0], _template[1], leftCount - 1,
                            _template[2], rightCount - 1, _template[3]);
                    }
                    found = true;
                    break;
                }
            }

            lock (_lengthLock)
            {
                if (found && (_length < length + _lengthIncrement / 2))
                    _length += _lengthIncrement;
                else
                    _length++;
                length = _length;
            }
        }
    }

    private static bool IsFragilePrime(int leftCount, int rightCount)
    {
        int count;
        if (_leftPrimes.TryGetValue(leftCount, out count))
            if (count < rightCount)
                return false;

        if (_rightPrimes.TryGetValue(rightCount, out count))
            if (count < leftCount)
                return false;

        if (!IsPrime(leftCount, rightCount))
            return false;

        for (int i = 0; i < leftCount; i++)
            if (IsPrime(i, rightCount))
                return false;

        for (int i = 0; i < rightCount; i++)
            if (IsPrime(leftCount, i))
                return false;

        return true;
    }

    private static bool IsPrime(int leftCount, int rightCount)
    {
        Tuple<int, int> tuple = Tuple.Create(leftCount, rightCount);
        if (_compositeNumbers.ContainsKey(tuple))
            return false;

        using (mpz_t n = new mpz_t(BuildStr(leftCount, rightCount)))
        {
            bool result = n.IsProbablyPrimeRabinMiller(20);

            if (result)
            {
                _leftPrimes.TryAdd(leftCount, rightCount);
                _rightPrimes.TryAdd(rightCount, leftCount);
            }
            else
                _compositeNumbers.TryAdd(tuple, 0);

            return result;
        }
    }

    private static string BuildStr(int leftCount, int rightCount)
    {
        char[] chars = new char[leftCount + rightCount + 1];
        for (int i = 0; i < chars.Length; i++)
            chars[i] = _template[1];
        chars[0] = _template[0];
        chars[leftCount + rightCount] = _template[3];
        chars[leftCount] = _template[2];
        return new string(chars);
    }
}

Haskell - 1220 - 1277 Stellen für echte Reals wurden korrigiert

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

Besser eins - 1277 Stellen

9{871} 8 9{405}

Haskell-Code

downADigit :: Integer -> [Integer]
downADigit n = f [] 1 where
     f xs a | nma /= n = f (((n `div` a10)*a + nma):xs) a10
            | otherwise = xs where
        a10 = a * 10
        nma = n `mod` a

isFragile = all (not . isPrime') . downADigit
findNextPrime :: Integer -> Integer
findNextPrime n | even n = f (n + 1)
                | otherwise = f n where
    f n | isPrime' n  = n
        | otherwise = f (n + 2)

primesFrom n = f (findNextPrime n) where
    f n = n:f (findNextPrime $ n + 1)

primeLimit = 10000

isPrime' n | n < primeLimit = isPrime n
isPrime' n = all (millerRabinPrimality n) [2,3,5,7,11,13,17,19,984,7283,6628,8398,2983,9849,2739]

-- (eq. to) find2km (2^k * n) = (k,n)
find2km :: Integer -> (Integer,Integer)
find2km n = f 0 n
    where 
        f k m
            | r == 1 = (k,m)
            | otherwise = f (k+1) q
            where (q,r) = quotRem m 2        

-- n is the number to test; a is the (presumably randomly chosen) witness
millerRabinPrimality :: Integer -> Integer -> Bool
millerRabinPrimality n a
    | a <= 1 || a >= n-1 = 
        error $ "millerRabinPrimality: a out of range (" 
              ++ show a ++ " for "++ show n ++ ")" 
    | n < 2 = False
    | even n = False
    | b0 == 1 || b0 == n' = True
    | otherwise = iter (tail b)
    where
        n' = n-1
        (k,m) = find2km n'
        b0 = powMod n a m
        b = take (fromIntegral k) $ iterate (squareMod n) b0
        iter [] = False
        iter (x:xs)
            | x == 1 = False
            | x == n' = True
            | otherwise = iter xs

-- (eq. to) pow' (*) (^2) n k = n^k
pow' :: (Num a, Integral b) => (a->a->a) -> (a->a) -> a -> b -> a
pow' _ _ _ 0 = 1
pow' mul sq x' n' = f x' n' 1
    where 
        f x n y
            | n == 1 = x `mul` y
            | r == 0 = f x2 q y
            | otherwise = f x2 q (x `mul` y)
            where
                (q,r) = quotRem n 2
                x2 = sq x

mulMod :: Integral a => a -> a -> a -> a
mulMod a b c = (b * c) `mod` a
squareMod :: Integral a => a -> a -> a
squareMod a b = (b * b) `rem` a

-- (eq. to) powMod m n k = n^k `mod` m
powMod :: Integral a => a -> a -> a -> a
powMod m = pow' (mulMod m) (squareMod m)

-- simple for small primes
primes :: [Integer]
primes = 2:3:primes' where
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n)
                                   $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
          | otherwise = f primes where
            f (p:ps) | p*p <= n = if n `rem` p == 0 then False else f ps
                     | otherwise = True

main = do
    print . head $ filter isFragile (primesFrom $ 10^1000)