Considérez la fonction Remove(n, startIndex, count)qui supprime les countchiffres du nombre nà partir du chiffre à la position startIndex. Exemples:

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

Nous appellerons le nombre premier X fragile si chaque Removeopération possible le rend non premier. Par exemple, 80651 est un nombre premier fragile car tous les nombres suivants ne sont pas premiers:

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

Objectif

Écrivez un programme qui trouve le plus grand nombre premier fragile. Edit: suppression du délai, car il y avait un moyen relativement juste de le contourner.

Le score est le nombre premier fragile trouvé par votre programme. En cas d'égalité, la soumission précédente l'emporte.

Règles

• Vous pouvez utiliser n'importe quelle langue et toute bibliothèque tierce.
• Vous exécutez le programme sur votre propre matériel.
• Vous pouvez utiliser des tests de primalité probabilistes.
• Tout est en base 10.

Entrées principales

• 6629 chiffres par Qualtagh (Java)
• 5048 chiffres par Emil (Python 2)
• 2268 chiffres par Jakube (Python 2)

Edit: j'ai ajouté ma propre réponse.

• 28164 chiffres par Suboptimus Prime, basé sur l'algorithme de Qualtagh (C #)

Java - 3144 3322 6629 chiffres

6 0{3314} 8969999

6 0{6623} 49099

Cette solution est basée sur la réponse de FryAmTheEggman .

1. Le dernier chiffre est 1 ou 9.
2. Si le dernier chiffre est 1, le précédent est 0, 8 ou 9.
3. Si le dernier chiffre est 9, le précédent est 0, 4, 6 ou 9.
4. ...

Et si nous creusons plus profondément?

Cela devient une structure arborescente:

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

Appelons le nombre R composé droit si R et toutes ses terminaisons sont composites.

Nous allons itérer sur tous les bons nombres composites de la manière la plus large: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901, etc.

Les nombres commençant par zéro ne sont pas vérifiés pour la primauté mais sont nécessaires pour construire d'autres nombres.

Nous chercherons un nombre cible N sous la forme X00 ... 00R, où X est l'un des 4, 6, 8 ou 9 et R est le composite de droite. X ne peut pas être premier. X ne peut pas être 0. Et X ne peut pas être 1 car si R se termine par 1 ou 9 alors N contiendrait 11 ou 19.

Si XR contient des nombres premiers après l'opération de "suppression", alors XYR les contiendrait également pour tout Y. Nous ne devrions donc pas traverser les branches à partir de R.

Soit X une constante, disons 6.

Pseudocode:

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

Nous devons limiter la quantité de zéros car cela peut prendre trop de temps pour trouver un nombre premier sous la forme X + zéros + R (ou pour toujours si tous sont composites).

Le vrai code est assez verbeux et peut être trouvé ici .

Le test de primalité pour les nombres à longue distance int est effectué par une variante déterministe du test de Miller. Pour les nombres BigInteger, une division d'essai est effectuée en premier, puis le test BailliePSW. C'est probabiliste mais assez certain. Et c'est plus rapide que le test de Miller-Rabin (nous devrions faire de nombreuses itérations pour de si grands nombres dans Miller-Rabin pour gagner suffisamment de précision).

Edit: la première tentative était incorrecte. Nous devons également ignorer les branches commençant par R si X0 ... 0R est premier. Alors X0 ... 0YR ne serait pas un premier fragile. Une vérification supplémentaire a donc été ajoutée. Cette solution semble être correcte.

Edit 2: ajout d'une optimisation. Si (X + R) est divisible par 3, alors (X + zéros + R) est également divisible par 3. Donc (X + zéros + R) ne peut pas être premier dans ce cas et de tels R peuvent être ignorés.

Edit 3: il n'était pas nécessaire de sauter les premiers chiffres s'ils ne sont pas dans la dernière ou la première position. Les terminaisons comme 21 ou 51 sont donc correctes. Mais cela ne change pas grand-chose.

Conclusions:

1. Ma dernière réponse a été de vérifier sa fragilité pendant 100 minutes. La recherche de la réponse (vérification de toutes les variantes précédentes) a pris environ 15 minutes. Oui, cela n'a aucun sens de limiter le temps de recherche (nous pouvons commencer la recherche à partir du numéro cible, donc le temps serait nul). Mais il pourrait être utile de limiter le temps de vérification comme dans cette question .
2. La réponse 60 ... 049099 a le chiffre 4 au milieu. Si l'opération "supprimer" la touche, le nombre devient divisible par 3. Nous devons donc vérifier les opérations de suppression sur les côtés gauche et droit. Le côté droit est trop court. La longueur du côté gauche est presque n = longueur (N).
3. Les tests de primalité comme BPSW et Miller-Rabin utilisent une quantité constante d'exponentiations modulaires. Sa complexité est O (M (n) * n) selon cette page , où M (n) est la complexité de multiplication. Java utilise les algorithmes Toom-Cook et Karatsuba mais nous prendrons l'algorithme savant pour plus de simplicité. M (n) = n ² . La complexité du test de primalité est donc O (n ³ ).
4. Nous devons vérifier tous les nombres de longueur = 6 à 6629. Prenons min = 1 et max = n pour les points communs. Toute la complexité de la vérification est O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. La réponse d'Emil a les mêmes asymptotiques de vérification. Mais le facteur constant est plus faible. Le chiffre "7" se trouve au milieu du numéro. Le côté gauche et le côté droit peuvent être presque égaux. Il donne (n / 2) ⁴ * 2 = n ⁴ / 8. Accélération: 8X. Les nombres sous la forme 9 ... 9Y9 ... 9 peuvent être 1,7 fois plus longs que sous la forme X0 ... 0R ayant le même temps de vérification.

Python 2-126 1221 1337 1719 2268 chiffres

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Il y a environ len (n) ^ 2 nombres résultants de Remove (n, startIndex, count). J'ai essayé de minimiser ces chiffres. S'il y a beaucoup de chiffres côte à côte, beaucoup de ces nombres résultants peuvent être ignorés, car ils apparaissent plusieurs fois.

Je l'ai donc poussé à l'extrême, seulement 9s et un peu prime au milieu. J'ai également jeté un coup d'œil au premier fragile de moins d'un million et j'ai vu qu'il y avait un tel premier fragile. La recherche de nombres avec 2 9 à la fin fonctionne vraiment bien, je ne sais pas pourquoi. 1 nombre, 3 ou 4 9 à la fin entraîne des nombres premiers fragiles plus petits.

Il utilise le module pyprimes . Je ne sais pas si c'est bon. Il utilise le test miller_rabin, il est donc probabiliste.

Le programme trouve ce premier fragile à 126 chiffres en environ 1 minute, et pour le reste du temps, il cherche sans succès.

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

Éditer:

Je viens de voir que vous avez supprimé le délai. Je vais exécuter le programme pendant la nuit, peut-être que de très gros nombres premiers fragiles apparaissent.

modifier 2:

J'ai rendu mon programme original plus rapide, donc mais toujours pas de solution avec plus de 126 chiffres. J'ai donc sauté dans le train et recherché x 9s + 1 chiffre + y 9s. L'avantage est que vous devez vérifier la primauté des nombres O (n) si vous fixez y. Il trouve un 1221 assez rapidement.

modifier 3:

Pour le nombre de 2268 chiffres, j'utilise le même programme, divisé uniquement le travail sur plusieurs cœurs.

Python 2.7 - 429623069 99993799

Jusqu'à présent, aucune optimisation. Juste en utilisant quelques observations triviales sur les nombres premiers fragiles (grâce à Rainbolt dans le chat):

1. Les nombres premiers fragiles doivent se terminer par 1 ou 9 (les nombres premiers ne sont pas pairs et le dernier chiffre ne doit pas être premier)
2. Les nombres premiers fragiles se terminant par 1 doivent commencer par 8 ou 9 (le premier nombre ne peut pas être premier, et 11, 41 et 61 et sont tous des nombres premiers)
3. Les nombres premiers fragiles se terminant par 9 doivent commencer par 4,6 ou 9 (voir le raisonnement pour 1, mais seulement 89 est premier)

J'essaie juste de faire rouler la balle :)

Cela dure techniquement un peu plus de 15 minutes, mais il ne vérifie qu'un seul numéro dans le temps supplémentaire.

is_primeest tiré d' ici (isaacg l'a utilisé ici ) et est probabiliste.

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

Juste une note, quand je commence ça, n=429623069je me lève 482704669. Le chiffre supplémentaire semble vraiment tuer cette stratégie ...

Python 2, 828 chiffres 5048 chiffres

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

Comme l'a souligné @Jakube, le premier Prime que j'ai soumis n'était pas réellement fragile en raison d'un bogue dans mon code. La correction du bogue était facile mais cela a également rendu l'algorithme beaucoup plus lent.

Je me suis limité à un sous-ensemble facilement interrogeable des nombres premiers fragiles, à savoir ceux qui ne comprennent que le chiffre 9 et exactement un chiffre 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))

J'ai utilisé la même is_primefonction (d' ici ) que @FryAmTheEggman.

Éditer:

J'ai fait deux changements pour accélérer l'algorithme:

• J'essaie d'ignorer autant de vérifications de primalité que possible et de ne revenir en arrière que lorsqu'un premier potentiel fragile est trouvé pour m'assurer qu'il est vraiment fragile. Il y a un petit nombre de vérifications en double, donc j'ai mémorisé grossièrement la fonction de vérification principale.

• Pour les numéros du formulaire, b*'9' + '7' + c*'9'j'ai limité la taille de b. Plus la limite est basse, moins les nombres doivent être vérifiés, mais les chances augmentent de ne trouver aucun grand premier fragile. J'ai en quelque sorte choisi arbitrairement 222 comme limite.

À quelques milliers de chiffres, une seule vérification principale peut déjà prendre quelques secondes mon programme. Donc, je ne peux probablement pas faire beaucoup mieux avec cette approche.

N'hésitez pas à vérifier l'exactitude de ma soumission. En raison du contrôle de primalité probabiliste, mon nombre ne pourrait théoriquement pas être premier, mais s'il l'est, il devrait être fragile. Ou j'ai fait quelque chose de mal. :-)

C #, 10039 28164 chiffres

6 0{28157} 169669

Edit: J'ai fait un autre programme basé sur l'algorithme de Qualtagh avec quelques modifications mineures:

• Je cherche les nombres de la forme L000 ... 000R, où L est composite gauche, R est composite droit. J'ai autorisé le nombre composite gauche L à avoir plusieurs chiffres, bien que ce soit principalement un changement de style, et cela n'affecte probablement pas l'efficacité de l'algorithme.
• J'ai ajouté le multithreading pour accélérer la recherche.

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

Ancienne réponse:

8 0{5436} 4 0{4600} 1

Voici quelques schémas notables pour les nombres premiers fragiles:

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

où X peut être 1, 2, 4, 5, 7 ou 8.

Pour de tels nombres, nous n'avons qu'à considérer (longueur - 1) les Removeopérations possibles . L'autreRemove opérations produisent soit des doublons, soit des nombres évidemment composites. J'ai essayé de rechercher tous ces numéros avec jusqu'à 800 chiffres et j'ai remarqué que 4 modèles apparaissent plus fréquemment que les autres: 8007001, 8004001, 9997999 et 6004009. Puisque Emil et Jakube utilisent le modèle 999X999, j'ai décidé d'utiliser 8004001 juste pour ajouter de la variété.

J'ai ajouté les optimisations suivantes à l'algorithme:

• Je commence la recherche à partir de nombres à 7 000 chiffres, puis j'augmente la longueur de 1 500 chaque fois qu'un nombre premier fragile est trouvé. S'il n'y a pas de nombre premier fragile avec une longueur donnée, je l'incrémente de 1. 7000 et 1500 ne sont que des nombres arbitraires qui semblaient appropriés.
• J'utilise le multithreading pour rechercher les numéros de longueur différente en même temps.
• Le résultat de chaque vérification principale est stocké dans une table de hachage pour éviter les vérifications en double.
• J'utilise l'implémentation Miller-Rabin de Mpir.NET , qui est très rapide (MPIR est un fork 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 chiffres fixes pour vraiment réels

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

Mieux - 1277 chiffres

9{871} 8 9{405}

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