Pertimbangkan fungsi Remove(n, startIndex, count)yang menghilangkan countangka dari angka nmulai dari angka di posisi startIndex. Contoh:

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

Kami akan menyebut bilangan prima X rapuh jika setiap Removeoperasi yang memungkinkan membuatnya non-prima. Misalnya, 80651 adalah prime rapuh karena semua angka berikut ini tidak prima:

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

Tujuan

Tulis program yang menemukan prime rapuh terbesar. Sunting: menghapus batas waktu karena ada cara yang relatif adil untuk menghindarinya.

Skornya adalah bilangan prima rapuh yang ditemukan oleh program Anda. Dalam hal seri, pengajuan sebelumnya menang.

Aturan

• Anda dapat menggunakan bahasa apa pun dan perpustakaan pihak ketiga mana pun.
• Anda menjalankan program di perangkat keras Anda sendiri.
• Anda dapat menggunakan tes primality probabilistik.
• Semuanya ada di base 10.

Entri terkemuka

• 6629 digit oleh Qualtagh (Jawa)
• 5048 digit oleh Emil (Python 2)
• 2268 digit oleh Jakube (Python 2)

Sunting: Saya telah menambahkan jawaban saya sendiri.

• 28164 digit oleh Suboptimus Prime, berdasarkan algoritma Qualtagh (C #)

Jawa - 3144 3322 6629 digit

6 0{3314} 8969999

6 0{6623} 49099

Solusi ini didasarkan pada jawaban FryAmTheEggman .

1. Digit terakhir adalah 1 atau 9.
2. Jika digit terakhir adalah 1 maka angka sebelumnya adalah 0, 8 atau 9.
3. Jika angka terakhir adalah 9 maka angka sebelumnya adalah 0, 4, 6 atau 9.
4. ...

Bagaimana jika kita menggali lebih dalam?

Itu menjadi struktur pohon:

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

Mari kita panggil angka R komposit kanan jika R dan semua ujungnya komposit.

Kita akan mengulangi semua angka komposit yang benar dengan cara pertama: 1, 9, 01, 81, 91, 09, 49, 69, 99, 001, 801, 901 dll.

Angka-angka yang dimulai dengan nol tidak diperiksa untuk primality tetapi diperlukan untuk membangun angka lebih lanjut.

Kami akan mencari nomor target N dalam bentuk X00 ... 00R, di mana X adalah salah satu dari 4, 6, 8 atau 9 dan R adalah komposit yang benar. X tidak bisa menjadi prima. X tidak boleh 0. Dan X tidak bisa 1 karena jika R berakhir dengan 1 atau 9 maka N akan berisi 11 atau 19.

Jika XR berisi bilangan prima setelah operasi "hapus" maka XYR akan memuatnya juga untuk Y. Jadi, kita tidak boleh melintasi cabang mulai dari R.

Biarkan X menjadi konstanta, katakan 6.

Kodesemu:

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

Kita harus membatasi jumlah nol karena mungkin butuh waktu terlalu lama untuk menemukan bilangan prima dalam bentuk X + nol + R (atau selamanya jika semuanya adalah komposit).

Kode sebenarnya sangat bertele-tele dan dapat ditemukan di sini .

Pengujian primality untuk angka dalam rentang int panjang dilakukan oleh varian deterministik dari uji Miller. Untuk nomor BigInteger, divisi uji coba dilakukan terlebih dahulu dan kemudian uji BailliePSW. Ini probabilistik tetapi cukup pasti. Dan ini lebih cepat daripada tes Miller-Rabin (kita harus melakukan banyak iterasi untuk sejumlah besar di Miller-Rabin untuk mendapatkan akurasi yang cukup).

Sunting: upaya pertama tidak benar. Kita juga harus mengabaikan cabang yang dimulai dengan R jika X0 ... 0R adalah yang utama. Maka X0 ... 0YR tidak akan menjadi prime rapuh. Jadi cek tambahan ditambahkan. Solusi ini tampaknya benar.

Sunting 2: menambahkan pengoptimalan. Jika (X + R) dapat dibagi dengan 3 maka (X + nol + R) juga dapat dibagi dengan 3. Jadi (X + nol + R) tidak dapat menjadi prima dalam kasus ini dan R seperti itu dapat dilewati.

Sunting 3: tidak perlu melewati digit utama jika mereka tidak berada di posisi terakhir atau pertama. Jadi akhiran seperti 21 atau 51 ok. Tapi itu tidak banyak berubah.

Kesimpulan:

1. Jawaban terakhir saya adalah memeriksa rapuh selama 100 menit. Pencarian jawaban (memeriksa semua varian sebelumnya) membutuhkan waktu sekitar 15 menit. Ya, tidak masuk akal untuk membatasi waktu pencarian (kita dapat mulai mencari dari nomor target, jadi waktu akan menjadi nol). Tetapi bisa berarti membatasi waktu pemeriksaan seperti dalam pertanyaan ini .
2. Jawaban 60 ... 049099 memiliki angka 4 di tengah. Jika operasi "hapus" menyentuhnya, jumlahnya menjadi habis dibagi 3. Jadi kita harus memeriksa operasi hapus di sisi kiri dan kanan. Sisi kanan terlalu pendek. Panjang sisi kiri hampir n = panjang (N).
3. Tes primality seperti BPSW dan Miller-Rabin menggunakan jumlah konstan eksponensial modular. Kompleksitasnya adalah O (M (n) * n) menurut halaman ini , di mana M (n) adalah kompleksitas multiplikasi. Java menggunakan algoritma Toom-Cook dan Karatsuba tetapi kami akan menggunakan algoritma cendekia untuk kesederhanaan. M (n) = n ² . Jadi kompleksitas pengujian primality adalah O (n ³ ).
4. Kita harus memeriksa semua angka dari panjang = 6 hingga 6629. Mari ambil min = 1 dan maks = n untuk persamaan. Keseluruhan kompleksitas pemeriksaan adalah O (1 ³ + 2 ³ + ... + n ³ ) = O ((n * (n + 1) / 2) ² ) = O (n ⁴ ).
5. Jawaban Emil memiliki asimtotik pengecekan yang sama. Tetapi faktor konstan lebih rendah. Digit "7" berdiri di tengah-tengah angka. Sisi kiri dan kanan bisa hampir sama. Ini memberi (n / 2) ⁴ * 2 = n ⁴ / 8. Speedup: 8X. Angka dalam formulir 9 ... 9Y9 ... 9 dapat 1,7 kali lebih lama daripada dalam formulir X0 ... 0R memiliki waktu pemeriksaan yang sama.

Python 2 - 126 1221 1337 1719 2268 digit

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Ada sekitar len (n) ^ 2 angka yang dihasilkan dari Remove (n, startIndex, count). Saya mencoba meminimalkan angka-angka itu. Jika ada banyak digit di sebelah satu sama lain adalah sama, banyak dari angka yang dihasilkan ini dapat diabaikan, karena mereka muncul beberapa kali.

Jadi saya membawanya ke ekstrim, hanya 9 dan sedikit prima di tengah. Saya juga melihat prime rapuh di bawah 1 juta, dan melihat, bahwa ada prime rapuh. Mencari angka dengan angka 9 pada akhirnya bekerja dengan sangat baik, tidak yakin mengapa. 1 angka, 3, atau 4 9s pada akhirnya menghasilkan bilangan prima rapuh yang lebih kecil.

Ini menggunakan modul pyprimes . Saya tidak yakin, apakah itu bagus. Ini menggunakan tes miller_rabin, jadi itu probabilistik.

Program ini menemukan prime rapuh 126 digit ini dalam waktu sekitar 1 menit, dan selama sisa waktu pencarian itu tidak berhasil.

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

edit:

Baru saja melihat, bahwa Anda menghapus batas waktu. Saya akan menjalankan program ini pada malam hari, mungkin beberapa bilangan prima rapuh besar muncul.

edit 2:

Membuat program asli saya lebih cepat, jadi tetapi masih tidak ada solusi dengan lebih dari 126 digit. Jadi saya melompat di kereta dan mencari x 9s + 1 digit + y 9s. Keuntungannya, Anda harus memeriksa nomor O (n) untuk primality, jika Anda memperbaikinya y. Ia menemukan 1221 agak cepat.

edit 3:

Untuk angka 2268 angka saya menggunakan program yang sama, hanya membagi pekerjaan pada beberapa core.

Python 2.7 - 429623069 99993799

Tidak ada optimasi apa pun, sejauh ini. Hanya menggunakan beberapa pengamatan sepele tentang bilangan prima rapuh (terima kasih kepada Rainbolt dalam obrolan):

1. Bilangan prima rapuh harus diakhiri dengan 1 atau 9 (Bilangan prima tidak genap, dan angka akhir tidak boleh prima)
2. Bilangan prima rapuh yang diakhiri dengan 1 harus dimulai dengan 8 atau 9 (angka pertama tidak boleh prima, dan 11, 41 dan 61 dan semuanya bilangan prima)
3. Primer rapuh yang diakhiri dengan 9 harus dimulai dengan 4,6 atau 9 (lihat alasan untuk 1, tetapi hanya 89 yang utama)

Hanya berusaha membuat bola bergulir :)

Secara teknis ini berjalan sedikit lebih dari 15 menit, tetapi hanya memeriksa satu nomor dalam waktu tambahan.

is_primediambil dari sini (isaacg menggunakannya di sini ) dan probabilistik.

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

Hanya sebuah catatan, ketika saya memulai ini dengan n=429623069saya bangun 482704669. Digit tambahan tampaknya benar-benar mematikan strategi ini ...

Python 2, 828 digit 5048 digit

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

Seperti @Jakube tunjukkan, perdana pertama yang saya kirimkan sebenarnya tidak rapuh karena bug dalam kode saya. Memperbaiki bug itu mudah tetapi itu juga membuat algoritma lebih lambat secara signifikan.

Saya membatasi diri pada subset yang mudah dicari dari bilangan prima yang rapuh, yaitu yang hanya terdiri dari angka 9 dan tepat satu digit 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))

Saya menggunakan is_primefungsi yang sama (dari sini ) sebagai @FryAmTheEggman.

Edit:

Saya membuat dua perubahan untuk membuat algoritme lebih cepat:

• Saya mencoba untuk melewatkan sebanyak mungkin pemeriksaan primality dan hanya kembali ketika prime prime yang rapuh ditemukan untuk memastikan itu benar-benar rapuh. Ada sejumlah kecil duplikat cek, jadi saya dengan kasar memoise fungsi pemeriksaan utama.

• Untuk jumlah formulir b*'9' + '7' + c*'9'saya membatasi ukuran b. Semakin rendah batas, semakin sedikit angka yang harus diperiksa, tetapi peluang meningkat untuk tidak menemukan prime rapuh besar sama sekali. Saya agak suka memilih 222 sebagai batas.

Dengan beberapa ribu digit, cek perdana tunggal sudah dapat mengambil program saya beberapa detik. Jadi, saya mungkin tidak bisa melakukan yang lebih baik dengan pendekatan ini.

Silakan periksa kebenaran kiriman saya. Karena primality probabilistic memeriksa nomor saya secara teoritis tidak bisa menjadi prima, tetapi jika ya, itu harus rapuh. Atau saya telah melakukan sesuatu yang salah. :-)

C #, 10039 28164 digit

6 0{28157} 169669

Sunting: Saya membuat program lain berdasarkan algoritma Qualtagh dengan beberapa modifikasi kecil:

• Saya mencari angka dari bentuk L000 ... 000R, di mana L adalah komposit kiri, R adalah komposit kanan. Saya membiarkan angka komposit L kiri memiliki beberapa digit, meskipun ini sebagian besar merupakan perubahan gaya, dan mungkin tidak mempengaruhi efisiensi algoritma.
• Saya telah menambahkan multithreading untuk mempercepat pencarian.

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

Jawaban lama:

8 0{5436} 4 0{4600} 1

Berikut adalah beberapa pola penting untuk bilangan prima rapuh:

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

di mana X bisa 1, 2, 4, 5, 7 atau 8.

Untuk angka seperti itu kita hanya perlu mempertimbangkan (panjang - 1) mungkin Remove operasi yang . RemoveOperasi lain menghasilkan duplikat atau angka gabungan. Saya mencoba mencari semua angka dengan 800 digit dan memperhatikan bahwa 4 pola muncul lebih sering daripada yang lain: 8007001, 8004001, 9997999, dan 6004009. Karena Emil dan Jakube menggunakan pola 999X999, saya memutuskan untuk menggunakan 8004001 saja. untuk menambah variasi.

Saya telah menambahkan optimasi berikut ke algoritme:

• Saya mulai mencari dari angka dengan 7000 digit dan kemudian menambah panjang 1500 setiap kali prime rapuh ditemukan. Jika tidak ada prime rapuh dengan panjang yang diberikan maka saya menambahnya dengan 1. 7000 dan 1500 hanya angka acak yang sepertinya cocok.
• Saya menggunakan multithreading untuk mencari angka dengan panjang berbeda pada waktu yang bersamaan.
• Hasil dari setiap pemeriksaan utama disimpan dalam tabel hash untuk mencegah pemeriksaan duplikat.
• Saya menggunakan implementasi Miller-Rabin dari Mpir.NET , yang sangat cepat (MPIR adalah fork dari 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 digit ditetapkan untuk benar-benar nyata

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997999999999999999999999999999999999999999999999999999999999999999999999

9{1150} 7 9{69}

Lebih baik - 1277 digit

9{871} 8 9{405}

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