Introducción

Considere el proceso de tomar un número entero positivo n en alguna base b y reemplazar cada dígito con su representación en la base del dígito a la derecha.

• Si el dígito a la derecha es a 0, use la base b .
• Si el dígito a la derecha es un 1, use unario con 0 como marcas de conteo.
• Si no hay un dígito a la derecha (es decir, está en el lugar de las unidades), recorra el dígito más significativo.

Como ejemplo, n = 160 yb = 10. La ejecución del proceso se ve así:

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.

El mismo procedimiento exacto pero moviéndose a la izquierda en lugar de a la derecha también se puede hacer:

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.

Por lo tanto, hemos hecho dos números relacionados con 160 (para b = 10): 16 y 10000000.

Definiremos n como un número astuto si divide al menos uno de los dos números generados en este proceso en 2 o más partes

En el ejemplo, n es astuto porque 160 divide 10000000 exactamente 62500 veces.

203 NO es astuto porque los números resultantes son 2011 y 203 en sí, que 203 no pueden caber uniformemente en 2 o más veces.

Desafío

(Para el resto del problema solo consideraremos b = 10.)

El desafío es escribir un programa que encuentre el número astuto más alto que también sea primo.

Los primeros 7 primos astutos (y todo lo que he encontrado hasta ahora) son:

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

Oficialmente no estoy seguro de si existen más, pero espero que existan. Si puedes demostrar que hay (o no) finitamente muchos, te daré +200 repeticiones.

El ganador será la persona que pueda proporcionar el mejor nivel de astucia, siempre que sea evidente que han estado activos en la búsqueda y que no están tomando la gloria intencionalmente de los demás.

Reglas

• Puede usar cualquier herramienta de búsqueda principal que desee.
• Puede utilizar probadores primarios probabilísticos.
• Puede reutilizar el código de otras personas con atribución . Este es un esfuerzo comunitario. Las tácticas feroces no serán toleradas.
• Su programa debe buscar activamente la prima. Puede comenzar su búsqueda en el primer astuto más alto conocido.
• Su programa debería poder calcular todos los primos astutos conocidos dentro de las 4 horas posteriores a las instancias de Amazon EC2 t2.medium (ya sea cuatro a la vez o una durante cuatro horas o algo intermedio). En realidad no lo probaré en ellos y ciertamente no es necesario. Esto es solo un punto de referencia.

Aquí está mi código Python 3 que usé para generar la tabla anterior: (se ejecuta en un segundo o dos)

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

Mathematica, encuentra 93,557 en 0.3s (no más primos astutos por debajo de 2 * 10 ¹⁰ )

Esta es solo una búsqueda ingenua y exhaustiva a través de todos los números primos. Para comenzar, verifica aproximadamente 1,000,000 de primos cada 55 segundos (lo que seguramente se hará más lento a medida que los primos se hacen más grandes).

Estoy usando un montón de funciones de ayuda:

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

Y luego este bucle realiza la búsqueda real:

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

Seguiré actualizando la publicación, si encuentro primos o puedo pensar en optimizaciones.

Actualmente verifica todos los números primos hasta 100,000,000 en aproximadamente 5.5 minutos.

Editar: decidí seguir el ejemplo del OP y cambié a una tabla de búsqueda para la conversión de base. Eso dio aproximadamente un 30% de aceleración.

Números astutos en general

Estoy deteniendo mi búsqueda de primos astutos ahora, ya que necesitaría varios días para ponerme al día con la respuesta de Perl. En cambio, comencé a buscar todos los números astutos. Tal vez su distribución ayude a encontrar una prueba de que el número de primos astutos es finito o infinito.

Defino derecha astuto números de aquellos que dividen el número relacionado obtenido mediante la interpretación del dígito a la derecha como la nueva base, y -izquierda astuto números en consecuencia. Probablemente ayudará a abordarlos individualmente como prueba.

Aquí están todos los números astutos a la izquierda hasta 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}

Y aquí están todos los números astutos correctos en ese rango:

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

Tenga en cuenta que hay un número infinito de números astutos a la izquierda y a la derecha, porque hay varias formas de generarlos a partir de los existentes:

• Se puede agregar un número arbitrario de 0s a cualquier número de izquierda-astucia cuyo dígito menos significativo sea mayor que su dígito más significativo para obtener otro número de izquierda-astuto.
• Del mismo modo, se puede agregar un número arbitrario de 0s a cualquier número ingenioso cuyo dígito menos significativo sea menor que su dígito más significativo. Esto (y la declaración anterior) se debe a 0que se agregará tanto al número astuto como a su número relacionado, multiplicándolos efectivamente por 10.
• Cada número impar de 2so 5s es astuto.
• Cada número impar de 777s es astuto.
• Parece que un número impar de s 28unidos 0, como, 28028028siempre es astuto.

Otras cosas a tener en cuenta:

• Hay al menos cuatro números de 10 dígitos que consisten en dos números repetidos de cinco dígitos (que en sí mismos no son astutos, pero puede haber algún patrón aquí de todos modos).
• Hay muchos números diestros que son múltiplos de 125. Podría valer la pena investigarlos para encontrar otra regla de producción.
• No he encontrado un número astuto a la izquierda que comience con 4 o termine con 3.
• Los números del lado derecho pueden comenzar con cualquier dígito, pero no he encontrado un número del lado derecho que termine en 1 o 3.

Supongo que esta lista sería más interesante si omitiera aquellos cuya existencia está implicada por un número astuto más pequeño, especialmente porque estas reglas de construcción descubiertas hasta ahora nunca son números primos. Así que aquí están todos los primos astutos que no pueden construirse con una de las reglas anteriores:

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}

Tenga en cuenta también que hay algunos números doblemente astutos (los que aparecen en ambas listas y, por lo tanto, dividen ambos números relacionados):

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

Existen infinitamente muchos de estos también. Pero como se puede ver, a excepción de 16, 28, 68todos éstos consisten únicamente de un solo dígito (repetido). También sería interesante probar si cualquier número mayor puede ser doblemente astuto sin tener esa propiedad, pero eso podría desaparecer como un corolario de una prueba de números ingeniosamente simples. Encontré el contraejemplo 1944919449.

Perl (1e5 en 0.03s, 1e8 en 21s). Máx. 93557 a 1e11.

Muy similar al original. Los cambios incluyen:

• transponer la búsqueda de base. Pequeños ahorros dependientes del idioma.
• modifique el desplazamiento a la derecha incrementado en lugar de if. Micro-opt dependiente del idioma.
• use Math :: GMPz porque Perl 5 no tiene bigints auto-mágicos como Python y Perl 6.
• Use 2s <= left en lugar de int (left / s)> = 2. Desplazamiento de entero nativo vs.división bigint.

Hace los primeros 1e8 primos en 21 segundos en mi máquina rápida, 3.5 minutos por 1e9, 34 minutos por 1e10. Estoy un poco sorprendido de que sea más rápido que el código Python para entradas pequeñas. Podríamos paralelizar (lo nuevo de Pari / GP parforprimesería bueno para esto). Como es una búsqueda, podemos paralelizar a mano, supongo ( forprimespuede tomar dos argumentos). forprimeses básicamente como Pari / GP's forprime: hace tamices segmentados internamente y llama al bloque con cada resultado. Es conveniente, pero para este problema no creo que sea un área de rendimiento.

#!/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;

C ++ 11, con hilos y GMP

Tiempo (en una MacBook Air):

• 4 hilos
  • 10 ^ 8 en 2.18986s
  • 10 ^ 9 en 21.3829s
  • 10 ^ 10 en 421.392s
  • 10 ^ 11 en 2557.22s
• 1 hilo
  • 10 ^ 8 en 3.95095s
  • 10 ^ 9 en 37.7009s

Requisitos:

• Necesita https://github.com/kimwalisch/primesieve y https://gmplib.org/
• Compilar: g++ crafty.cpp -o crafty --std=c++11 -ffast-math -lprimesieve -O3 -lgmpxx -lgmp -Wall -Wextra

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

Salida:

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

C, con GMP, multiproceso (1e8 en 17s para 1 hilo)

Similar en concepto al resto, con probablemente un poco de optimizaciones aquí y allá.

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

Por favor done su poder de CPU. No tengo una computadora rápida.
1e8 en 17 segundos con 1 hilo en mi 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;
}

Python, encuentra 93557 en 0.28s

Muy similar al código de OP en que también usa pyprimes. Yo mismo escribí esto aunque 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)

También imprime el tiempo desde el inicio que encuentra un número.

Salida:

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

El formato es number left right time. Como comparación, el código de OP encuentra 93557 alrededor 0.37.