Considere a função Remove(n, startIndex, count)que remove countdígitos do número ncomeçando do dígito na posição startIndex. Exemplos:

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

Vamos chamar o número primo X frágil se todas as Removeoperações possíveis o tornarem não primo. Por exemplo, 80651 é um primo frágil porque todos os seguintes números não são primos:

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

Objetivo

Escreva um programa que encontre o maior primo frágil. Edit: removeu o limite de tempo porque havia uma maneira relativamente justa de contorná-lo.

A pontuação é o número primo frágil encontrado pelo seu programa. Em caso de empate, a finalização anterior vence.

Regras

• Você pode usar qualquer idioma e qualquer biblioteca de terceiros.
• Você executa o programa em seu próprio hardware.
• Você pode usar testes probabilísticos de primalidade.
• Tudo está na base 10.

Entradas principais

• 6629 dígitos por Qualtagh (Java)
• 5048 dígitos por Emil (Python 2)
• 2268 dígitos por Jakube (Python 2)

Edit: eu adicionei minha própria resposta.

• 28164 dígitos pelo Suboptimus Prime, com base no algoritmo de Qualtagh (C #)

Java - 3144 3322 6629 dígitos

6 0{3314} 8969999

6 0{6623} 49099

Esta solução é baseada na resposta de FryAmTheEggman .

1. O último dígito é 1 ou 9.
2. Se o último dígito for 1, o anterior será 0, 8 ou 9.
3. Se o último dígito for 9, o anterior será 0, 4, 6 ou 9.
4. ...

E se cavarmos mais fundo?

Torna-se uma estrutura de árvore:

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

Vamos chamar o número R composto à direita se R e todas as suas terminações forem compostas.

Vamos iterar sobre todos os números compostos corretos da maneira primeira: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901 etc.

Os números que começam com zero não são verificados quanto à primalidade, mas são necessários para criar mais números.

Procuraremos um número alvo N no formato X00 ... 00R, onde X é um de 4, 6, 8 ou 9 e R é o composto correto. X não pode ser primo. X não pode ser 0. E X não pode ser 1 porque se R termina com 1 ou 9, então N conteria 11 ou 19.

Se o XR contiver números primos após a operação "remover", o XYR os conteria também para qualquer Y. Portanto, não devemos percorrer ramificações a partir de R.

Seja X uma constante, digamos 6.

Pseudo-código:

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

Devemos limitar a quantidade de zeros, pois pode levar muito tempo para encontrar um número primo no formato X + zeros + R (ou para sempre, se todos eles forem compostos).

O código real é bastante detalhado e pode ser encontrado aqui .

O teste de primazia para números no intervalo int longo é realizado pela variante determinística do teste de Miller. Para os números do BigInteger, primeiro é realizada uma divisão de teste e, em seguida, o teste BailliePSW. É probabilístico, mas bastante certo. E é mais rápido que o teste de Miller-Rabin (devemos fazer muitas iterações para que números tão grandes em Miller-Rabin ganhem precisão suficiente).

Editar: a primeira tentativa estava incorreta. Também devemos ignorar os ramos que começam com R se X0 ... 0R é primo. Então X0 ... 0YR não seria primo frágil. Portanto, uma verificação adicional foi adicionada. Esta solução parece estar correta.

Editar 2: adicionada uma otimização. Se (X + R) é divisível por 3, (X + zeros + R) também é divisível por 3. Portanto, X + zeros + R) não podem ser primos nesse caso e esses Rs podem ser ignorados.

Edição 3: não era necessário pular dígitos primos se eles não estiverem na última ou na primeira posição. Portanto, finais como 21 ou 51 estão ok. Mas isso não muda muito.

Conclusões:

1. Minha última resposta foi checar por ser frágil por 100 minutos. A busca da resposta (verificando todas as variantes anteriores) levou cerca de 15 minutos. Sim, não faz sentido restringir o tempo de pesquisa (podemos começar a pesquisar a partir do número de destino, para que o tempo seja zero). Mas pode ser significativo restringir o tempo de verificação, como nesta pergunta .
2. A resposta 60 ... 049099 tem o dígito 4 no meio. Se a operação "remover" a tocar, o número se tornará divisível por 3. Portanto, devemos verificar as operações de remoção nos lados esquerdo e direito. O lado direito é muito curto. O comprimento do lado esquerdo é quase n = comprimento (N).
3. Testes de primazia como BPSW e Miller-Rabin usam quantidade constante de exponenciações modulares. Sua complexidade é O (M (n) * n) de acordo com esta página , onde M (n) é a complexidade da multiplicação. Java usa os algoritmos Toom-Cook e Karatsuba, mas usaremos o algoritmo escolar para simplificar. H (n) = N ² . Portanto, a complexidade dos testes de primalidade é O (n ³ ).
4. Devemos verificar todos os números de comprimento = 6 a 6629. Vamos considerar min = 1 e max = n para a semelhança. Toda a complexidade da verificação é O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. A resposta de Emil tem os mesmos assintóticos verificadores. Mas o fator constante é menor. O dígito "7" está no meio do número. O lado esquerdo e o lado direito podem ser quase iguais. Dá (n / 2) ⁴ * 2 = n ⁴ / 8. Aceleração: 8X. Os números no formato 9 ... 9Y9 ... 9 podem ser 1,7 vezes maiores que no formato X0 ... 0R com o mesmo tempo de verificação.

Python 2 - 126 1221 1337 1719 2268 dígitos

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Existem cerca de len (n) ^ 2 números resultantes de Remove (n, startIndex, count). Eu tentei minimizar esses números. Se houver muitos dígitos próximos um do outro, os mesmos números resultantes poderão ser ignorados, pois aparecem várias vezes.

Então eu levei ao extremo, apenas 9s e um pouco de prima no meio. Também dei uma olhada no primo frágil abaixo de 1 milhão e vi que existem primos tão frágeis. Procurar números com 2 9s no final funciona muito bem, não sei por quê. 1 número, 3 ou 4 9s no final resulta em números primos frágeis menores.

Ele usa o módulo pyprimes . Não tenho certeza, se é bom. Ele usa o teste miller_rabin, portanto é probabilístico.

O programa encontra esse primo frágil de 126 dígitos em cerca de 1 minuto e, durante o resto do tempo, procura sem sucesso.

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

editar:

Acabei de ver que você removeu o prazo. Vou executar o programa durante a noite, talvez alguns primos frágeis realmente grandes apareçam.

editar 2:

Tornei meu programa original mais rápido, mas ainda não há solução com mais de 126 dígitos. Então pulei no trem e procurei x 9s + 1 dígito + y 9s. A vantagem é que você deve verificar os números O (n) em busca de primalidade, se você o corrigir. Encontra um 1221 rapidamente.

editar 3:

Para o número de 2268 dígitos, eu uso o mesmo programa, apenas dividi o trabalho em vários núcleos.

Python 2.7 - 429623069 99993799

Até o momento, nenhuma otimização. Apenas usando algumas observações triviais sobre números primos frágeis (graças a Rainbolt no bate-papo):

1. Os números primos frágeis devem terminar em 1 ou 9 (os primos não são pares e o dígito final não deve ser primo)
2. Os números primos frágeis que terminam em 1 devem começar com 8 ou 9 (o primeiro número não pode ser primo e 11, 41 e 61 e são todos números primos)
3. Os números primos frágeis que terminam em 9 devem começar com 4,6 ou 9 (veja o raciocínio para 1, mas apenas 89 é primo)

Apenas tentando fazer a bola rolar :)

Tecnicamente, esse processo dura um pouco mais de 15 minutos, mas verifica apenas um único número no tempo extra.

is_primeé retirado daqui (isaacg o usou aqui ) e é probabilístico.

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

Apenas uma observação: quando eu começo isso, n=429623069eu acordo 482704669. O dígito extra realmente parece matar essa estratégia ...

Python 2, 828 dígitos 5048 dígitos

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

Como o @Jakube apontou, o primeiro prime que enviei não era realmente frágil devido a um erro no meu código. A correção do bug foi fácil, mas também tornou o algoritmo significativamente mais lento.

Limitei-me a um subconjunto facilmente pesquisável dos números primos frágeis, ou seja, aqueles que consistem apenas no dígito 9 e exatamente um dígito 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))

Eu usei a mesma is_primefunção ( daqui ) como @FryAmTheEggman.

Editar:

Fiz duas alterações para tornar o algoritmo mais rápido:

• Tento pular o máximo de checagens de primalidade possível e só volto quando um potencial frágil em potencial é encontrado para garantir que ele seja realmente frágil. Há um pequeno número de verificações duplicadas, então memorizei grosseiramente a função de verificação primária.

• Para os números do formulário b*'9' + '7' + c*'9', limitei o tamanho de b. Quanto menor o limite, menos números precisam ser verificados, mas as chances aumentam para não encontrar nenhum primo grande e frágil. Eu meio que escolhi arbitrariamente 222 como o limite.

Com alguns milhares de dígitos, uma única verificação principal já pode demorar alguns segundos para o meu programa. Então, provavelmente não posso fazer muito melhor com essa abordagem.

Por favor, sinta-se livre para verificar a exatidão da minha submissão. Devido à verificação probabilística de primalidade, meu número não pode ser teoricamente primo, mas, se for, deve ser frágil. Ou eu fiz algo errado. :-)

C #, 10039 28164 dígitos

6 0{28157} 169669

Edit: Eu fiz outro programa baseado no algoritmo de Qualtagh com algumas pequenas modificações:

• Estou procurando os números no formato L000 ... 000R, onde L é composto à esquerda, R é composto à direita. Eu permiti que o número composto esquerdo L tivesse vários dígitos, embora isso seja principalmente uma alteração estilística e provavelmente não afete a eficiência do algoritmo.
• Adicionei multithreading para acelerar a pesquisa.

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

Resposta antiga:

8 0{5436} 4 0{4600} 1

Existem alguns padrões notáveis ​​para primos frágeis:

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

onde X pode ser 1, 2, 4, 5, 7 ou 8.

Para esses números, precisamos considerar apenas (comprimento - 1) Removeoperações possíveis . As outras Removeoperações produzem números duplicados ou obviamente compostos. Tentei procurar todos esses números com até 800 dígitos e notei que quatro padrões aparecem com mais frequência do que o restante: 8007001, 8004001, 9997999 e 6004009. Como Emil e Jakube estão usando o padrão 999X999, decidi usar 8004001 apenas para adicionar alguma variedade.

Adicionei as seguintes otimizações ao algoritmo:

• Começo a pesquisar a partir de números com 7000 dígitos e, em seguida, incremento o comprimento em 1500 toda vez que um primo frágil é encontrado. Se não houver primo frágil com um determinado comprimento, eu o incremento em 1. 7000 e 1500 são apenas números arbitrários que pareciam apropriados.
• Estou usando o multithreading para procurar os números com comprimentos diferentes ao mesmo tempo.
• O resultado de cada verificação principal é armazenado em uma tabela de hash para evitar verificações duplicadas.
• Estou usando a implementação Miller-Rabin do Mpir.NET , que é muito rápida (MPIR é um fork do 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 dígitos corrigidos para reais reais

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

Melhor - 1277 dígitos

9{871} 8 9{405}

Código 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)