# Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: https://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime

A supreme prime has the following properties:

• the number itself is prime
• the number of digits is prime
• the sum of digits is prime
• the product of digits is prime

Are there finitely many "supreme" primes? Are there infinitely many? Currently the highest one found is ~$10^{72227}$

• I'd suspect that heuristic/probabilistic methods are likely to be more helpful than looking for proofs (e.g. estimate the probability of finding a supreme prime as the numbers get colossal.) Jul 31, 2014 at 14:45
• the product of digits is prime? That implies that the number has a very simple form: It is a sequence of 1's, with perhaps one and only one prime somewhere in the digits. Jul 31, 2014 at 14:46
• @Ryan I think they are all necessarily of this form. If 1 is excluded from the set of primes (as is usually done), the one prime in the sequence of digits is mandatory. Jul 31, 2014 at 14:54
• @Ryan That's what I'm saying. The digit sequence consists of 1's and one and only one prime. Otherwise the product of digits will be composite. Do we agree? Jul 31, 2014 at 14:55
• @Ryan No, they all have to have that form. Jul 31, 2014 at 14:57

This is not an answer, just a bit too long to be a comment. I didn't write the code for finding supreme primes, but I think it is simple.

All supreme primes $x$ are of the form:

$$x = \sum_{k=0}^n 10^k + 10^w\times(p-1) = \frac{10^{n+1} - 1}{9} + 10^w\times(p-1) \tag{1}$$

where $p$ is a prime number, and $0\le w \le n$. Therefore you only need to explore varying three parameters: $n,w,p$. Moreover, the search can be restricted so that $n + p$ (digit sum) and $n + 1$ (number of digits) are prime numbers (see comments). Defining $q = n +1$, we have to search pairs of prime numbers $p,q$ such that $p + q - 1$ is also a prime number (see comments). Having found such a pair, search for a $w$ in the range $0\le w\le q - 1$ such that $x$ in (1) is prime.

Just to clarify (there was some confusion in the comments), note that an $x$ of the form (1) may not be a supreme prime; indeed we still need to know that $x$ itself is prime.

• With $n+p$ prime (digit sum.) Jul 31, 2014 at 14:58
• And $n+1$ prime (number of digits). Jul 31, 2014 at 14:59
• Which suggests a nice search routine, actually: Pick two primes $p,q$ and check if $p+q-1$ is prime. If not, it can't produce a supreme prime. Jul 31, 2014 at 15:05
• It's not "the answer," @Ryan, it's just a way to narrow a search for more. Numbers io this form are not necessarily prime... Jul 31, 2014 at 15:07
• There's also the condition that $p\in\{2,3,5,7\}$. But since $n+1$ is prime, $n+2$ can't be, so the conditions on the parameters are: $p\in\{3,5,7\}$, $n+1$ prime, $n+p$ prime, and $w\leq n$. To whoever asked if it was open if there are infinitely many candidates, every twin prime pair generates a candidate, with $p=3$ and $n$ being one less than the smaller number in the pair. Jul 31, 2014 at 15:23

Heuristically, a random $n$-digit number has probability approximately $c/n$ of being prime, where $c$ is a positive constant. Since $p$ is $3$ or $5$ or $7$ and there are $n$ possible locations for it, there are $3n$ $n$-digit candidates. So the expected number of primes of this form among the $n$-digit candidates should be approximately constant. This would indicate that there should be infinitely many supreme primes. Of course it is not a proof. It would be very surprising if this could be proven.

• We're definitely in the "almost certainly true but un-provable" domain. It does suggest an interesting Code Golf question: Numerically, does it hold true that the number of supreme primes of length $n$ is roughly constant? Jul 31, 2014 at 15:45
• The numbers of such primes of lengths from $1$ to $20$ are $3, 5, 4, 4, 5, 4, 4, 7, 5, 5, 6, 4, 3, 1, 2, 1, 3, 2, 4, 4$. There are $2$ of length $100$, $3$ of length $200$, $3$ of length $300$, $4$ of length $1000$. Jul 31, 2014 at 16:31
• Hmm, that is pretty consistent (aside from obvious deviations for small lengths.) Jul 31, 2014 at 16:32
• And then the number n of digits and the sum of digits (n + 2, n + 4, or n + 6) must be prime as well. So up to n digits we get about c n / log^2 n. Still infinitely many. Not harder to find; instead of checking length 200 you would check length 209, all ones plus a digit 3. Jul 31, 2014 at 16:47

Only some extended hints:

The numbers are necessarily of the form $N=\frac{10^n-1}9+a10^k$ with $0\le k<n$ and $a+1$ prime (i.e. $a\in\{1,2,4,6\}$) to meet the product criterion. Of course, $n$ must be prime to meet the length criterion. Next, the digit sum is $n+a$, which rules out $a=1$ except for small cases.

If $a=2$ we must have $n\equiv -1\pmod 6$. Then $N\equiv n-k \pmod 3$, so we need $k\not\equiv -1\pmod 3$. Also , $\frac{10^n-1}9\equiv 2\pmod 7$, ${}\equiv 9\pmod {13}$, ${}\equiv 11\pmod{37}$, which rules out another fraction $\frac 17$, $\frac 1{13}$, $\frac1{37}$, respectively, of possible $k$ values.

Similarly, if $a=4$ we must have $n\equiv 1\pmod 6$. Then $N\equiv n+k\pmod 3$, so we need $k\not\equiv -1\pmod 3$ again. The argumentation with the primes $7,13,37$ dividing $111111$ applies as well in a similar way.

More generally, for any (small) prime $p>5$ we can obtain restrictions for $n,k\pmod{p-1}$. This makes it easy to construct $N$ which has no small prime divisors (and of course fulfills the sum, product, and length criterion). There's still a long way to go to make $N$ prime, of course.

Heuristically, the chance of $N$ being prime is $\sim \frac1n$; and since we have $\sim n$ choices for $k$, we'd expect a certain more or less constant amount of supreme primes per $n$ ...