Yo soy un programador y diseñador de software. Definitivamente, no soy un matemático y mis matemáticas es bastante básica.
Uno de mis colegas me desafió a generar un capicúa primer número, al menos 1000 dígitos de largo y sólo utilizando los dígitos 1 y 7.
Escribí un 1 minuto a Java hack construido alrededor de un instintivo y defectuosa de la conjetura: vamos a tratar de construir un pequeño palindrómicas primer número de la primera y, a continuación, de forma aleatoria agregar el mismo dígito antes y después, con la esperanza de conseguir otro. Suena un poco infantil, pero todo aquello era sólo un juego.
Bien con mi sorpresa que "trabaja", o el tipo de. Obviamente, si usted toma un capicúa primer y anexar y anteponer un dígito (1, 3, 7 o 9), usted no consigue otra palindrómicas prime. Pero si sigues con la adición de dígitos al azar antes y después, parece que, finalmente, llegar a otro palindrómicas prime, y esto sucede... muy a menudo.
Con esto se tambalea y sin sentido del método, me las arreglé para ganar la apuesta y generar este número, en unos 10 minutos:
71771177771711117177717711111717117111711777117717117117777117711117177711177777171777717111771777717777111711717711177711177771771717117777177777777771777111177717177777771177177717777171177771771111717177777117717117711777177771177111711777711717711717771177771711117117171171771111771717777711177171171771717111117711111711177717171117777777111171777717777117117711177111711771777771111777171117711717711117777117111711177771777111777111777117777171711711717111771117777111777171111711111111717177171111117111771117177777771711717171171171117171171177111171777117717771177771171717111771111117777177771111117711171717117777117771771177717111177117117171117117117171711717777777171117711171111117177171711111111711117177711177771117711171711711717177771177711177711177717777111711171177771111771711771117177711117777717711711177111771171177771777717111177777771117171777111711111771111171717717117177111777771717711117717117171171111717777117771711771711777711711177117777177711771171771177777171711117717777117177771777177117777777171777111177717777777777177771171717717777111777111771711711177771777717711171777717177777111777171111771177771171171771177711711171171711111771777171111717777117717
Es capicúa, es 1199 dígitos de largo, y parece ser la mejor o, al menos, de Mathematica PrimeQ dice así, pero yo no prueba con un método determinista.
Este es el programa:
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class PalindromicPrimeFinder implements Runnable {
/**
* Test main
*/
public static void main(String[] args) {
int maxDepth = 50;
int testCertainty = 20;
Character[] digitsFinal = { '1', '7' }; // should be a subset of {1, 3, 7, 9}
Character[] digitsAll = { '1', '7' };
PrintWriter writer = new PrintWriter(System.out);
PalindromicPrimeFinder finder = new PalindromicPrimeFinder(
maxDepth, testCertainty, digitsFinal, digitsAll, writer);
finder.run();
}
private final Random random = new Random();
private final int maxDepth;
private final int testCertainty;
private final Character[] digitsFinal;
private final Character[] digitsAll;
private final PrintWriter writer;
/**
* Constructor.
*
* @param start The starting number
* @param maxDepth Max search depth
* @param testCertainty Certainty of primality test
* @param digitsFinal final digits (subset of {1, 3, 7, 9})
* @param digitsAll all digits
*/
public PalindromicPrimeFinder(int maxDepth,
int testCertainty, Character[] digitsFinal, Character[] digitsAll,
PrintWriter writer) {
this.maxDepth = maxDepth;
this.testCertainty = testCertainty;
this.digitsFinal = digitsFinal;
this.digitsAll = digitsAll;
this.writer = writer;
}
/**
* Run method
*/
@Override
public void run() {
String start = ""+digitsFinal[random.nextInt(digitsFinal.length)];
findPalindromicPrime(start, 0);
}
/**
* Worker recursive method
* @param number current number
* @param depth current depth
*/
private void findPalindromicPrime(String number, int depth) {
for (char digit : digitsFinal) {
String nextNumber = digit + number + digit;
if (new BigInteger(nextNumber).isProbablePrime(testCertainty)) {
writer.println("New prime [length=" + nextNumber.length()
+ "]: " + nextNumber + "\n");
writer.flush();
findPalindromicPrime(nextNumber, 0);
return;
}
}
if (depth > maxDepth) {
return;
}
List<Character> digitsAll_shuffled = new ArrayList<Character>(
Arrays.asList(digitsAll));
Collections.shuffle(digitsAll_shuffled, random);
for (char digit : digitsAll_shuffled) {
String nextNumber = digit + number + digit;
findPalindromicPrime(nextNumber, depth + 1);
}
}
}
En realidad, a veces mi programa puede generar números al igual que uno en un instante, otras veces sólo se produce un error o se bloquea. Si se cuelga por horas, usted tiene que interrumpir (CTRL+C).
Estoy interesado, de la vana curiosidaden saber por qué funciona (cuando lo hace) y si se usa un conocido de palindrómicas de los números primos. Soy bastante ignorante en matemáticas, pero yo soy una persona curiosa.
EDIT: puedes leer mi respuesta.
EDIT2: he creado un multi-threaded programa que se da por vencido después de un tiempo de espera. Echa un vistazo si tienes tiempo libre. :)
