Encuentra el primo más grande que sigue siendo primo después de la eliminación de dígitos

En /math/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this se hace la siguiente pregunta. ¿Cuántos números primos hay que siguen siendo primos después de eliminar cualquiera de sus dígitos? Por ejemplo, 719es tan importante como obtienes 71, 19y 79. Si bien esta pregunta no está resuelta, pensé que sería un buen desafío de codificación.

Tarea. Proporcione el primo más grande que pueda encontrar que sigue siendo primo después de eliminar cualquiera de sus dígitos. También debe proporcionar el código que lo encuentra.

Puntuación. El valor de la prima que das.

Puede usar cualquier lenguaje de programación y bibliotecas que desee siempre que sean gratuitas.

Para empezar, 99444901133es el más grande dado en la página vinculada.

Límite de tiempo. Aceptaré la respuesta correcta más grande dada exactamente una semana después de la primera respuesta correcta más grande que la 99444901133dada en una respuesta.

Puntuaciones hasta ahora.

Python (primo)

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

J (randomra) (Esta respuesta comenzó el temporizador de una semana el 21 de febrero de 2013).

222223333333

274 dígitos

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

Esto tomó alrededor de 20 horas de tiempo de CPU para encontrar, y aproximadamente 2 minutos por cebado para probar. Por el contrario, la solución de 84 dígitos se puede encontrar en unos 3 minutos.

84 dígitos

444444444444444444444444444444444444444444444444441111111113333333333333333333333333

77777777999999999999999777777777 (32 dígitos)
66666666666666622222222222222333 (32 dígitos)
647777777777777777777777777 (27 dígitos)
44444441333333333333 (20 dígitos)
999996677777777777 (18 dígitos)
7777 ( 18 dígitos 77 ) 1577

Recomiendo esta herramienta si desea confirmar la originalidad: D. Alpern's ECM Applet

También se utiliza un enfoque repdigit, que parece ser el enfoque con mayor probabilidad de encontrar valores grandes. El siguiente script omite algorítmicamente la mayoría de los números o truncamientos, lo que dará como resultado múltiplos de 2, 3, 5 y ahora 11 c / o PeterTaylor (su contribución aumentó la eficiencia en aproximadamente un 50%).

from my_math import is_prime

sets = [
 (set('147'), set('0147369'), set('1379')),
 (set('369'), set('147'), set('1379')),
 (set('369'), set('0369'), set('17')),
 (set('258'), set('0258369'), set('39')),
 (set('369'), set('258'), set('39'))]

div2or5 = set('024568')

for n in range(3, 100):
 for sa, sb, sc in sets:
  for a in sa:
   for b in sb-set([a]):
    bm1 = int(b in div2or5)
    for c in sc-set([b]):
     if int(a+b+c)%11 == 0: continue
     for na in xrange(1, n-1, 1+(n&1)):
      eb = n - na
      for nb in xrange(1, eb-bm1, 1+(~eb&1)):
       nc = eb - nb
       if not is_prime(long(a*(na-1) + b*nb + c*nc)):
        continue
       if not is_prime(long(a*na + b*(nb-1) + c*nc)):
        continue
       if not is_prime(long(a*na + b*nb + c*(nc-1))):
        continue
       if not is_prime(long(a*na + b*nb + c*nc)):
        continue
       print a*na + b*nb + c*nc

my_math.pyse puede encontrar aquí: http://codepad.org/KtXsydxK
Alternativamente, también puede usar la gmpy.is_primefunción: Proyecto GMPY

Algunas pequeñas mejoras de velocidad como resultado de la creación de perfiles. La comprobación de primalidad para el más largo de los cuatro candidatos se ha movido al final, xrangereemplaza rangey longreemplaza los inttipos de yeso. intparece tener una sobrecarga innecesaria si la expresión evaluada da como resultado a long.

Reglas de divisibilidad

Deje que N sea un número entero postitive de la forma de un ... ab ... bc ... c , donde un , b y c se repiten dígitos.

Por 2 y 5
: para evitar la divisibilidad entre 2 y 5 , c puede no estar en el conjunto [0, 2, 4, 5, 6, 8] . Además, si b es miembro de este conjunto, la longitud de c no puede ser inferior a 2.

Por 3
: si N = 1 (mod 3) , entonces N puede no contener ninguno de [1, 4, 7] , ya que la eliminación de cualquiera de estos resultados trivialmente daría como resultado un múltiplo de 3 . Del mismo modo para N = 2 (mod 3) y [2, 5, 8] . Esta implementación utiliza una forma ligeramente debilitada de esto: si N contiene uno de [1, 4, 7] , puede que no contenga ninguno de [2, 5, 8] , y viceversa. Además, N no puede consistir únicamente en [0, 3, 6, 9] . Esto es en gran medida una declaración equivalente, pero sí permite para algunos casos triviales, por ejemplo un , b , y ccada uno se repite un múltiplo de 3 veces.

Por 11
- Como señala PeterTaylor , si N tiene la forma aabbcc ... xxyyzz , es decir, consiste solo en dígitos repetidos un número par de veces, es divisible trivialmente por 11 : a0b0c ... x0y0z . Esta observación elimina la mitad del espacio de búsqueda. Si N es de longitud impar, entonces la longitud de un , b y c deben ser todos impar, así (reducción del espacio de búsqueda 75%), y si N es de longitud incluso, entonces sólo uno de una , b o c pueden ser aún de longitud (reducción del espacio de búsqueda del 25%).
- conjetura: Si abc es un múltiplo de 11 , por ejemplo 407 , a continuación, todas las repeticiones impares de un , b y c también se múltiplos de 11 . Esto cae fuera del alcance de la divisibilidad anterior por 11 regla; de hecho, solo las repeticiones impares están entre las que están explícitamente permitidas. No tengo una prueba de esto, pero las pruebas sistemáticas no pudieron encontrar un contraejemplo. Compare: 444077777 , 44444000777 , 44444440000077777777777 , etc. Cualquiera puede sentirse libre de probar o refutar esta conjetura. Aditsu ha demostrado que esto es correcto.

Otras formas

2 juegos de dígitos repetidos Los
números de la forma que randomra buscaba , a ... ab ... b , parecen ser mucho más raros. Solo hay 7 soluciones de menos de 10 ¹⁷⁰⁰ , la mayor de las cuales tiene 12 dígitos de longitud.

4 conjuntos de dígitos repetidos Los
números de esta forma, a ... ab ... bc ... cd ... d , parecen estar más densamente distribuidos que los que estaba buscando. Hay 69 soluciones de menos de 10 ¹⁰⁰ , en comparación con las 32 que usan 3 juegos de dígitos repetidos. Los que están entre 10 ¹¹ y 10 ¹⁰⁰ son los siguientes:

190000007777
700000011119
955666663333
47444444441111
66666622222399
280000000033333
1111333333334999
1111333333377779
1199999999900111
3355555666999999
2222233333000099
55555922222222233333
444444440004449999999
3366666633333333377777
3333333333999888883333
4441111113333333333311111
2222222293333333333333999999
999999999339999999977777777777
22222226666666222222222299999999
333333333333333333339944444444444999999999
559999999999933333333333339999999999999999
3333333333333333333111111111111666666666611111
11111111333330000000000000111111111111111111111
777777777770000000000000000000033333339999999999999999999999999
3333333333333333333333333333333333333333333333336666666977777777777777
666666666666666666611111113333337777777777777777777777777777777777777777
3333333333333333333888889999999999999999999999999999999999999999999999999933333333

Hay un argumento heurístico simple de por qué este debería ser el caso. Para cada longitud digital, hay una serie de conjuntos repetidos (es decir, 3 conjuntos repetidos, o 4 conjuntos repetidos, etc.) para los cuales el número esperado de soluciones será el más alto. La transición se produce cuando el número de posibles soluciones adicionales, tomadas como una relación, supera la probabilidad de que el número adicional a verificar sea primo. Dada la naturaleza exponencial de las posibilidades de verificación, y la naturaleza logarítmica de la distribución de números primos, esto sucede relativamente rápido.

Si, por ejemplo, quisiéramos encontrar una solución de 300 dígitos, verificar 4 conjuntos de dígitos repetidos sería mucho más probable que produjera una solución que 3 conjuntos, y 5 conjuntos serían aún más probables. Sin embargo, con la potencia informática que tengo a mi disposición, encontrar una solución mucho más grande que 100 dígitos con 4 juegos estaría fuera de mi capacidad, y mucho menos 5 o 6.

222223333333 (12 dígitos)

Aquí solo busqué aa..aabb..bb formato de hasta 100 dígitos. Solo otros golpes son 23 37 53 73 113 311.

Código J (limpiado) (lo siento, no hay explicación):

a=.>,{,~<>:i.100
b=.>,{,~<i.10
num=.".@(1&":)@#~
p=.(*/"1@:((1&p:)@num) (]-"1(0,=@i.@#)))"1 1
]res=./:~~.,b (p#num)"1 1/ a

Editar: Alguien ya hizo un análisis muuuucho más profundo que yo aquí.

No es una solución, sino una estimación aproximada del número de soluciones de n dígitos.

Generando código J

   ops=: 'title ','Estimated number of solutions by digits',';xcaption ','digits',';ycaption ','log10 #'
   ops plot 10^.((%^.)%(2&(%~)@^.@(%&10))^(10&^.))(10&^(2+i.100))

Javascript (fuerza bruta)

Aún no ha encontrado un número mayor

http://jsfiddle.net/79FDr/4/

Sin una biblioteca bigint, javascript está limitado a enteros <= 2^53.

Como es Javascript, el navegador se quejará si no liberamos el hilo de ejecución para que la interfaz de usuario se actualice, como resultado, decidí rastrear dónde está el algoritmo en su progresión en la interfaz de usuario.

function isPrime(n){
    return n==2||(n>1&&n%2!=0&&(function(){
        for(var i=3,max=Math.sqrt(n);i<=max;i+=2)if(n%i==0)return false;
        return true;
    })());
};

var o=$("#o"), m=Math.pow(2,53),S=$("#s");

(function loop(n){
    var s = n.toString(),t,p=true,i=l=s.length,h={};
    if(isPrime(n)){
        while(--i){
            t=s.substring(0,i-1) + s.substring(i,l); // cut out a digit
            if(!h[t]){   // keep a hash of numbers tested so we don't end up testing 
                h[t]=1;  // the same number multiple times
                if(!isPrime(+t)){p=false;break;}
            }
        }
        if(p)
            o.append($("<span>"+n+"</span>"));
    }
    S.text(n);
    if(n+2 < m)setTimeout(function(){
        loop(n+2);
    },1);
})(99444901133);

Se publicó un enlace a un análisis del problema, pero pensé que le faltaban algunas cosas. Veamos los números de m dígitos, que consisten en k secuencias de 1 o más dígitos idénticos. Se demostró que si dividimos los dígitos en los grupos {0, 3, 6, 9}, {1, 4, 7} y {2, 5, 8}, una solución no puede contener dígitos tanto del segundo como del tercer grupo , y debe contener 3n + 2 dígitos de uno de estos grupos. Al menos dos de las k secuencias deben tener un número impar de dígitos. De los dígitos {1, 4, 7} solo 1 y 7 pueden ser el dígito más bajo. Ninguno de {2, 5, 8} puede ser el dígito más bajo. Entonces hay cuatro (1, 3, 7, 9) o dos (3, 9) opciones para el dígito más bajo,

¿Cuántos candidatos hay? Tenemos m dígitos divididos en k secuencias de al menos 1 dígito. Hay (m - k + 1) sobre (k - 1) formas de elegir la longitud de estas secuencias, que es aproximadamente (m - 1.5k + 2) ^ (k - 1) / (k - 1). Hay 2 o 4 opciones para el dígito más bajo, seis en total. Hay seis opciones para los otros dígitos, excepto 36/7 opciones para el dígito más alto; el total es (6/7) * 6 ^ k. Hay 2 ^ k formas de elegir si la longitud de una secuencia es par o impar; k + 1 de estos están excluidos porque ninguno o solo uno es impar; multiplicamos el número de opciones por (1 - (k + 1) / 2 ^ k), que es 1/4 cuando k = 2, 1/2 cuando k = 3, 11/16 cuando k = 4, etc. El número de los dígitos del conjunto {1, 4, 7} o {2, 5, 8} deben ser 3n + 2, por lo que el número de opciones se divide por 3.

Multiplicando todos estos números, el número de candidatos es

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (6/7) * 6^k * (1 - (k + 1) / 2^k) / 3

o

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k)

El candidato en sí y los k números que se crean al eliminar un dígito deben ser primos. La probabilidad de que un número entero aleatorio alrededor de N sea primo es aproximadamente 1 / ln N. La probabilidad de un número aleatorio de m dígitos es aproximadamente 1 / (m ln 10). Sin embargo, los números aquí no son aleatorios. Todos han sido elegidos para no ser divisibles por 2, 3 o 5. 8 de los 30 enteros consecutivos no son divisibles por 2, 3 o 5. Por lo tanto, la probabilidad de ser primo es (30/8) / (m ln 10) o aproximadamente 1.6286 / m.

El número esperado de soluciones es sobre

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k) * (1.6286 / m)^(k + 1)

o para grandes m aproximadamente

(1 - (1.5k - 2) / m)^(k - 1) / (k - 1)! * 0.465 * 9.772^k * (1 - (k + 1) / 2^k) / m^2

Para k = 2, 3, 4, ... obtenemos lo siguiente:

k = 2: 11.1 * (1 - 1/m) / m^2
k = 3: 108 * (1 - 2.5/m)^2 / m^2 
k = 4: 486 * (1 - 4/m)^3 / m^2


k = 10: 10,065 * (1 - 13/m)^9 / m^2

De k = 10 en adelante, el número se vuelve más pequeño nuevamente.