Temukan prime craftiest

9

Intro

Pertimbangkan proses mengambil bilangan bulat positif n di beberapa basis b dan mengganti setiap digit dengan perwakilannya di dasar digit di sebelah kanan.

  • Jika digit di sebelah kanan adalah 0, gunakan basis b .
  • Jika digit di sebelah kanan adalah 1, gunakan unary dengan 0 sebagai tanda penghitungan.
  • Jika tidak ada digit di sebelah kanan (yaitu Anda berada di tempat yang), lilitkan ke digit yang paling signifikan.

Sebagai contoh, mari n = 160 dan b = 10. Menjalankan prosesnya terlihat seperti ini:

The first digit is 1, the digit to the right is 6, 1 in base 6 is 1.
The next digit is 6, the digit to the right is 0, 0 is not a base so use b, 6 in base b is 6.
The last digit is 0, the digit to the right (looping around) is 1, 0 in base 1 is the empty string (but that's ok).

Concatenating '1', '6', and '' together gives 16, which is read in the original base b = 10.

Prosedur yang persis sama tetapi bergerak ke kiri dan bukan ke kanan juga dapat dilakukan:

The first digit is 1, the digit to the left (looping around) is 0, 0 is not a base so use b, 1 in base b is 1.
The next digit is 6, the digit to the left is 1, 6 in base 1 is 000000.
The last digit is 0, the digit to the left is 6, 0 in base 6 is 0.

Concatenating '1', '000000', and '0' together gives 10000000, which is read in the original base b = 10.

Dengan demikian, kami telah membuat dua angka yang terkait dengan 160 (untuk b = 10): 16 dan 10.000000.

Kami akan mendefinisikan n sebagai angka yang licik jika membagi secara merata setidaknya satu dari dua angka yang dihasilkan dalam proses ini menjadi 2 atau lebih bagian

Dalam contoh n adalah licik karena 160 membagi 10.000.000 persis 62500 kali.

203 BUKAN licik karena angka yang dihasilkan adalah 2011 dan 203 itu sendiri, yang 203 tidak bisa masuk secara merata menjadi 2 atau lebih kali.

Tantangan

(Untuk sisa masalah, kami hanya akan mempertimbangkan b = 10.)

Tantangannya adalah untuk menulis sebuah program yang menemukan angka licik tertinggi yang juga prima.

7 prima licik pertama (dan semua yang saya temukan sejauh ini) adalah:

2
5
3449
6287
7589
9397
93557 <-- highest so far (I've searched to 100,000,000+)

Saya tidak yakin secara resmi apakah lebih ada, tetapi saya berharap mereka ada. Jika Anda dapat membuktikan bahwa ada (atau tidak) yang banyak, saya akan memberi Anda +200 rep bounty.

Pemenangnya adalah orang yang dapat memberikan prime licik tertinggi, asalkan jelas bahwa mereka telah aktif dalam pencarian dan tidak sengaja mengambil kemuliaan dari orang lain.

Aturan

  • Anda dapat menggunakan alat temuan utama apa pun yang Anda inginkan.
  • Anda dapat menggunakan penguji utama probabilistik.
  • Anda dapat menggunakan kembali kode orang lain dengan atribusi . Ini adalah upaya bersama. Taktik kejam tidak akan ditoleransi.
  • Program Anda harus secara aktif mencari yang utama. Anda dapat memulai pencarian di prime licik yang paling dikenal.
  • Program Anda harus dapat menghitung semua prima licik yang dikenal dalam waktu 4 jam dari Amazon EC2 t2.medium instance (baik empat sekaligus atau satu selama empat jam atau sesuatu di antaranya). Saya sebenarnya tidak akan mengujinya pada Anda dan Anda tentu tidak perlu. Ini hanya tolok ukur.

Berikut ini adalah kode Python 3 yang saya gunakan untuk membuat tabel di atas: (berjalan dalam satu atau dua detik)

import pyprimes

def toBase(base, digit):
    a = [
            ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
            ['', '0', '00', '000', '0000', '00000', '000000', '0000000', '00000000', '000000000' ],
            ['0', '1', '10', '11', '100', '101', '110', '111', '1000', '1001'],
            ['0', '1', '2', '10', '11', '12', '20', '21', '22', '100'],
            ['0', '1', '2', '3', '10', '11', '12', '13', '20', '21'],
            ['0', '1', '2', '3', '4', '10', '11', '12', '13', '14'],
            ['0', '1', '2', '3', '4', '5', '10', '11', '12', '13'],
            ['0', '1', '2', '3', '4', '5', '6', '10', '11', '12'],
            ['0', '1', '2', '3', '4', '5', '6', '7', '10', '11'],
            ['0', '1', '2', '3', '4', '5', '6', '7', '8', '10']
        ]
    return a[base][digit]

def getCrafty(start=1, stop=100000):
    for p in pyprimes.primes_above(start):
        s = str(p)
        left = right = ''
        for i in range(len(s)):
            digit = int(s[i])
            left += toBase(int(s[i - 1]), digit)
            right += toBase(int(s[0 if i + 1 == len(s) else i + 1]), digit)
        left = int(left)
        right = int(right)
        if (left % p == 0 and left // p >= 2) or (right % p == 0 and right // p >= 2):
            print(p, left, right)
        if p >= stop:
            break
    print('DONE')

getCrafty()
code-challenge primes Hobi Calvin
sumber
Saya pikir bahwa membuat 0 di setiap basis x menjadi string kosong akan lebih matematis. Juga, saya yakin akan lebih mudah untuk membuktikan atau menyangkal versi ini
bangga haskeller

Jawaban:

7

Mathematica, temukan 93.557 dalam 0,3 detik (tidak ada bilangan prima lebih lanjut di bawah 2 * 10 10 )

Ini hanya pencarian lengkap yang naif melalui semua bilangan prima. Untuk mulai dengan itu memeriksa sekitar 1.000.000 bilangan prima setiap 55 detik (yang pasti akan semakin lambat karena bilangan prima menjadi lebih besar).

Saya menggunakan banyak fungsi pembantu:

lookup = {
  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
  {{}, 0, {0, 0}, {0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, 
   {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}},
  {0, 1, {1, 0}, {1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}, {1, 0, 0, 0}, 
   {1, 0, 0, 1}},
  {0, 1, 2, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}, {1, 0, 0}},
  {0, 1, 2, 3, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {2, 0}, {2, 1}},
  {0, 1, 2, 3, 4, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}},
  {0, 1, 2, 3, 4, 5, {1, 0}, {1, 1}, {1, 2}, {1, 3}},
  {0, 1, 2, 3, 4, 5, 6, {1, 0}, {1, 1}, {1, 2}},
  {0, 1, 2, 3, 4, 5, 6, 7, {1, 0}, {1, 1}},
  {0, 1, 2, 3, 4, 5, 6, 7, 8, {1, 0}}
};
convertBase[d_, b_] := lookup[[b + 1, d + 1]];
related[n_] := (
   d = IntegerDigits[n];
   {FromDigits[Flatten[convertBase @@@ Transpose[{d, RotateRight@d}]]],
    FromDigits[Flatten[convertBase @@@ Transpose[{d, RotateLeft@d}]]]}
);
crafty[n_] := (
   {ql, qr} = related[n]/n;
   IntegerQ[ql] && ql > 1 || IntegerQ[qr] && qr > 1
);

Dan kemudian loop ini melakukan pencarian yang sebenarnya:

p = 2;
start = TimeUsed[];
i = 1;
While[True,
 If[crafty[p], Print@{"CRAFTY PRIME:", p, TimeUsed[] - start}];
 p = NextPrime@p;
 If[Mod[++i, 1000000] == 0, 
  Print[{"Last prime checked:", p, TimeUsed[] - start}]
 ]
]

Saya akan terus memperbarui posting, jika saya menemukan bilangan prima atau dapat memikirkan optimisasi.

Saat ini memeriksa semua bilangan prima hingga 100.000.000 dalam waktu sekitar 5,5 menit.

Sunting: Saya memutuskan untuk mengikuti contoh OP dan beralih ke tabel pencarian untuk konversi basis. Itu memberi sekitar 30% percepatan.

Angka licik secara umum

Saya menghentikan pencarian saya untuk bilangan prima licik sekarang, karena saya perlu beberapa hari hanya untuk mengejar ketinggalan dari mana jawaban Perl sudah didapat. Sebaliknya, saya mulai mencari semua angka licik. Mungkin distribusi mereka membantu menemukan bukti bahwa jumlah prima licik adalah terbatas atau tidak terbatas.

Saya mendefinisikan angka licik kanan yang membagi angka terkait yang diperoleh dengan menafsirkan angka di sebelah kanan sebagai basis baru, dan angka licik kiri sesuai. Mungkin akan membantu untuk mengatasi ini secara individual sebagai bukti.

Berikut adalah semua angka licik kiri hingga 2.210.000.000:

{2, 5, 16, 28, 68, 160, 222, 280, 555, 680, 777, 1600, 2605, 2800, 
 6800, 7589, 7689, 9397, 9777, 16000, 16064, 16122, 22222, 24682, 
 26050, 28000, 55555, 68000, 75890, 76890, 93557, 160000, 160640, 
 161220, 247522, 254408, 260500, 280000, 680000, 758900, 768900, 
 949395, 1600000, 1606400, 1612200, 2222222, 2544080, 2605000, 
 2709661, 2710271, 2717529, 2800000, 3517736, 5555555, 6800000, 
 7589000, 7689000, 9754696, 11350875, 16000000, 16064000, 16122000,
 25440800, 26050000, 27175290, 28000000, 28028028, 35177360, 52623721, 
 68000000, 68654516, 75890000, 76890000, 113508750, 129129129, 160000000,
 160640000, 161220000, 222222222, 254408000, 260500000, 271752900,
 275836752, 280000000, 280280280, 333018547, 351773600, 370938016, 
 555555555, 680000000, 758900000, 768900000, 777777777, 877827179, 
 1135087500, 1291291290, 1600000000, 1606400000, 1612200000, 1944919449}

Dan di sini ada semua angka licik di kisaran itu:

{2, 5, 16, 28, 68, 125, 128, 175, 222, 284, 555, 777, 1575, 1625, 
 1875, 3449, 5217, 6287, 9375, 14625, 16736, 19968, 22222, 52990, 
 53145, 55555, 58750, 93750, 127625, 152628, 293750, 529900, 587500, 
 593750, 683860, 937500, 1034375, 1340625, 1488736, 2158750, 2222222, 
 2863740, 2937500, 5299000, 5555555, 5875000, 5937500, 6838600, 
 7577355, 9375000, 12071125, 19325648, 21587500, 28637400, 29375000, 
 29811250, 42107160, 44888540, 52990000, 58750000, 59375000, 68386000, 
 71461386, 74709375, 75773550, 93750000, 100540625, 116382104,
 164371875, 197313776, 207144127, 215875000, 222222222, 226071269,
 227896480, 274106547, 284284284, 286374000, 287222080, 293750000, 
 298112500, 421071600, 448885400, 529900000, 555555555, 587500000, 
 593750000, 600481125, 683860000, 714613860, 747093750, 757735500, 
 769456199, 777777777, 853796995, 937500000, 1371513715, 1512715127, 
 1656354715, 1728817288, 1944919449, 2158750000}

Perhatikan bahwa ada angka tak terbatas nomor kiri-licik dan licik, karena ada beberapa cara untuk menghasilkan mereka dari yang ada:

  • Seseorang dapat menambahkan angka arbitrer 0s ke angka licik kiri mana digit paling signifikan lebih besar dari digit paling signifikan untuk mendapatkan angka licik kiri lainnya.
  • Demikian juga, seseorang dapat menambahkan angka arbitrer 0s ke angka licik mana pun yang digit paling signifikan kurang dari digit paling signifikan. Ini (dan pernyataan sebelumnya) adalah karena 0akan ditambahkan ke nomor licik dan nomor terkait, secara efektif mengalikan keduanya dengan 10.
  • Setiap ganjil 2s atau 5s adalah licik.
  • Setiap angka ganjil 777adalah licik.
  • Tampaknya jumlah ganjil yang 28bergabung dengan 0s, seperti 28028028selalu licik.

Hal-hal lain yang perlu diperhatikan:

  • Setidaknya ada empat angka 10 digit yang terdiri dari dua angka lima digit berulang (yang sendiri tidak licik, tetapi mungkin ada beberapa pola di sini).
  • Ada banyak angka licik yang merupakan kelipatan 125. Mungkin perlu menyelidiki mereka untuk menemukan aturan produksi lain.
  • Saya belum menemukan angka licik kiri yang dimulai dengan 4 atau berakhir dengan 3.
  • Angka licik dapat dimulai dengan angka apa pun, tetapi saya belum menemukan angka licik yang diakhiri dengan 1 atau 3.

Saya kira daftar ini akan lebih menarik jika saya menghilangkan mereka yang keberadaannya tersirat oleh angka licik yang lebih kecil, terutama karena ini tidak pernah menjadi bilangan prima oleh aturan konstruksi yang ditemukan sejauh ini. Jadi di sini adalah semua bilangan prima licik yang tidak dapat dibangun dengan salah satu aturan di atas:

Left-crafty:
{16, 68, 2605, 7589, 7689, 9397, 9777, 16064, 16122, 24682, 
 93557, 247522, 254408, 949395, 2709661, 2710271, 2717529, 3517736,
 9754696, 11350875, 52623721, 68654516, 129129129, 275836752, 
 333018547, 370938016, 877827179, 1944919449}

Right-crafty:
{16, 28, 68, 125, 128, 175, 284, 1575, 1625, 1875, 3449, 5217, 
 6287, 9375, 14625, 16736, 19968, 52990, 53145, 58750, 127625, 
 152628, 293750, 593750, 683860, 1034375, 1340625, 1488736, 2158750,
 2863740, 7577355, 12071125, 19325648, 29811250, 42107160, 44888540,
 71461386, 74709375, 100540625, 116382104, 164371875, 197313776,
 207144127, 226071269, 227896480, 274106547, 284284284, 287222080, 
 600481125, 769456199, 853796995, 1371513715, 1512715127, 1656354715, 
 1728817288, 1944919449}

Perhatikan juga bahwa ada beberapa angka licik ganda (yang muncul di kedua daftar dan karenanya membagi kedua angka terkait):

{2, 5, 16, 28, 68, 222, 555, 777, 22222, 55555, 2222222, 5555555, 1944919449}

Ada banyak hal yang tak terhingga juga. Tapi seperti yang Anda lihat, kecuali 16, 28, 68ini semua hanya terdiri dari (diulang) digit tunggal. Ini juga akan menarik untuk membuktikan apakah angka yang lebih besar dapat menjadi dua kali lipat licik tanpa memiliki properti itu, tetapi itu mungkin hanya akan keluar sebagai akibat wajar dari bukti angka tunggal yang licik. Menemukan contoh tandingan 1944919449.

Martin Ender
sumber
Apakah ada alasan yang Anda miliki 100540625, 100540625dalam daftar licik Anda?
isaacg
1
@isaacg ya. karena saya tidak bisa menyalin dan menempel.
Martin Ender
Menerima ini karena tidak ada yang menemukan bilangan prima licik melampaui 93.557. Ini adalah jawaban pertama, pilihan tertinggi, dan masuk ke kedalaman paling dalam.
Hobi Calvin
6

Perl (1e5 dalam 0,03s, 1e8 dalam 21s). Maks 93557 hingga 1e11.

Sangat mirip dengan aslinya. Perubahan meliputi:

  • transpos pencarian dasar. Penghematan tergantung pada bahasa kecil.
  • mod pergeseran kanan yang bertambah alih-alih jika. Ketergantungan mikro bergantung pada bahasa.
  • gunakan Math :: GMPz karena Perl 5 tidak memiliki bigint auto-sihir seperti Python dan Perl 6.
  • Gunakan 2s <= kiri dan bukan int (kiri / s)> = 2. Pergeseran bilangan bulat asli vs pembagian bigint.

Melakukan prie 1e8 pertama dalam 21 detik pada mesin cepat saya, 3,5 menit untuk 1e9, 34 menit untuk 1e10. Saya sedikit terkejut itu sama sekali lebih cepat daripada kode Python untuk input kecil. Kita bisa memparalelkan (Pari / GP baru parforprimeakan bagus untuk ini). Karena ini adalah pencarian, kita dapat memparalelkan dengan tangan saya kira ( forprimesdapat mengambil dua argumen). forprimespada dasarnya seperti Pari / GP forprime- itu memang saringan tersegmentasi secara internal dan memanggil blok dengan setiap hasil. Memang nyaman, tetapi untuk masalah ini saya tidak berpikir itu adalah area kinerja.

#!/usr/bin/env perl
use warnings;
use strict;
use Math::Prime::Util qw/forprimes/;
use Math::GMPz;

my @rbase = (
  [   0,"",       0,   0,  0, 0, 0, 0, 0, 0],
  [qw/1 0         1    1   1  1  1  1  1  1/],
  [qw/2 00        10   2   2  2  2  2  2  2/],
  [qw/3 000       11   10  3  3  3  3  3  3/],
  [qw/4 0000      100  11  10 4  4  4  4  4/],
  [qw/5 00000     101  12  11 10 5  5  5  5/],
  [qw/6 000000    110  20  12 11 10 6  6  6/],
  [qw/7 0000000   111  21  13 12 11 10 7  7/],
  [qw/8 00000000  1000 22  20 13 12 11 10 8/],
  [qw/9 000000000 1001 100 21 14 13 12 11 10/],
);

my($s,$left,$right,$slen,$i,$barray);
forprimes {
  ($s,$slen,$left,$right) = ($_,length($_),'','');
  foreach $i (0 .. $slen-1) {
    $barray = $rbase[substr($s,$i,1)];
    $left  .= $barray->[substr($s,$i-1,1)];
    $right .= $barray->[substr($s,($i+1) % $slen,1)];
  }
  $left = Math::GMPz::Rmpz_init_set_str($left,10) if length($left) >= 20;
  $right = Math::GMPz::Rmpz_init_set_str($right,10) if length($right) >= 20;
  print "$s      $left $right\n" if (($s<<1) <= $left && $left % $s == 0)
                                 || (($s<<1) <= $right && $right % $s == 0);
} 1e9;
DanaJ
sumber
5

C ++ 11, dengan utas dan GMP

Pengaturan Waktu (di MacBook Air):

  • 4 utas
    • 10 ^ 8 dalam 2.18986s
    • 10 ^ 9 dalam 21,3829s
    • 10 ^ 10 dalam 421.392s
    • 10 ^ 11 dalam 2557.22s
  • 1 utas
    • 10 ^ 8 dalam 3,95095s
    • 10 ^ 9 dalam 37.7009s

Persyaratan:

#include <vector>
#include <iostream>
#include <chrono>
#include <cmath>
#include <future>
#include <mutex>
#include <atomic>
#include "primesieve.hpp"
#include "gmpxx.h"

using namespace std;

using ull = unsigned long long;

mutex cout_mtx;
atomic<ull> prime_counter;


string ppnum(ull number) {
    if (number == 0) {
        return "0 * 10^0";
    }
    else {
        int l = floor(log10(number));
        return to_string(number / pow(10, l)) + " * 10^" + to_string(int(l));
    }
}


inline void bases(int& base, int& digit, mpz_class& sofar) {
    switch (base) {
        case 0:
            sofar *= 10;
            sofar += digit;
            break;
        case 1:
            sofar *= pow(10, digit);
            break;
        case 2:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 100; sofar += 10; break;
                case 3: sofar *= 100; sofar += 11; break;
                case 4: sofar *= 1000; sofar += 100; break;
                case 5: sofar *= 1000; sofar += 101; break;
                case 6: sofar *= 1000; sofar += 110; break;
                case 7: sofar *= 1000; sofar += 111; break;
                case 8: sofar *= 10000; sofar += 1000; break;
                case 9: sofar *= 10000; sofar += 1001; break;
            }
            break;
        case 3:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 100; sofar += 10; break;
                case 4: sofar *= 100; sofar += 11; break;
                case 5: sofar *= 100; sofar += 12; break;
                case 6: sofar *= 100; sofar += 20; break;
                case 7: sofar *= 100; sofar += 21; break;
                case 8: sofar *= 100; sofar += 22; break;
                case 9: sofar *= 1000; sofar += 100; break;
            }
            break;
        case 4:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 10; sofar += 3; break;
                case 4: sofar *= 100; sofar += 10; break;
                case 5: sofar *= 100; sofar += 11; break;
                case 6: sofar *= 100; sofar += 12; break;
                case 7: sofar *= 100; sofar += 13; break;
                case 8: sofar *= 100; sofar += 20; break;
                case 9: sofar *= 100; sofar += 21; break;
            }
            break;
        case 5:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 10; sofar += 3; break;
                case 4: sofar *= 10; sofar += 4; break;
                case 5: sofar *= 100; sofar += 10; break;
                case 6: sofar *= 100; sofar += 11; break;
                case 7: sofar *= 100; sofar += 12; break;
                case 8: sofar *= 100; sofar += 13; break;
                case 9: sofar *= 100; sofar += 14; break;
            }
            break;
        case 6:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 10; sofar += 3; break;
                case 4: sofar *= 10; sofar += 4; break;
                case 5: sofar *= 10; sofar += 5; break;
                case 6: sofar *= 100; sofar += 10; break;
                case 7: sofar *= 100; sofar += 11; break;
                case 8: sofar *= 100; sofar += 12; break;
                case 9: sofar *= 100; sofar += 13; break;
            }
            break;
        case 7:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 10; sofar += 3; break;
                case 4: sofar *= 10; sofar += 4; break;
                case 5: sofar *= 10; sofar += 5; break;
                case 6: sofar *= 10; sofar += 6; break;
                case 7: sofar *= 100; sofar += 10; break;
                case 8: sofar *= 100; sofar += 11; break;
                case 9: sofar *= 100; sofar += 12; break;
            }
            break;
        case 8:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 10; sofar += 3; break;
                case 4: sofar *= 10; sofar += 4; break;
                case 5: sofar *= 10; sofar += 5; break;
                case 6: sofar *= 10; sofar += 6; break;
                case 7: sofar *= 10; sofar += 7; break;
                case 8: sofar *= 100; sofar += 10; break;
                case 9: sofar *= 100; sofar += 11; break;
            }
            break;
        case 9:
            switch (digit) {
                case 0: sofar *= 10; break;
                case 1: sofar *= 10; sofar += 1; break;
                case 2: sofar *= 10; sofar += 2; break;
                case 3: sofar *= 10; sofar += 3; break;
                case 4: sofar *= 10; sofar += 4; break;
                case 5: sofar *= 10; sofar += 5; break;
                case 6: sofar *= 10; sofar += 6; break;
                case 7: sofar *= 10; sofar += 7; break;
                case 8: sofar *= 10; sofar += 8; break;
                case 9: sofar *= 100; sofar += 10; break;
            }
            break;
    };
}

vector<ull> crafty(ull start, ull stop) {
    cout_mtx.lock();
    cout << "Thread scanning from " << start << " to " << stop << endl;
    cout_mtx.unlock();
    vector<ull> res;

    auto prime_iter = primesieve::iterator(start);
    ull num;
    int prev, curr, next, fprev;
    int i, size;
    mpz_class left, right;
    unsigned long num_cpy;
    unsigned long* num_ptr;
    mpz_class num_mpz;


    while ((num = prime_iter.next_prime()) && num < stop) {
        ++prime_counter;
        left = 0;
        right = 0;
        size = floor(log10(num));
        i = pow(10, size);
        prev = num % 10;
        fprev = curr = num / i;
        if (i != 1) {
            i /= 10;
            next = (num / i) % 10;
        }
        else {
            next = prev;
        }
        for (size += 1; size; --size) {
            bases(prev, curr, left);
            bases(next, curr, right);
            prev = curr;
            curr = next;
            if (i > 1) {
                i /= 10;
                next = (num / i) % 10;
            }
            else {
                next = fprev;
            }
        }
        num_cpy = num;

        if (num != num_cpy) {
            num_ptr = (unsigned long *) &num;
            num_mpz = *num_ptr;
            num_mpz << sizeof(unsigned long) * 8;
            num_mpz += *(num_ptr + 1);
        }
        else {
            num_mpz = num_cpy;
        }
        if ((left % num_mpz == 0 && left / num_mpz >= 2) || (right % num_mpz == 0 && right / num_mpz >= 2)) {
            res.push_back(num);
        }
    }
    cout_mtx.lock();
    cout << "Thread scanning from " << start << " to " << stop << " is done." << endl;;
    cout << "Found " << res.size() << " crafty primes." << endl;
    cout_mtx.unlock();
    return res;
}

int main(int argc, char *argv[]) {
    ull start = 0, stop = 1000000000;
    int number_of_threads = 4;

    if (argc > 1) {
        start = atoll(argv[1]);
    }
    if (argc > 2) {
        stop = atoll(argv[2]);
    }
    if (argc > 3) {
        number_of_threads = atoi(argv[3]);
    }
    ull gap = stop - start;

    cout << "Start: " << ppnum(start) << ", stop: " << ppnum(stop) << endl;
    cout << "Scanning " << ppnum(gap) << " numbers" << endl;
    cout << "Number of threads: " << number_of_threads << endl;

    chrono::time_point<chrono::system_clock> tstart, tend;
    tstart = chrono::system_clock::now();

    cout << "Checking primes..." << endl;

    using ptask = packaged_task<decltype(crafty)>;
    using fur = future<vector<ull>>;

    vector<thread> threads;
    vector<fur> futures;
    for (int i = 0; i < number_of_threads; ++i) {
        auto p = ptask(crafty);
        futures.push_back(move(p.get_future()));
        auto tstop = (i + 1 == number_of_threads) ? (stop) : (start + gap / number_of_threads * (i + 1));
        threads.push_back(thread(move(p), start + gap / number_of_threads * i, tstop));
    }

    vector<ull> res;

    for (auto& thread : threads) {
        thread.join();
    }

    for (auto& fut : futures) {
        auto v = fut.get();
        res.insert(res.end(), v.begin(), v.end());
    }

    cout << "Finished checking primes..." << endl;

    tend = chrono::system_clock::now();
    chrono::duration<double> elapsed_seconds = tend - tstart;

    cout << "Number of tested primes: " << ppnum(prime_counter) << endl;
    cout << "Number of found crafty primes: " << res.size() << endl;
    cout << "Crafty primes are: ";
    for (auto iter = res.begin(); iter != res.end(); ++iter) {
        if (iter != res.begin())
            cout << ", ";
        cout << *iter;
    }
    cout << endl;
    cout << "Time taken: " << elapsed_seconds.count() << endl;
}

Keluaran:

Start: 0 * 10^0, stop: 1.000000 * 10^11
Scanning 1.000000 * 10^11 numbers
Number of threads: 4
Checking primes...
Thread scanning from 25000000000 to 50000000000
Thread scanning from 0 to 25000000000
Thread scanning from 50000000000 to 75000000000
Thread scanning from 75000000000 to 100000000000
Thread scanning from 75000000000 to 100000000000 is done.
Found 0 crafty primes.
Thread scanning from 50000000000 to 75000000000 is done.
Found 0 crafty primes.
Thread scanning from 25000000000 to 50000000000 is done.
Found 0 crafty primes.
Thread scanning from 0 to 25000000000 is done.
Found 7 crafty primes.
Finished checking primes...
Number of tested primes: 4.118055 * 10^9
Number of found crafty primes: 7
Crafty primes are: 2, 5, 3449, 6287, 7589, 9397, 93557
Time taken: 2557.22
matsjoyce
sumber
Pada num = 12919, kanan harus 120000000001000000000000. Ini meluap int 64-bit, dan dalam program Anda r = 9223372036854775807. Saya pikir Anda akan perlu menggunakan GMP atau yang serupa.
DanaJ
Sangat bagus. Pengaturan waktu pada 3930K dengan 12 utas adalah 54 detik untuk 1e10 dan 1e11 pada 421s.
DanaJ
Itu alasan yang bagus untuk mencoba fitur concurrency C ++ 11
matsjoyce
1

C, dengan GMP, multithreaded (1e8 in 17s for 1 thread)

Mirip dalam konsep dengan yang lain, dengan mungkin sedikit optimasi di sana-sini.

Menyusun: gcc -I/usr/local/include -Ofast crafty.c -pthread -L/usr/local/lib -lgmp && ./a.out

Mohon donasikan kekuatan CPU Anda. Saya tidak punya komputer yang cepat.
1e8 dalam 17 detik dengan 1 utas di macbook air saya.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <gmp.h>
#include <pthread.h>
#include <string.h>

#define THREAD_COUNT 1           // Number of threads
#define MAX_DIGITS   32768       // Maximum digits allocated for the string... some c stuff
#define MAX_NUMBER   "100000000" // Number in string format
#define START_INDEX  1           // Must be an odd number >= 1
#define GET_WRAP_INDEX(index, stringLength) index<0?stringLength+index:index>=stringLength?index-stringLength:index

static void huntCraftyPrime(int startIndex) {

    char lCS [MAX_DIGITS];
    char rCS [MAX_DIGITS];
    char tPS [MAX_DIGITS];

    mpz_t tP, lC, rC, max;
    mpz_init_set_ui(tP, startIndex);
    mpz_init(lC);
    mpz_init(rC);
    mpz_init_set_str(max, MAX_NUMBER, 10);

    int increment = THREAD_COUNT*2;

    if (START_INDEX < 9 && startIndex == START_INDEX) {
        printf("10 10 2\n\n");
        printf("10 10 5\n\n");
    }

    while (mpz_cmp(max, tP) > 0) {
        mpz_get_str(tPS, 10, tP);
        int tPSLength = strlen(tPS);
        int l = 0, r = 0, p = 0;
        while (p < tPSLength) {
            char lD = tPS[GET_WRAP_INDEX(p-1, tPSLength)];
            char d  = tPS[GET_WRAP_INDEX(p  , tPSLength)];
            char rD = tPS[GET_WRAP_INDEX(p+1, tPSLength)];
            if (d == '0') {
                if (lD != '1') lCS[l++] = '0';
                if (rD != '1') rCS[r++] = '0';
            } else if (d == '1') {
                lCS[l++] = (lD != '1') ? '1' : '0';
                rCS[r++] = (rD != '1') ? '1' : '0';
            } else if (d == '2') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '2';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '2';
                }
            } else if (d == '3') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '3') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '3';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '3') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '3';
                }
            } else if (d == '4') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '3') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '4') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '4';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '3') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '4') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '4';
                }
            } else if (d == '5') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                    lCS[l++] = '1';
                } else if (lD == '3') {
                    lCS[l++] = '1';
                    lCS[l++] = '2';
                } else if (lD == '4') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '5') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '5';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                    rCS[r++] = '1';
                } else if (rD == '3') {
                    rCS[r++] = '1';
                    rCS[r++] = '2';
                } else if (rD == '4') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '5') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '5';
                }
            } else if (d == '6') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else if (lD == '3') {
                    lCS[l++] = '2';
                    lCS[l++] = '0';
                } else if (lD == '4') {
                    lCS[l++] = '1';
                    lCS[l++] = '2';
                } else if (lD == '5') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '6') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '6';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else if (rD == '3') {
                    rCS[r++] = '2';
                    rCS[r++] = '0';
                } else if (rD == '4') {
                    rCS[r++] = '1';
                    rCS[r++] = '2';
                } else if (rD == '5') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '6') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '6';
                }
            } else if (d == '7') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '3') {
                    lCS[l++] = '2';
                    lCS[l++] = '1';
                } else if (lD == '4') {
                    lCS[l++] = '1';
                    lCS[l++] = '3';
                } else if (lD == '5') {
                    lCS[l++] = '1';
                    lCS[l++] = '2';
                } else if (lD == '6') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '7') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '7';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '3') {
                    rCS[r++] = '2';
                    rCS[r++] = '1';
                } else if (rD == '4') {
                    rCS[r++] = '1';
                    rCS[r++] = '3';
                } else if (rD == '5') {
                    rCS[r++] = '1';
                    rCS[r++] = '2';
                } else if (rD == '6') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '7') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '7';
                }
            } else if (d == '8') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '3') {
                    lCS[l++] = '2';
                    lCS[l++] = '2';
                } else if (lD == '4') {
                    lCS[l++] = '2';
                    lCS[l++] = '0';
                } else if (lD == '5') {
                    lCS[l++] = '1';
                    lCS[l++] = '3';
                } else if (lD == '6') {
                    lCS[l++] = '1';
                    lCS[l++] = '2';
                } else if (lD == '7') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '8') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '8';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '3') {
                    rCS[r++] = '2';
                    rCS[r++] = '2';
                } else if (rD == '4') {
                    rCS[r++] = '2';
                    rCS[r++] = '0';
                } else if (rD == '5') {
                    rCS[r++] = '1';
                    rCS[r++] = '3';
                } else if (rD == '6') {
                    rCS[r++] = '1';
                    rCS[r++] = '2';
                } else if (rD == '7') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '8') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '8';
                }
            } else if (d == '9') {
                if (lD == '1') {
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '2') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                    lCS[l++] = '1';
                } else if (lD == '3') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                    lCS[l++] = '0';
                } else if (lD == '4') {
                    lCS[l++] = '2';
                    lCS[l++] = '1';
                } else if (lD == '5') {
                    lCS[l++] = '1';
                    lCS[l++] = '4';
                } else if (lD == '6') {
                    lCS[l++] = '1';
                    lCS[l++] = '3';
                } else if (lD == '7') {
                    lCS[l++] = '1';
                    lCS[l++] = '2';
                } else if (lD == '8') {
                    lCS[l++] = '1';
                    lCS[l++] = '1';
                } else if (lD == '9') {
                    lCS[l++] = '1';
                    lCS[l++] = '0';
                } else {
                    lCS[l++] = '9';
                }
                if (rD == '1') {
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '2') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                    rCS[r++] = '1';
                } else if (rD == '3') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                    rCS[r++] = '0';
                } else if (rD == '4') {
                    rCS[r++] = '2';
                    rCS[r++] = '1';
                } else if (rD == '5') {
                    rCS[r++] = '1';
                    rCS[r++] = '4';
                } else if (rD == '6') {
                    rCS[r++] = '1';
                    rCS[r++] = '3';
                } else if (rD == '7') {
                    rCS[r++] = '1';
                    rCS[r++] = '2';
                } else if (rD == '8') {
                    rCS[r++] = '1';
                    rCS[r++] = '1';
                } else if (rD == '9') {
                    rCS[r++] = '1';
                    rCS[r++] = '0';
                } else {
                    rCS[r++] = '9';
                }
            }
            ++p;
        }
        lCS[l] = '\0';
        rCS[r] = '\0';

        mpz_set_str(lC, lCS, 10);
        mpz_set_str(rC, rCS, 10);

        if ((mpz_divisible_p(lC, tP) && mpz_cmp(lC, tP) > 0) || (mpz_divisible_p(rC, tP) && mpz_cmp(rC, tP) > 0)){
            if (mpz_millerrabin(tP, 25)) {
                gmp_printf("%Zd %Zd %Zd\n\n", lC, rC, tP);
            }
        }
        mpz_add_ui(tP, tP, increment);
    }
}

static void *huntCraftyPrimeThread(void *p) {
    int* startIndex = (int*) p;
    huntCraftyPrime(*startIndex);
    pthread_exit(NULL);
}

int main(int argc, char *argv[]) {

    struct timeval time_started, time_now, time_diff;
    gettimeofday(&time_started, NULL);

    int  startIndexes[THREAD_COUNT];
    pthread_t threads[THREAD_COUNT];

    int startIndex = START_INDEX;
    for (int i = 0; i < THREAD_COUNT; ++i) {
        for (;startIndex % 2 == 0; ++startIndex);
        startIndexes[i] = startIndex;
        int rc = pthread_create(&threads[i], NULL, huntCraftyPrimeThread, (void*)&startIndexes[i]); 
        if (rc) { 
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
        ++startIndex;
    }

    for (int i = 0; i < THREAD_COUNT; ++i) {
        void * status;
        int rc = pthread_join(threads[i], &status);
        if (rc) {
            printf("ERROR: return code from pthread_join() is %d\n", rc);
            exit(-1);
        }
    }

    gettimeofday(&time_now, NULL);
    timersub(&time_now, &time_started, &time_diff);
    printf("Time taken,%ld.%.6d s\n", time_diff.tv_sec, time_diff.tv_usec);

    pthread_exit(NULL);
    return 0;
}
Vektor
sumber
0

Python, menemukan 93557 dalam 0,28s

Sangat mirip dengan kode OP yang digunakannya pyprimes. Saya menulis ini sendiri meskipun xD

import pyprimes, time

d = time.clock()

def to_base(base, n):
    if base == 1:
        return '0'*n
    s = ""
    while n:
        s = str(n % base) + s
        n //= base
    return s

def crafty(n):
    digits = str(n)
    l, r = "", ""
    for i in range(len(digits)):
        t = int(digits[i])
        base = int(digits[i-1])
        l += to_base(base, t) if base else digits[i]
        base = int(digits[(i+1)%len(digits)])
        r += to_base(base, t) if base else digits[i]
    l, r = int(l) if l else 0, int(r) if r else 0
    if (l%n==0 and 2 <= l/n) or (r%n==0 and 2 <= r/n):
        print(n, l, r, time.clock()-d)

for i in pyprimes.primes_above(1):
    crafty(i)

Ini juga mencetak waktu sejak awal yang menemukan nomor.

Keluaran:

2 10 10 3.156656792490237e-05
5 10 10 0.0006756015452219958
3449 3111021 3104100 0.012881854420378145
6287 6210007 11021111 0.022036544076745254
7589 751311 125812 0.026288406792971432
9397 1231007 1003127 0.03185028207808106
93557 123121012 10031057 0.27897531840850603

Formatnya adalah number left right time. Sebagai perbandingan, kode OP menemukan 93557 di sekitar 0.37.

cjfaure
sumber