Estás buscando un número $n$ que se ajusta a tres criterios:
- $n$ es un palíndromo en base $10$
- $n$ es un palíndromo en base $5$
- $n$ es un primer
Voy a empezar con un análisis heurístico de la situación.
Un número que, en base a$b$ es un palíndromo con $d$ dígitos es divisible por $b+1$ si $d$ es incluso. Por lo tanto podemos considerar como un primer filtro de los criterios:
- $n$ tiene un número impar de dígitos en base $10$
- $n$ tiene un número impar de dígitos en base $5$
- $n$ es un palíndromo en base $10$
- $n$ es un palíndromo en base $5$
Que ya es muy difícil de filtro: a $10^{17}$ sólo $47$ números de pasar:
1 2 3 4
626 676 15751 18881
808656808 831333138 831868138 836131638
836181638 12114741121 12185058121 6105769675016
6643369633466 6648130318466 6694978794966 6982578752896
6989062609896 7730173710377 103191131191301 103824717428301
107745787547701 107793080397701 132412434214231 172102080201271
172849181948271 176071838170671 176265757562671 202304515403202
206725444527602 206903565309602 279119383911972 301537434735103
374476969674473 378573424375873 445336272633544 445384969483544
445389595983544 449488282884944 449933929339944 473643646346374
473696969696374 62596751915769526 67546323432364576
Podemos filtrar un número de los de ojo de no ser primos. Así que vamos a añadir un quinto criterio para el filtro:
- $n$ es impar
- $n$ tiene un número impar de dígitos en base $10$
- $n$ tiene un número impar de dígitos en base $5$
- $n$ es un palíndromo en base $10$
- $n$ es un palíndromo en base $5$
Es fácil enumerar los intervalos de la satisfacción de los tres primeros criterios. A continuación, podemos estimar para cada uno de los intervalos de la probabilidad de satisfacer la 4ª y 5ª criterios y la probabilidad de ser el primer ($\approx \frac{2}{\ln n}$ debido a que el primer criterio).
Pero el par de bases aquí es especial, y por lo que la probabilidad de ser palíndromo en las dos bases es definitivamente no es independiente. Específicamente, cada dígito menos significativo en base a$5$ corresponde a los dos dígitos menos significativos en base a$10$. Así que podemos tomar en cuenta y descartar grandes intervalos de números enteros.
Teniendo todo esto en cuenta, ignorando los números de un solo dígito, y sumar el total estimado de los primos de cruzar el umbral de un estimado de prime en el rango de $(4\times 5^{12},10^{9})$, el umbral de dos estimada de los números primos en el rango de $(10^{14}, 2\times 5^{20})$, y el límite de tres estimado de los números primos en el rango de $(2\times 5^{38} - 8\times 10^{26})$. Comprobar mis cálculos aquí.
Conclusión: probablemente hay primos que cumplen los criterios, pero que están mirando raro.
Buscar, creo que el mejor enfoque es el de extender la idea de que cada dígito menos significativo en base a$5$ corresponde a los dos dígitos menos significativos en base a$10$. De manera más general, cualquier $d$dígitos sufijo en base $10$ corresponde a un $d$dígitos sufijo en base $5$, y desde el reverso del sufijo le da el prefijo podemos hacer progresivo refinamiento de los intervalos.
He utilizado el siguiente código en C# para generar impar de longitud impar doble-palíndromos y, a continuación, realiza las pruebas de primalidad por separado:
using System;
using System.Collections.Generic;
using System.Numerics;
namespace Sandbox.DoublePalindromes
{
// https://math.stackexchange.com/q/3209975
class DoublePalindromeSearcher
{
private static DateTime _Start;
public static void Main()
{
_Start = DateTime.UtcNow;
Search(Base5(), Base10());
}
private static void Search(IEnumerable<PalindromeInterval> base5, IEnumerable<PalindromeInterval> base10)
{
var fives = base5.GetEnumerator();
var tens = base10.GetEnumerator();
if (!fives.MoveNext()) return;
if (!tens.MoveNext()) return;
while (true)
{
System.Diagnostics.Debug.Assert(tens.Current.AffixLength == fives.Current.AffixLength);
if (fives.Current.Overlaps(tens.Current) && (tens.Current.Suffix % BigInteger.Pow(5, fives.Current.AffixLength) == fives.Current.Suffix))
{
if (tens.Current.Upper == tens.Current.Lower + 1)
{
if (IsPalindrome(tens.Current.Lower, 5)) Console.WriteLine(tens.Current.Lower + " " + (DateTime.UtcNow - _Start).TotalSeconds);
}
else Search(fives.Current.Subdivide(), tens.Current.Subdivide());
}
var lowerUpper = BigInteger.Min(fives.Current.Upper, tens.Current.Upper);
if (fives.Current.Upper == lowerUpper && !fives.MoveNext()) return;
if (tens.Current.Upper == lowerUpper && !tens.MoveNext()) return;
}
}
private static bool IsPalindrome(BigInteger n, BigInteger b)
{
var digits = new List<BigInteger>();
while (n > 0)
{
digits.Add(n % b);
n /= b;
}
for (int i = 0, j = digits.Count - 1; i < j; i++, j--)
{
if (digits[i] != digits[j]) return false;
}
return true;
}
private static IEnumerable<PalindromeInterval> Base10()
{
// Odd number of digits, avoiding evens and 5.
var digits = new int[] { 1, 3, 7, 9 };
for (int length = 3; ; length += 2)
{
foreach (var prefix in digits)
{
yield return new PalindromeInterval(10, prefix, prefix, 1, length);
}
}
}
private static IEnumerable<PalindromeInterval> Base5()
{
// Odd number of digits.
for (int length = 3; ; length += 2)
{
for (int prefix = 1; prefix < 5; prefix++)
{
yield return new PalindromeInterval(5, prefix, prefix, 1, length);
}
}
}
}
class PalindromeInterval
{
public PalindromeInterval(BigInteger @base, BigInteger prefix, BigInteger suffix, int affixLength, int length)
{
if (2 * affixLength > length + 1) throw new ArgumentOutOfRangeException();
Base = @base;
Prefix = prefix;
Suffix = suffix;
AffixLength = affixLength;
Length = length;
if (2 * AffixLength == Length + 1)
{
// The last digit of the prefix overlaps the first digit of the affix
Lower = (Prefix - Prefix % Base) * BigInteger.Pow(Base, Length - AffixLength) + Suffix;
Upper = Lower + 1;
}
else
{
Lower = Prefix * BigInteger.Pow(Base, Length - AffixLength) + Suffix;
Upper = Lower + (BigInteger.Pow(Base, Length - 2 * AffixLength) - 1) * BigInteger.Pow(Base, AffixLength) + 1;
}
}
public BigInteger Base { get; }
public BigInteger Prefix { get; }
public BigInteger Suffix { get; }
public int AffixLength { get; }
public int Length { get; }
public BigInteger Lower { get; }
public BigInteger Upper { get; }
public bool Overlaps(PalindromeInterval that) => this.Lower <= that.Upper && that.Lower <= this.Upper;
public IEnumerable<PalindromeInterval> Subdivide()
{
if (2 * (AffixLength + 1) > Length + 1) yield break;
var offset = BigInteger.Pow(Base, AffixLength);
for (int newDigit = 0; newDigit < Base; newDigit++)
{
yield return new PalindromeInterval(Base, Prefix * Base + newDigit, Suffix + newDigit * offset, AffixLength + 1, Length);
}
}
public override string ToString() => $"[{Lower}, {Upper})";
}
}
Después de 4121 segundos encontrado el siguiente número, que es el primer comprobar como prime:
$$7278175677249196711781595411145951871176919427765718727$$
