Rozważ funkcję, Remove(n, startIndex, count)która usuwa countcyfry z numeru nrozpoczynającego się od cyfry na pozycji startIndex. Przykłady:

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

Będziemy nazywać liczbę pierwszą X kruchą, jeśli każda możliwa Removeoperacja spowoduje, że będzie ona niepierwszorzędna. Na przykład 80651 jest kruchą liczbą pierwszą, ponieważ wszystkie następujące liczby nie są liczbami pierwszymi:

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

Cel

Napisz program, który znajdzie największą kruchą liczbę pierwszą. Edycja: usunięto limit czasu, ponieważ istniał względnie sprawiedliwy sposób na obejście go.

Wynik to krucha liczba pierwsza znaleziona przez twój program. W przypadku remisu wygrywa wcześniejsze zgłoszenie.

Zasady

• Możesz używać dowolnego języka i dowolnych bibliotek stron trzecich.
• Program uruchamiasz na własnym sprzęcie.
• Możesz użyć probabilistycznych testów pierwszeństwa.
• Wszystko jest w bazie 10.

Wiodące wpisy

• 6629 cyfr według Qualtagh (Java)
• 5048 cyfr według Emila (Python 2)
• 2268 cyfr według Jakube (Python 2)

Edycja: Dodałem własną odpowiedź.

• 28164 cyfry według Suboptimus Prime, oparte na algorytmie Qualtagha (C #)

Java - 3144 3322 6629 cyfr

6 0{3314} 8969999

6 0{6623} 49099

To rozwiązanie jest oparte na odpowiedzi FryAmTheEggman .

1. Ostatnia cyfra to 1 lub 9.
2. Jeśli ostatnia cyfra to 1, to poprzednia to 0, 8 lub 9.
3. Jeśli ostatnia cyfra to 9, to poprzednia to 0, 4, 6 lub 9.
4. ...

Co jeśli będziemy kopać głębiej?

Staje się strukturą drzewa:

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

Nazwijmy R prawy złożony, jeśli R i wszystkie jego zakończenia są złożone.

Będziemy iterować po wszystkich liczbach zespolonych w pierwszej kolejności: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901 itd.

Liczby zaczynające się od zera nie są sprawdzane pod kątem pierwszeństwa, ale są potrzebne do budowania kolejnych liczb.

Poszukamy liczby docelowej N w postaci X00 ... 00R, gdzie X jest jednym z 4, 6, 8 lub 9, a R jest prawym kompozytu. X nie może być liczbą pierwszą. X nie może być 0. A X nie może wynosić 1, ponieważ jeśli R kończy się na 1 lub 9, wówczas N będzie zawierać 11 lub 19.

Jeśli XR zawiera liczby pierwsze po operacji „usuń”, to XYR będzie je również zawierał dla dowolnego Y. Nie powinniśmy więc przechodzić przez gałęzie zaczynające się od R.

Niech X będzie stałą, powiedzmy 6.

Pseudo kod:

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 ).
        }
      }
    }
  }
}

Powinniśmy ograniczyć liczbę zer, ponieważ znalezienie liczby pierwszej w postaci X + zera + R może zająć zbyt długo (lub na zawsze, jeśli wszystkie są złożone).

Prawdziwy kod jest dość szczegółowy i można go znaleźć tutaj .

Badanie pierwotności liczb w długim zakresie int jest wykonywane przez deterministyczny wariant testu Millera. W przypadku liczb BigInteger najpierw wykonywany jest podział próbny, a następnie test BailliePSW. Jest to probabilistyczne, ale całkiem pewne. I jest szybszy niż test Millera-Rabina (powinniśmy zrobić wiele iteracji dla tak dużych liczb w Millerze-Rabinie, aby uzyskać wystarczającą dokładność).

Edycja: pierwsza próba była niepoprawna. Powinniśmy również zignorować gałęzie zaczynające się na R, jeśli X0 ... 0R jest liczbą pierwszą. Wtedy X0 ... 0YR nie byłby kruchą liczbą pierwszą. Dodano więc dodatkową kontrolę. To rozwiązanie wydaje się poprawne.

Edycja 2: dodano optymalizację. Jeśli (X + R) można podzielić przez 3, to (X + zera + R) jest również podzielne przez 3. Więc (X + zera + R) nie może być w tym przypadku liczbą pierwszą i takie R mogą zostać pominięte.

Edycja 3: nie było konieczne pomijanie cyfr pierwszych, jeśli nie znajdują się one na ostatniej lub pierwszej pozycji. Zakończenia takie jak 21 lub 51 są w porządku. Ale to niewiele zmienia.

Wnioski:

1. Moją ostatnią odpowiedzią było sprawdzenie, czy jestem delikatny przez 100 minut. Wyszukiwanie odpowiedzi (sprawdzenie wszystkich poprzednich wariantów) zajęło około 15 minut. Tak, nie ma sensu ograniczać czasu wyszukiwania (możemy rozpocząć wyszukiwanie od numeru docelowego, więc czas wyniósłby zero). Ale może być sensowne ograniczenie czasu sprawdzania, jak w tym pytaniu .
2. Odpowiedź 60 ... 049099 ma cyfrę 4 pośrodku. Jeśli dotknie go operacja „usuń”, liczba staje się podzielna przez 3. Dlatego powinniśmy sprawdzić operacje usuwania po lewej i prawej stronie. Prawa strona jest za krótka. Długość lewej strony wynosi prawie n = długość (N).
3. Testy pierwotności, takie jak BPSW i Miller-Rabin, wykorzystują stałą liczbę wykładników modułowych. Jego złożoność wynosi O (M (n) * n) zgodnie z tą stroną , gdzie M (n) jest złożonością mnożenia. Java wykorzystuje algorytmy Toom-Cook i Karatsuba, ale dla uproszczenia weźmiemy algorytm naukowy. M (n) = n ² . Zatem złożoność testowania pierwotności wynosi O (n ³ ).
4. Powinniśmy sprawdzić wszystkie liczby od długości = 6 do 6629. Weźmy min = 1 i max = n dla wspólności. Cała złożoność czeku wynosi O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. Odpowiedź Emila ma tę samą asymptotyczną kontrolę. Ale stały współczynnik jest niższy. Cyfra „7” stoi pośrodku cyfry. Lewa strona i prawa strona mogą być prawie równe. Daje to (n / 2), ⁴ * 2 = N ⁴ / 8. przyspieszenia 8x. Liczby w postaci 9 ... 9Y9 ... 9 mogą być 1,7 razy dłuższe niż w postaci X0 ... 0R o tym samym czasie sprawdzania.

Python 2 - 126 1221 1337 1719 2268 cyfr

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Istnieje około len (n) ^ 2 wynikowych liczb Remove (n, startIndex, count). Próbowałem zminimalizować te liczby. Jeśli wiele cyfr obok siebie jest takich samych, wiele z tych liczb wynikowych można zignorować, ponieważ pojawiają się wiele razy.

Podszedłem więc do skrajności, tylko 9s i trochę pierwsza w środku. Spojrzałem również na kruchą liczbę pierwszą poniżej 1 miliona i zobaczyłem, że są takie kruche pierwsze. Wyszukiwanie liczb z 2 9 na końcu działa naprawdę dobrze, nie wiem, dlaczego. 1 liczba, 3 lub 4 9 na końcu daje mniejsze kruche liczby pierwsze.

Wykorzystuje moduł pyprimes . Nie jestem pewien, czy to jest dobre. Wykorzystuje test miller_rabin, więc jest probabilistyczny.

Program znajduje tę 126-cyfrową kruchą liczbę pierwszą w około 1 minutę, a przez resztę czasu szuka bez powodzenia.

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

edytować:

Właśnie zobaczyłem, że usunąłeś limit czasu. Uruchomię program przez noc, może pojawią się naprawdę duże, delikatne liczby pierwsze.

edycja 2:

Przyspieszyłem mój oryginalny program, więc nadal nie ma rozwiązania z więcej niż 126 cyframi. Wskoczyłem więc do pociągu i szukałem x 9s + 1 cyfra + y 9s. Zaletą jest to, że musisz sprawdzić liczby O (n) pod kątem pierwszeństwa, jeśli naprawisz to. Szybko odnajduje 1221.

edycja 3:

W przypadku liczby 2268 cyfr używam tego samego programu, dzieliłem tylko pracę na wiele rdzeni.

Python 2.7 - 429623069 99993799

Jak dotąd żadnych optymalizacji. Wystarczy użyć kilku trywialnych spostrzeżeń na temat delikatnych liczb pierwszych (dzięki Rainbolt na czacie):

1. Kruche liczby pierwsze muszą kończyć się na 1 lub 9 (liczby pierwsze nie są parzyste, a ostatnia cyfra nie może być liczbą pierwszą)
2. Kruche liczby pierwsze kończące się na 1 muszą zaczynać się od 8 lub 9 (pierwsza liczba nie może być liczbą pierwszą, a 11, 41 i 61 i wszystkie są liczbami pierwszymi)
3. Kruche liczby pierwsze kończące się na 9 muszą zaczynać się od 4,6 lub 9 (patrz argumentacja 1, ale tylko 89 jest liczbą pierwszą)

Próbuję tylko uruchomić piłkę :)

To technicznie trwa nieco ponad 15 minut, ale sprawdza tylko jeden numer w dogrywce.

is_primejest wzięty stąd (użył go tutaj isaacg ) i jest probabilistyczny.

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

Tylko uwaga, kiedy zacznę to z n=429623069wstaję do482704669 . Dodatkowa cyfra naprawdę zabija tę strategię ...

Python 2, 828 cyfr 5048 cyfr

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

Jak wskazał @Jakube, pierwsza liczba przesłana przeze mnie nie była tak naprawdę krucha z powodu błędu w moim kodzie. Naprawienie błędu było łatwe, ale znacznie spowolniło algorytm.

Ograniczyłem się do łatwo przeszukiwalnego podzbioru delikatnych liczb pierwszych, a mianowicie tych, które składają się tylko z cyfry 9 i dokładnie jednej cyfry 7.

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))

Użyłem tej samej is_primefunkcji ( stąd ) jak @FryAmTheEggman.

Edytować:

Wprowadziłem dwie zmiany, aby przyspieszyć algorytm:

• Staram się pomijać jak najwięcej kontroli pierwotności, jak to możliwe, i cofam się tylko wtedy, gdy zostanie znaleziona potencjalna krucha liczba pierwsza, aby upewnić się, że jest naprawdę krucha. Istnieje niewielka liczba zduplikowanych kontroli, więc z grubsza zapamiętałem funkcję sprawdzania liczby pierwszych.

• Dla liczb formularza b*'9' + '7' + c*'9'ograniczyłem rozmiar b. Im niższy limit, tym mniej liczb trzeba sprawdzić, ale szanse rosną, aby w ogóle nie znaleźć dużej kruchej liczby pierwszej. Jakoś arbitralnie wybrałem 222 jako limit.

Przy kilku tysiącach cyfr pojedynczy test wstępny może już zająć mojemu programowi kilka sekund. Tak więc prawdopodobnie nie mogę nic lepszego z tym podejściem.

Sprawdź poprawność mojego zgłoszenia. Ze względu na probabilistyczną kontrolę pierwotności mój numer teoretycznie nie może być liczbą pierwszą, ale jeśli tak, to powinien być kruchy. Albo zrobiłem coś złego. :-)

C #, 10039 28164 cyfry

6 0{28157} 169669

Edycja: Stworzyłem inny program oparty na algorytmie Qualtagha z niewielkimi modyfikacjami:

• Szukam liczb w postaci L000 ... 000R, gdzie L jest kompozytem lewym, R jest kompozytem prawym. Pozwoliłem, aby lewy numer kompozytowy L miał wiele cyfr, chociaż jest to głównie zmiana stylistyczna i prawdopodobnie nie wpływa to na wydajność algorytmu.
• Dodałem wielowątkowość, aby przyspieszyć wyszukiwanie.

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;
    }
}

Stara odpowiedź:

8 0{5436} 4 0{4600} 1

Istnieje kilka godnych uwagi wzorów na kruche liczby pierwsze:

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

gdzie X może wynosić 1, 2, 4, 5, 7 lub 8.

W przypadku takich liczb musimy jedynie wziąć pod uwagę (długość - 1) możliwe Removeoperacje. Inne Removeoperacje generują albo duplikaty, albo oczywiście liczby zespolone. Próbowałem wyszukać wszystkie takie liczby z maksymalnie 800 cyframi i zauważyłem, że 4 wzorce pojawiają się częściej niż pozostałe: 8007001, 8004001, 9997999 i 6004009. Ponieważ Emil i Jakube używają wzoru 999X999, postanowiłem użyć 8004001 tylko dodać trochę urozmaicenia.

Do algorytmu dodałem następujące optymalizacje:

• Zaczynam szukać od liczb zawierających 7000 cyfr, a następnie zwiększam długość o 1500 za każdym razem, gdy zostanie znaleziona krucha liczba pierwsza. Jeśli nie ma kruchej liczby pierwszej o danej długości, zwiększam ją o 1. 7000 i 1500 to tylko dowolne liczby, które wydawałyby się odpowiednie.
• Używam wielowątkowości do wyszukiwania liczb o różnej długości w tym samym czasie.
• Wynik każdej kontroli wstępnej jest przechowywany w tabeli skrótów, aby zapobiec powielaniu kontroli.
• Korzystam z implementacji Miller-Rabin z Mpir.NET , która jest bardzo szybka (MPIR jest rozwidleniem 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 - naprawiono 1220 1277 cyfr dla prawdziwych reali

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

Lepiej jeden - 1277 cyfr

9{871} 8 9{405}

Kod Haskell

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)