# Origins of the conjecture on the existence of infinitely many palindromic primes

A palindromic prime with respect to a base $b \geq 2$ is a prime number such that, when you reverse its sequence of digits in base $b$, you get the same prime. For example in base 10, the prime 16661 is palindromic. See the wiki here for more:

https://en.wikipedia.org/wiki/Palindromic_prime

It is a well-known conjecture that there are infinitely many of these in base 10 (but likely in every base). I tried online to find info on the origins of this conjecture but with no success. I couldn't even find in what century it was first talked about. Perhaps it's a folklore problem? Nevertheless there should at least be some first papers which mention it. Would you know anything about the origins of the conjecture or at least the century in which it first appears in a paper or correspondence between mathematicians? Thanks a lot.

Update: Several comments and answers point out heuristics for the conjecture and a recent paper. Would you also know of an old citable paper or book where the conjecture appears or at least something closely related is said about these primes?

• My guess: people simply looked at tables of primes and saw that there are many palindromic primes. – Mariano Suárez-Álvarez Oct 22 '16 at 18:32
• Alternatively, a fair number of integers are prime (for example, by the prime number theorem, the proportion of $k$-digit integers that are prime is about $\frac1{k\log 10}$), and there are lots of palindromic integers (the number of $k$-digit palindromes is about $10^{\lceil k/2\rceil}$). Since there's no obvious reason why an odd-length palindrome shouldn't be prime, we suspect that the proportion of $k$-digit palindromes that are prime (when $k$ is odd) should still be about $\frac1{k\log 10}$. And presumably numerical studies support this heuristic. – Greg Martin Oct 22 '16 at 18:55

It may be even true that infinite pyramids of palindromic primes can be constructed (the example is too long for a comment):

$$5 97579 389757983 3138975798313 15313897579831351 741531389757983135147 9074153138975798313514709 73907415313897579831351470937 907390741531389757983135147093709 3690739074153138975798313514709370963 38369073907415313897579831351470937096383 393836907390741531389757983135147093709638393 7039383690739074153138975798313514709370963839307 71703938369073907415313897579831351470937096383930717 347170393836907390741531389757983135147093709638393071743 9534717039383690739074153138975798313514709370963839307174359 93953471703938369073907415313897579831351470937096383930717435939 799395347170393836907390741531389757983135147093709638393071743593997 3679939534717039383690739074153138975798313514709370963839307174359399763 14367993953471703938369073907415313897579831351470937096383930717435939976341 761436799395347170393836907390741531389757983135147093709638393071743593997634167 1776143679939534717039383690739074153138975798313514709370963839307174359399763416771 70177614367993953471703938369073907415313897579831351470937096383930717435939976341677107$$

• Wow! Mind blowing :) – user152169 Oct 22 '16 at 20:16
• Yes, that is impressive! But I don't believe it can go on like that forever $-$ once you get beyond the point where significantly fewer than $1$ in $100$ numbers are prime, the odds start stacking up against you. – TonyK Oct 22 '16 at 20:23
• But it could be the case that in any base there are arbitrarily long pyramids of palindromic primes. – Per Manne Oct 23 '16 at 8:35
• @PerManne: That sounds likely as long as your pyramid does not involve adding the same number of digits at each step (4 in the above example). With that added constraint it sounds very unlikely, per TonyK's comment. – R.. Oct 23 '16 at 14:21
• @R.. I think you should be able to add the same number $d$ of digits at each step. For each $d$ there would be a maximal height of the pyramid, but any height could be reached by choosing $d$ large enough. – Per Manne Oct 23 '16 at 15:07

Let $N(x)$ and $P(x)$ respectively be the number of palindromes and the number of palindromic primes $\le x$. Banks, Hart and Sakata proved that $$P(x) \sim O\bigg(\frac{N(x)\ln\ln\ln x}{\ln x}\bigg).$$

In the same paper, the authors conjecture that based on their results that the set of palindromes should behave as “random” integers, thus one might expect that the asymptotic relation

$$P(x) = O\bigg(\frac{N(x)}{\ln x}\bigg)$$

For more details refer to the paper Banks, Hart, Sakata 2008, Almost all palindromes are composite.

Another simple heuristic argument is given by Anthony Quas in the comments of the Mathoverflow thread: https://mathoverflow.net/questions/79113/why-so-difficult-to-prove-infinitely-many-restricted-primes

In the interval $2^n$ to $2^{n+1}$ there are approximately $2^{n/2}$ palindromes. Prime number theorem says that the density of primes in this interval is about $1/n$ so we can expect to see about $c2^{n/2}/n$ palindromic primes in this range. Thus in general you can conjecture that the number of palindromic primes $\le x \sim \frac{\sqrt x}{\ln x}$.

• The linked Banks/Hart/Sakata paper doesn’t cite any earlier discussion of palindromic primes. This presumably can be taken as negative evidence — that the authors must have done some literature searching, but didn’t find anything. – Peter LeFanu Lumsdaine Oct 23 '16 at 9:34

One of your tags being math-history it is pertinent to mention a topic concerning a way to generate palindromic numbers whatever be prime or composed.

It seems, according to Jean-Paul Delahaye in his paper “Déconcertantes conjectures” that the origin of this theme is in “Palindrome in addition” of Charles Trigg (Mathematics Magazine, 1967. Vol. 40, pages 26-28) however Delahaye adds “mais peut-être est-elle plus ancienne?”.

Starting from a number $N$ written in base 10, we reverse the order of its digits and add to N the inverted number. By repeating several times if necessary the operation, typically found a palindromic number. Examples $$14+41=55\\1048+8401=9449\\1723+3271=4994$$ You not always quickly get this way a palindrome and for example starting from $N = 89$ you need twenty-four iterations to get the palindrome $$(1)\space89+98=187\\(2)\space187+781=968\\(3)\space968+869=1837\\..........\\..........\\(24)\space1801200002107+7012000021081=8813200023188$$ And the first number not giving a palindrome in a known finite number of iterations is $196$. The record till now (of Waden Van Landingham) with $7\cdot 10^8$ iterations without a palindrome appears, stopped at an integer having more than $3\cdot 10^8$ digits and all this has given place to the following

Conjecture: The number $196$ to undergo the rollover-add operation (i.e. the exposed way) never produce a palindrome.