16
$\begingroup$

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}$

$\endgroup$
12
  • 1
    $\begingroup$ 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.) $\endgroup$ Jul 31, 2014 at 14:45
  • 13
    $\begingroup$ 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. $\endgroup$
    – a06e
    Jul 31, 2014 at 14:46
  • 4
    $\begingroup$ @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. $\endgroup$
    – a06e
    Jul 31, 2014 at 14:54
  • 3
    $\begingroup$ @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? $\endgroup$
    – a06e
    Jul 31, 2014 at 14:55
  • 5
    $\begingroup$ @Ryan No, they all have to have that form. $\endgroup$ Jul 31, 2014 at 14:57

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
20
  • 2
    $\begingroup$ With $n+p$ prime (digit sum.) $\endgroup$ Jul 31, 2014 at 14:58
  • 2
    $\begingroup$ And $n+1$ prime (number of digits). $\endgroup$ Jul 31, 2014 at 14:59
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 31, 2014 at 15:05
  • 3
    $\begingroup$ 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... $\endgroup$ Jul 31, 2014 at 15:07
  • 7
    $\begingroup$ 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. $\endgroup$ Jul 31, 2014 at 15:23
7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jul 31, 2014 at 15:45
  • 2
    $\begingroup$ 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$. $\endgroup$ Jul 31, 2014 at 16:31
  • $\begingroup$ Hmm, that is pretty consistent (aside from obvious deviations for small lengths.) $\endgroup$ Jul 31, 2014 at 16:32
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Jul 31, 2014 at 16:47
6
$\begingroup$

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$ ...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .