Finde die schlaueste Primzahl

9

Intro

Betrachten Sie den Prozess, bei dem eine positive ganze Zahl n in einer Basis b genommen und jede Ziffer durch ihre Darstellung in der Basis der Ziffer rechts ersetzt wird.

  • Wenn die Ziffer rechts eine 0 ist, verwenden Sie die Basis b .
  • Wenn die Ziffer rechts eine 1 ist, verwenden Sie unär mit Nullen als Strichmarkierungen.
  • Wenn sich rechts keine Ziffer befindet (dh Sie befinden sich an der richtigen Stelle), wechseln Sie zur höchstwertigen Ziffer.

Als Beispiel sei n = 160 und b = 10. Das Ausführen des Prozesses sieht folgendermaßen aus:

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.

Das genau gleiche Verfahren, aber das Bewegen nach links statt nach rechts kann auch durchgeführt werden:

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.

Daher haben wir zwei Zahlen für 160 (für b = 10) erstellt: 16 und 10000000.

Wir werden n als eine listige Zahl definieren, wenn sie mindestens eine der beiden in diesem Prozess erzeugten Zahlen gleichmäßig in zwei oder mehr Teile aufteilt

Im Beispiel ist n schlau, weil 160 10000000 genau 62500 mal teilt.

203 ist NICHT schlau, da die resultierenden Zahlen 2011 und 203 selbst sind, die 203 nicht gleichmäßig in zwei oder mehr Male passen können.

Herausforderung

(Für den Rest des Problems betrachten wir nur b = 10.)

Die Herausforderung besteht darin, ein Programm zu schreiben, das die höchste schlauen Zahl findet, die auch eine Primzahl ist.

Die ersten 7 schlauen Primzahlen (und alles, was ich bisher gefunden habe) sind:

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

Ich bin mir offiziell nicht sicher, ob es noch mehr gibt, aber ich gehe davon aus, dass dies der Fall ist. Wenn Sie beweisen können, dass es endlich viele gibt (oder nicht), gebe ich Ihnen +200 Kopfgeld-Repräsentanten.

Der Gewinner wird die Person sein, die die höchste schlauen Primzahl liefern kann, vorausgesetzt, es ist offensichtlich, dass sie bei der Suche aktiv war und nicht absichtlich Ruhm von anderen nimmt.

Regeln

  • Sie können alle gewünschten Suchwerkzeuge verwenden.
  • Sie können probabilistische Primetester verwenden.
  • Sie können den Code anderer Personen mit Namensnennung wiederverwenden . Dies ist eine gemeinsame Anstrengung. Cutthroat-Taktiken werden nicht toleriert.
  • Ihr Programm muss aktiv nach der Primzahl suchen. Sie können Ihre Suche am höchsten bekannten schlauen Prime beginnen.
  • Ihr Programm sollte in der Lage sein, alle bekannten schlauen Primzahlen innerhalb von 4 Stunden nach Amazon EC2 t2.medium-Instanzen zu berechnen (entweder vier auf einmal oder eine für vier Stunden oder etwas dazwischen). Ich werde es nicht wirklich an ihnen testen und du musst es bestimmt nicht. Dies ist nur ein Maßstab.

Hier ist mein Python 3-Code, den ich zum Generieren der obigen Tabelle verwendet habe: (läuft in ein oder zwei Sekunden)

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 Calvins Hobbys
quelle
Ich denke, dass es mathematischer wäre, 0 in einer beliebigen Basis x als leere Zeichenfolge zu verwenden. Ich bin mir auch sicher, dass es einfacher wäre, diese Version zu beweisen oder zu widerlegen
stolzer Haskeller

Antworten:

7

Mathematica findet 93.557 in 0,3 s (keine weiteren schlauen Primzahlen unter 2 * 10 10 )

Dies ist nur eine naive erschöpfende Suche durch alle Primzahlen. Zunächst werden alle 55 Sekunden etwa 1.000.000 Primzahlen überprüft (was mit zunehmender Primzahl zwangsläufig langsamer wird).

Ich verwende eine Reihe von Hilfsfunktionen:

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

Und dann führt diese Schleife die eigentliche Suche durch:

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

Ich werde den Beitrag weiter aktualisieren, wenn ich Primzahlen finde oder mir Optimierungen vorstellen kann.

Derzeit werden alle Primzahlen bis zu 100.000.000 in etwa 5,5 Minuten überprüft.

Bearbeiten: Ich habe mich entschlossen, dem Beispiel des OP zu folgen und bin zur Basiskonvertierung zu einer Nachschlagetabelle gewechselt. Das ergab eine Beschleunigung von ungefähr 30%.

Crafty Numbers im Allgemeinen

Ich stoppe jetzt meine Suche nach schlauen Primzahlen, da ich mehrere Tage brauchen würde, um zu erfahren, wo die Perl-Antwort bereits angekommen ist. Stattdessen fing ich an, nach allen schlauen Zahlen zu suchen. Vielleicht hilft ihre Verteilung, einen Beweis dafür zu finden, dass die Anzahl der schlauen Primzahlen endlich oder unendlich ist.

Ich definiere rechtsbastelnde Zahlen, die die zugehörige Zahl teilen, die durch Interpretieren der Ziffer rechts als neue Basis erhalten wird, und linksbastelnde Zahlen entsprechend. Es wird wahrscheinlich helfen, diese einzeln für einen Beweis anzugehen.

Hier sind alle links schlauen Zahlen bis zu 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}

Und hier sind alle richtigen Zahlen in diesem Bereich:

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

Beachten Sie, dass es unendlich viele links und rechts geschickte Zahlen gibt, da es verschiedene Möglichkeiten gibt, sie aus vorhandenen zu generieren:

  • Man kann eine beliebige Zahl von 0s an jede linksbastelnde Zahl anhängen, deren niedrigstwertige Ziffer größer als ihre höchstwertige Ziffer ist, um eine andere linksbastelnde Zahl zu erhalten.
  • Ebenso kann man eine beliebige Zahl von 0s an jede rechtschaffene Zahl anhängen, deren niedrigstwertige Ziffer kleiner als ihre höchstwertige Ziffer ist. Dies (und die vorherige Aussage) ist darauf zurückzuführen, dass die 0sowohl an die schlauen als auch an die zugehörige Nummer angehängt wird, wodurch beide effektiv mit 10 multipliziert werden.
  • Jede ungerade Anzahl von 2s oder 5s ist schlau.
  • Jede ungerade Anzahl von 777s ist schlau.
  • Es scheint, dass eine ungerade Anzahl von 28durch 0s verbundenen, wie 28028028immer schlau ist.

Andere Dinge zu beachten:

  • Es gibt mindestens vier 10-stellige Zahlen, die aus zwei wiederholten fünfstelligen Zahlen bestehen (die selbst nicht schlau sind, aber hier könnte es trotzdem ein Muster geben).
  • Es gibt viele richtig geschickte Zahlen, die ein Vielfaches von sind 125. Es könnte sich lohnen, diese zu untersuchen, um eine andere Produktionsregel zu finden.
  • Ich habe keine linke Nummer gefunden, die mit 4 beginnt oder mit 3 endet.
  • Richtig geschickte Zahlen können mit jeder Ziffer beginnen, aber ich habe keine richtig geschickte Zahl gefunden, die mit 1 oder 3 endet.

Ich nehme an, diese Liste wäre interessanter, wenn ich diejenigen weglassen würde, deren Existenz durch eine kleinere schlauen Zahl impliziert wird, zumal dies nach den bisher entdeckten Konstruktionsregeln niemals Primzahlen sind. Hier sind also alle schlauen Primzahlen, die nicht mit einer der oben genannten Regeln konstruiert werden können:

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}

Beachten Sie auch, dass es einige doppelt listige Zahlen gibt (diejenigen, die in beiden Listen erscheinen und daher beide verwandten Zahlen teilen):

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

Es gibt auch unendlich viele davon. Aber wie Sie sehen können, mit Ausnahme 16, 28, 68bestehen alle diese nur aus einer einzigen (Wiederholung) Ziffer. Es wäre auch interessant zu beweisen, ob größere Zahlen ohne diese Eigenschaft doppelt schlau sein können, aber dies könnte als Folge eines Beweises für einfach geschickte Zahlen herausfallen. Das Gegenbeispiel gefunden 1944919449.

Martin Ender
quelle
Gibt es einen Grund, den Sie 100540625, 100540625in Ihrer Liste der richtigen Handwerker haben?
isaacg
1
@isaacg ja. weil ich nicht kopieren und einfügen kann.
Martin Ender
Akzeptiere dies, da niemand mehr als 93.557 schlauen Primzahlen gefunden hat. Dies war die erste Antwort, ist am höchsten gewählt und geht in die Tiefe.
Calvins Hobbys
6

Perl (1e5 in 0,03 s, 1e8 in 21 s). Max 93557 bis 1e11.

Sehr ähnlich dem Original. Änderungen umfassen:

  • transponieren Sie die Basissuche. Kleine sprachabhängige Einsparungen.
  • mod die inkrementierte Rechtsverschiebung anstelle von if. Sprachabhängiges Mikroopt.
  • Verwenden Sie Math :: GMPz, da Perl 5 keine automatisch magischen Bigints wie Python und Perl 6 enthält.
  • Verwenden Sie 2s <= left anstelle von int (left / s)> = 2. Native Integer Shift vs. Bigint Divide.

Führt die ersten 1e8-Primzahlen in 21 Sekunden auf meiner schnellen Maschine aus, 3,5 Minuten für 1e9, 34 Minuten für 1e10. Ich bin ein wenig überrascht, dass es für kleine Eingaben überhaupt schneller ist als der Python-Code. Wir könnten parallelisieren (Pari / GPs neues parforprimewäre schön dafür). Da es sich um eine Suche handelt, können wir vermutlich von Hand parallelisieren ( forprimeskann zwei Argumente annehmen ). forprimesist im Grunde wie bei Pari / GPs forprime- es macht intern segmentierte Siebe und ruft den Block mit jedem Ergebnis auf. Es ist praktisch, aber für dieses Problem denke ich nicht, dass es ein Leistungsbereich ist.

#!/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
quelle
5

C ++ 11 mit Threads und GMP

Timing (auf einem MacBook Air):

  • 4 Fäden
    • 10 ^ 8 in 2.18986s
    • 10 ^ 9 in 21.3829s
    • 10 ^ 10 in 421.392s
    • 10 ^ 11 in 2557.22s
  • 1 Thread
    • 10 ^ 8 in 3.95095s
    • 10 ^ 9 in 37.7009s

Bedarf:

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

Ausgabe:

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
quelle
Bei num = 12919 sollte rechts 120000000001000000000 sein. Dies überläuft ein 64-Bit-int und in Ihrem Programm r = 9223372036854775807. Ich denke, Sie müssen GMP oder ähnliches verwenden.
DanaJ
Sehr schön. Das Timing auf 3930K mit 12 Threads beträgt 54s für 1e10 und 1e11 in 421s.
DanaJ
Es war eine gute Ausrede, um die Parallelität C ++ 11 Funktionen
auszuprobieren
1

C, mit GMP, Multithread (1e8 in 17s für 1 Thread)

Ähnlich im Konzept wie die anderen, wahrscheinlich mit ein paar Optimierungen hier und da.

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

Bitte spenden Sie Ihre CPU-Leistung. Ich habe keinen schnellen Computer.
1e8 in 17 Sekunden mit 1 Thread auf meinem MacBook Air.

#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;
}
Vektorisiert
quelle
0

Python findet 93557 in 0,28s

Sehr ähnlich zu OPs Code, da er auch verwendet pyprimes. Ich habe das selbst geschrieben, obwohl 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)

Es wird auch die Zeit seit dem Start ausgedruckt, zu der eine Nummer gefunden wurde.

Ausgabe:

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

Format ist number left right time. Zum Vergleich: OPs Code findet 93557 in etwa 0.37.

cjfaure
quelle