Рассмотрим функцию, Remove(n, startIndex, count)которая удаляет countцифры из числа, nначиная с цифры в позиции startIndex. Примеры:

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

Мы назовем простое число X хрупким, если каждая возможная Removeоперация делает его непростым. Например, 80651 - хрупкое простое число, потому что все следующие числа не просты:

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

Цель

Напишите программу, которая находит наибольшее хрупкое простое число. Изменить: убрал ограничение по времени, потому что был относительно справедливый способ обойти его.

Счет - это хрупкое простое число, найденное вашей программой. В случае ничьей побеждает более ранняя подача.

правила

• Вы можете использовать любой язык и любые сторонние библиотеки.
• Вы запускаете программу на собственном оборудовании.
• Вы можете использовать вероятностные тесты простоты.
• Все в базе 10.

Ведущие записи

• 6629 цифр по Qualtagh (Java)
• Эмиль, 5048 цифр (Python 2)
• 2268 цифр Якуба (Python 2)

Изменить: я добавил свой собственный ответ.

• 28164 цифр по Suboptimus Prime, основанный на алгоритме Qualtagh (C #)

Джава - 3144 3322 6629 цифр

6 0{3314} 8969999

6 0{6623} 49099

Это решение основано на ответе FryAmTheEggman .

1. Последняя цифра - 1 или 9.
2. Если последняя цифра равна 1, то предыдущая цифра - 0, 8 или 9.
3. Если последняя цифра 9, то предыдущая цифра 0, 4, 6 или 9.
4. ...

Что если мы будем копать глубже?

Это становится древовидной структурой:

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

Назовем номер R правым составным, если R и все его окончания составные.

Мы будем перебирать все правильные составные числа в ширину: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901 и т. Д.

Числа, начинающиеся с нуля, не проверяются на простоту, но необходимы для построения дальнейших чисел.

Мы будем искать целевое число N в форме X00 ... 00R, где X является одним из 4, 6, 8 или 9, а R является правым составным. Х не может быть простым. X не может быть 0. И X не может быть 1, потому что, если R заканчивается 1 или 9, тогда N будет содержать 11 или 19.

Если XR содержит простые числа после операции «удалить», то XYR будет содержать их также для любого Y. Поэтому мы не должны проходить ветви, начиная с R.

Пусть X - константа, скажем, 6.

псевдокод:

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

Мы должны ограничить количество нулей, потому что это может занять слишком много времени, чтобы найти простое число в форме X + нули + R (или навсегда, если все они составные).

Настоящий код довольно многословен и его можно найти здесь .

Проверка первичности чисел в длинном диапазоне int выполняется детерминистическим вариантом теста Миллера. Для номеров BigInteger сначала выполняется пробное деление, а затем тест BailliePSW. Это вероятностно, но вполне определенно. И это быстрее, чем тест Миллера-Рабина (мы должны сделать много итераций для таких больших чисел в Миллере-Рабине, чтобы получить достаточную точность).

Изменить: первая попытка была неверной. Мы также должны игнорировать ветви, начинающиеся с R, если X0 ... 0R простое. Тогда X0 ... 0YR не будет хрупким простым. Поэтому была добавлена ​​дополнительная проверка. Это решение кажется правильным.

Редактировать 2: добавлена ​​оптимизация. Если (X + R) делится на 3, то (X + нули + R) также делится на 3. Так что (X + нули + R) не могут быть простыми в этом случае, и такие R могут быть пропущены.

Редактировать 3: не было необходимости пропускать простые цифры, если они не находятся в последней или первой позиции. Так что концовки вроде 21 или 51 в порядке. Но это ничего не меняет.

Выводы:

1. Моим последним ответом была проверка на хрупкость в течение 100 минут. Поиск ответа (проверка всех предыдущих вариантов) занял около 15 минут. Да, нет смысла ограничивать время поиска (мы можем начать поиск с номера цели, поэтому время будет равно нулю). Но было бы целесообразно ограничить время проверки, как в этом вопросе .
2. Ответ 60 ... 049099 имеет цифру 4 в середине. Если операция «удалить» касается этого, число становится делимым на 3. Поэтому мы должны проверить операции удаления в левой и правой частях. Правая сторона слишком короткая. Длина левой стороны почти n = длина (N).
3. Тесты на первичность, такие как BPSW и Miller-Rabin, используют постоянное количество модульных возведений в степень. Согласно этой странице его сложность составляет O (M (n) * n) , где M (n) - сложность умножения. Java использует алгоритмы Toom-Cook и Karatsuba, но для простоты мы возьмем научный алгоритм. M (n) = n ² . Таким образом, сложность тестирования простоты равна O (n ³ ).
4. Мы должны проверить все числа от длины = 6 до 6629. Давайте возьмем min = 1 и max = n для общности. Вся сложность проверки составляет O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. Ответ Эмиля имеет такую ​​же проверочную асимптотику. Но постоянный фактор ниже. Цифра "7" стоит в середине номера. Левая сторона и правая сторона могут быть почти равны. Это дает (n / 2) ⁴ * 2 = n ⁴ / 8. Ускорение: 8X. Числа в форме 9 ... 9Y9 ... 9 могут быть в 1,7 раза длиннее, чем в форме X0 ... 0R с одинаковым временем проверки.

Python 2 - 126 1221 1337 1719 2268 цифр

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Приблизительно len (n) ^ 2 результирующих числа Remove (n, startIndex, count). Я пытался минимизировать эти цифры. Если много цифр рядом друг с другом, то многие из этих результирующих чисел могут быть проигнорированы, потому что они появляются несколько раз.

Таким образом, я взял это до крайности, только 9 и немного премьер в середине. Я также взглянул на хрупкое простое число до 1 миллиона и увидел, что существуют такие хрупкие простое число. Поиск чисел с 2 9 в конце работает действительно хорошо, не знаю почему. 1 число, 3 или 4 9 в конце приводит к меньшим хрупким простым числам.

Он использует модуль pyprimes . Я не уверен, если это хорошо. Он использует тест miller_rabin, поэтому он вероятностный.

Программа находит это 126-значное хрупкое простое число примерно за 1 минуту, а в остальное время ищет безуспешно.

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

редактировать:

Только что увидел, что вы сняли ограничение по времени. Я буду запускать программу в течение ночи, возможно, появятся действительно большие хрупкие простые числа.

редактировать 2:

Сделал мою оригинальную программу быстрее, но до сих пор нет решения с более чем 126 цифрами. Поэтому я вскочил на поезд и искал x 9s + 1 цифра + y 9s. Преимущество состоит в том, что вы должны проверить O (n) чисел на простоту, если вы исправите y. Он находит 1221 довольно быстро.

редактировать 3:

Для 2268-значного числа я использую ту же программу, только поделил работу на несколько ядер.

Python 2.7 - 429623069 99993799

Пока никаких оптимизаций. Просто используя некоторые тривиальные наблюдения о хрупких простых числах (спасибо Rainbolt в чате):

1. Хрупкие простые числа должны заканчиваться 1 или 9 (простые числа не являются четными, и последняя цифра не должна быть простой)
2. Хрупкие простые числа, оканчивающиеся на 1, должны начинаться с 8 или 9 (первое число не может быть простым, а 11, 41 и 61 - все простые)
3. Хрупкие простые числа, оканчивающиеся на 9, должны начинаться с 4,6 или 9 (см. Обоснование 1, но только 89 является простым)

Просто пытаюсь заставить мяч катиться :)

Технически это выполняется чуть более 15 минут, но в дополнительное время проверяется только один номер.

is_primeвзято отсюда (isaacg использовал его здесь ) и является вероятностным.

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

Просто примечание, когда я начинаю это с, n=429623069я встаю 482704669. Кажется, лишняя цифра убивает эту стратегию ...

Python 2, 828 цифр, 5048 цифр

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

Как указал @Jakube, первое простое число, которое я отправил, на самом деле не было хрупким из-за ошибки в моем коде. Исправить ошибку было легко, но это также сделало алгоритм значительно медленнее.

Я ограничил себя легко доступным для поиска подмножеством хрупких простых чисел, а именно теми, которые состоят только из цифры 9 и ровно одной цифры 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))

Я использовал ту же is_primeфункцию ( отсюда ), что и @FryAmTheEggman.

Редактировать:

Я сделал два изменения, чтобы сделать алгоритм быстрее:

• Я стараюсь пропустить как можно больше проверок простоты и возвращаюсь назад, только когда обнаружен потенциальный хрупкий простой код, чтобы убедиться, что он действительно хрупкий. Существует небольшое количество повторных проверок, поэтому я грубо запомнил функцию первичной проверки.

• Для чисел формы b*'9' + '7' + c*'9'я ограничил размер b. Чем ниже предел, тем меньше чисел нужно проверять, но шансы увеличиваться, чтобы вообще не найти большого хрупкого простого числа. Я как бы произвольно выбрал 222 в качестве предела.

При нескольких тысячах разовых простых проверок моя программа может занять несколько секунд. Таким образом, я, вероятно, не могу сделать намного лучше с этим подходом.

Пожалуйста, не стесняйтесь проверить правильность моего представления. Из-за вероятностной проверки простоты мое число теоретически не может быть простым, но если оно есть, оно должно быть хрупким. Или я сделал что-то не так. :-)

C #, 10039, 28164 цифры

6 0{28157} 169669

Редактировать: я сделал другую программу, основанную на алгоритме Qualtagh с некоторыми незначительными изменениями:

• Я ищу числа в форме L000 ... 000R, где L является составным слева, R является составным справа. Я позволил левому составному номеру L иметь несколько цифр, хотя это в основном стилистическое изменение, и оно, вероятно, не влияет на эффективность алгоритма.
• Я добавил многопоточность, чтобы ускорить поиск.

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

Старый ответ:

8 0{5436} 4 0{4600} 1

Вот несколько примечательных шаблонов для хрупких простых чисел:

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

где Х может быть 1, 2, 4, 5, 7 или 8.

Для таких чисел нам нужно только рассмотреть (длина - 1) возможные Removeоперации. ДругойRemove операции производят либо дубликаты, либо явно составные числа. Я попытался найти все такие числа с длиной до 800 цифр и заметил, что 4 шаблона появляются чаще, чем остальные: 8007001, 8004001, 9997999 и 6004009. Поскольку Эмиль и Якуб используют шаблон 999X999, я решил использовать 8004001 просто добавить немного разнообразия.

Я добавил следующие оптимизации в алгоритм:

• Я начинаю поиск с чисел с 7000 цифрами, а затем увеличиваю длину на 1500 каждый раз, когда обнаруживается хрупкое простое число. Если нет хрупкого простого числа с данной длиной, то я увеличиваю его на 1. 7000 и 1500 - просто произвольные числа, которые кажутся подходящими.
• Я использую многопоточность для одновременного поиска чисел разной длины.
• Результат каждой первичной проверки сохраняется в хеш-таблице, чтобы предотвратить повторные проверки.
• Я использую реализацию Миллера-Рабина из Mpir.NET , которая очень быстра (MPIR - это форк 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 цифр исправлено для настоящих реалов

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

Лучше один - 1277 цифр

9{871} 8 9{405}

Код 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)