Considere la función Remove(n, startIndex, count)que elimina countdígitos del número que ncomienza desde el dígito en la posición startIndex. Ejemplos:

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

Llamaremos al número primo X frágil si todas las Removeoperaciones posibles lo hacen no primo. Por ejemplo, 80651 es un primo frágil porque todos los siguientes números no son primos:

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

Objetivo

Escribe un programa que encuentre el primo frágil más grande. Editar: eliminó el límite de tiempo porque había una forma relativamente justa de eludirlo.

El puntaje es el número primo frágil encontrado por su programa. En caso de empate, gana la presentación anterior.

Reglas

• Puede usar cualquier idioma y cualquier biblioteca de terceros.
• Ejecutas el programa en tu propio hardware.
• Puede usar pruebas de primalidad probabilística.
• Todo está en la base 10.

Entradas principales

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

Editar: he añadido mi propia respuesta.

• 28164 dígitos por Suboptimus Prime, basado en el algoritmo de Qualtagh (C #)

Java - 3144 3322 6629 dígitos

6 0{3314} 8969999

6 0{6623} 49099

Esta solución se basa en la respuesta de FryAmTheEggman .

1. El último dígito es 1 o 9.
2. Si el último dígito es 1, el anterior es 0, 8 o 9.
3. Si el último dígito es 9, el anterior es 0, 4, 6 o 9.
4. ...

¿Qué pasa si cavamos más profundo?

Se convierte en una estructura de árbol:

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

Llamemos al número R compuesto derecho si R y todas sus terminaciones son compuestas.

Vamos a iterar sobre todos los números compuestos correctos en primer lugar: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901, etc.

Los números que comienzan con cero no se comprueban por primalidad, pero son necesarios para construir más números.

Buscaremos un número objetivo N en la forma X00 ... 00R, donde X es uno de 4, 6, 8 o 9 y R es el compuesto correcto. X no puede ser primo. X no puede ser 0. Y X no puede ser 1 porque si R termina con 1 o 9, entonces N contendría 11 o 19.

Si XR contiene números primos después de la operación "eliminar", XYR también los contendría para cualquier Y. Por lo tanto, no deberíamos atravesar ramas a partir de R.

Sea X una constante, digamos 6.

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

Deberíamos limitar la cantidad de ceros porque puede llevar demasiado tiempo encontrar un número primo en forma X + ceros + R (o para siempre si todos son compuestos).

El código real es bastante detallado y se puede encontrar aquí .

La prueba de primalidad para números en rango int largo se realiza mediante la variante determinista de la prueba de Miller. Para los números de BigInteger, primero se realiza una división de prueba y luego la prueba BailliePSW. Es probabilístico pero bastante seguro. Y es más rápido que la prueba de Miller-Rabin (deberíamos hacer muchas iteraciones para números tan grandes en Miller-Rabin para obtener suficiente precisión).

Editar: el primer intento fue incorrecto. También debemos ignorar las ramas que comienzan con R si X0 ... 0R es primo. Entonces X0 ... 0YR no sería primo frágil. Entonces se agregó un cheque adicional. Esta solución parece ser correcta.

Edición 2: se agregó una optimización. Si (X + R) es divisible entre 3, entonces (X + ceros + R) también es divisible entre 3. Entonces (X + ceros + R) no puede ser primo en este caso y se pueden omitir tales R.

Edición 3: no fue necesario omitir los dígitos primos si no están en la última o primera posición. Entonces finales como 21 o 51 están bien. Pero no cambia mucho nada.

Conclusiones:

1. Mi última respuesta fue comprobar si era frágil durante 100 minutos. La búsqueda de la respuesta (verificando todas las variantes anteriores) tomó aproximadamente 15 minutos. Sí, no tiene sentido restringir el tiempo de búsqueda (podemos comenzar a buscar desde el número objetivo, por lo que el tiempo sería cero). Pero podría ser significativo restringir el tiempo de verificación como en esta pregunta .
2. La respuesta 60 ... 049099 tiene el dígito 4 en el medio. Si la operación "eliminar" lo toca, el número se vuelve divisible por 3. Por lo tanto, debemos verificar las operaciones de eliminación en los lados izquierdo y derecho. El lado derecho es demasiado corto. La longitud del lado izquierdo es casi n = longitud (N).
3. Las pruebas de primalidad como BPSW y Miller-Rabin utilizan una cantidad constante de exponenciaciones modulares. Su complejidad es O (M (n) * n) de acuerdo con esta página , donde M (n) es la complejidad de la multiplicación. Java usa los algoritmos Toom-Cook y Karatsuba, pero tomaremos el algoritmo académico por simplicidad. M (n) = n ² . Entonces, la complejidad de la prueba de primalidad es O (n ³ ).
4. Deberíamos verificar todos los números desde length = 6 hasta 6629. Tomemos min = 1 y max = n para la similitud. Toda la complejidad de la verificación es O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. La respuesta de Emil tiene la misma comprobación de asintóticos. Pero el factor constante es más bajo. El dígito "7" está parado en el medio del número. El lado izquierdo y el lado derecho pueden ser casi iguales. Se da (n / 2) ⁴ * 2 = n ⁴ / 8. Speedup: 8X. Los números en la forma 9 ... 9Y9 ... 9 pueden ser 1.7 veces más largos que en la forma X0 ... 0R con el mismo tiempo de verificación.

Python 2 - 126 1221 1337 1719 2268 dígitos

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Hay aproximadamente len (n) ^ 2 números resultantes de Remove (n, startIndex, count). Traté de minimizar esos números. Si hay muchos dígitos uno al lado del otro, muchos de estos números resultantes pueden ignorarse, ya que aparecen varias veces.

Así que lo llevé al extremo, solo 9 segundos y un poco primo en el medio. También eché un vistazo a la prima frágil por debajo de 1 millón, y vi que hay una prima tan frágil. Buscar números con 2 9 al final funciona muy bien, no estoy seguro de por qué. 1 número, 3 o 4 9 al final da como resultado primos frágiles más pequeños.

Utiliza el módulo pyprimes . No estoy seguro, si es bueno. Utiliza la prueba miller_rabin, por lo que es probabilístico.

El programa encuentra este primo frágil de 126 dígitos en aproximadamente 1 minuto, y durante el resto del tiempo busca sin éxito.

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:

Acabo de ver que eliminaste el límite de tiempo. Ejecutaré el programa durante la noche, tal vez aparezcan algunos primos frágiles realmente grandes.

editar 2:

Hice mi programa original más rápido, pero aún no hay solución con más de 126 dígitos. Entonces me subí al tren y busqué x 9s + 1 dígito + y 9s. La ventaja es que tiene que verificar los números O (n) para primalidad, si corrige y. Encuentra un 1221 bastante rápido.

editar 3:

Para el número de 2268 dígitos utilizo el mismo programa, solo dividí el trabajo en múltiples núcleos.

Python 2.7 - 429623069 99993799

Sin optimizaciones de ningún tipo, hasta ahora. Simplemente usando algunas observaciones triviales sobre primos frágiles (gracias a Rainbolt en el chat):

1. Los primos frágiles deben terminar en 1 o 9 (los primos no son pares y el último dígito no debe ser primo)
2. Los primos frágiles que terminan en 1 deben comenzar con 8 o 9 (el primer número no puede ser primo, y 11, 41 y 61 y son todos primos)
3. Los primos frágiles que terminan en 9 deben comenzar con 4,6 o 9 (ver razonamiento para 1, pero solo 89 es primo)

Solo trato de hacer rodar la pelota :)

Esto técnicamente dura un poco más de 15 minutos, pero solo verifica un solo número en el tiempo extra.

is_primese toma de aquí (isaacg lo usó aquí ) y es 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

Solo una nota, cuando comienzo esto con n=429623069me levanto 482704669. El dígito extra realmente parece matar esta estrategia ...

Python 2, 828 dígitos 5048 dígitos

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

Como señaló @Jakube, la primera prima que envié no era realmente frágil debido a un error en mi código. Arreglar el error fue fácil pero también hizo que el algoritmo fuera significativamente más lento.

Me limité a un subconjunto de búsqueda fácil de los primos frágiles, es decir, aquellos que solo consisten en el dígito 9 y exactamente un 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))

Usé la misma is_primefunción (desde aquí ) que @FryAmTheEggman.

Editar:

Hice dos cambios para acelerar el algoritmo:

• Intento omitir tantas verificaciones de primalidad como sea posible y solo retrocedo cuando se encuentra una posible prima frágil para asegurarme de que sea realmente frágil. Hay una pequeña cantidad de verificaciones duplicadas, así que memoricé crudamente la función de verificación principal.

• Para los números del formulario b*'9' + '7' + c*'9', limité el tamaño de b. Cuanto más bajo es el límite, menos números deben verificarse, pero aumentan las posibilidades de no encontrar ningún primo frágil grande. Elegí arbitrariamente 222 como límite.

Con unos pocos miles de dígitos, una sola verificación principal ya puede demorar unos segundos mi programa. Entonces, probablemente no pueda hacerlo mucho mejor con este enfoque.

No dude en verificar la corrección de mi envío. Debido a la comprobación de primalidad probabilística, mi número teóricamente podría no ser primo, pero si lo es, debería ser frágil. O he hecho algo mal. :-)

C #, 10039 28164 dígitos

6 0{28157} 169669

Editar: Hice otro programa basado en el algoritmo de Qualtagh con algunas modificaciones menores:

• Estoy buscando los números de la forma L000 ... 000R, donde L es compuesto izquierdo, R es compuesto derecho. Permití que el número compuesto izquierdo L tuviera varios dígitos, aunque esto es principalmente un cambio estilístico, y probablemente no afecta la eficiencia del algoritmo.
• He agregado subprocesos múltiples para acelerar la búsqueda.

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

Vieja respuesta:

8 0{5436} 4 0{4600} 1

Hay algunos patrones notables para números primos frágiles:

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

donde X puede ser 1, 2, 4, 5, 7 u 8.

Para tales números solo tenemos que considerar (longitud - 1) posibles Removeoperaciones. Las otras Removeoperaciones producen números duplicados o obviamente compuestos. Traté de buscar todos esos números con hasta 800 dígitos y noté que aparecen 4 patrones con más frecuencia que el resto: 8007001, 8004001, 9997999 y 6004009. Dado que Emil y Jakube están usando el patrón 999X999, decidí usar 8004001 solo Para agregar algo de variedad.

He agregado las siguientes optimizaciones al algoritmo:

• Empiezo a buscar desde números con 7000 dígitos y luego incremento la longitud en 1500 cada vez que se encuentra una prima frágil. Si no hay un número primo frágil con una longitud dada, entonces lo incremento en 1. 7000 y 1500 son solo números arbitrarios que parecían apropiados.
• Estoy usando subprocesos múltiples para buscar los números con diferente longitud al mismo tiempo.
• El resultado de cada verificación principal se almacena en una tabla hash para evitar verificaciones duplicadas.
• Estoy usando la implementación Miller-Rabin de Mpir.NET , que es muy rápida (MPIR es una bifurcación de 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 corregidos para verdaderos reales

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

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