Is there a palindrome prime $p>3$ that is also palindrome in base $\ 5\ $?

Question

A prime $\ p\ $ is called palindrome, if the digits in reverse order give the same prime. For bases $\ b=2,3,4\ $ , there are large examples of palindrome primes that are also palindrome in base $b$ , but for $\ b=5\ $, I know only the trivial primes $\ p=2\ $ and $\ p=3\ $.

Is there a palindrome prime $\ p>3\ $ that is also palindrome in base $\ 5\ $ ?

With this routine :

? z=5;for(a=1,10^10,u=digits(a);if(gcd(u[1],10)==1,for(b=0,9,n=a*10+b;forstep(k=l
ength(u),1,-1,n=n*10+u[k]);if(isprime(n)==1,v=digits(n,z);if(Vecrev(v)==v,print(
n))))))

we can check whether a solution with $\ 21\ $ digits or less exists.

Brute force easily reveals that no prime below $\ 11\ $ does the job, so we can assume that the number of digits is odd and start with $\ 101\ $.

The program generates the palindromes and checks whether there is a solution.

I ran the program with limit $\ 10^8\ $ with no result, so a solution must have more than $\ 17\ $ digits.

Answer 1

You're looking for a number $n$ which fits three criteria:

1. $n$ is a palindrome in base $10$
2. $n$ is a palindrome in base $5$
3. $n$ is a prime

I start with a heuristic analysis of the situation.

---

A number which in base $b$ is a palindrome with $d$ digits is divisible by $b+1$ if $d$ is even. Therefore we can consider as a first filter the criteria:

1. $n$ has an odd number of digits in base $10$
2. $n$ has an odd number of digits in base $5$
3. $n$ is a palindrome in base $10$
4. $n$ is a palindrome in base $5$

That is already a very tough filter: up to $10^{17}$ only $47$ numbers pass it:

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

We can filter out a number of those by eye as being non-primes. So let's add a fifth criterion to the filter:

1. $n$ is odd
2. $n$ has an odd number of digits in base $10$
3. $n$ has an odd number of digits in base $5$
4. $n$ is a palindrome in base $10$
5. $n$ is a palindrome in base $5$

It's easy to enumerate intervals satisfying the first three criteria. We can then estimate for each of those intervals the probability of satisfying the 4th and 5th criteria and the probability of being prime ($\approx \frac{2}{\ln n}$ because of the first criterion).

But the pair of bases here is special, and so the probability of being palindrome in the two bases is definitely not independent. Specifically, each least significant digit in base $5$ corresponds to two possible least significant digits in base $10$. So we can take that into account and discard large intervals of integers.

Taking all this into account, ignoring single-digit numbers, and summing the total estimated primes we cross the threshold of one estimated prime in the range $(4\times 5^{12},10^{9})$, the threshold of two estimated primes in the range $(10^{14}, 2\times 5^{20})$, and the threshold of three estimated primes in the range $(2\times 5^{38} - 8\times 10^{26})$. Check my calculations here.

Conclusion: there probably are primes meeting the criteria, but they're looking to be rare.

---

To search, I think the best approach is to extend the idea that each least significant digit in base $5$ corresponds to two possible least significant digits in base $10$. More generally, any $d$-digit suffix in base $10$ corresponds to a $d$-digit suffix in base $5$, and since the reverse of the suffix gives you the prefix we can do progressive refinement of intervals.

I used the following C# code to generate odd odd-length double-palindromes and then performed primality testing separately:

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

After 4121 seconds it found the following number, which is the first to check out as prime:

$$7278175677249196711781595411145951871176919427765718727$$