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

|cite|improve this question
$\endgroup$
  • 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$ – Semiclassical Jul 31 '14 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$ – becko Jul 31 '14 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$ – becko Jul 31 '14 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$ – becko Jul 31 '14 at 14:55
  • 5
    $\begingroup$ @Ryan No, they all have to have that form. $\endgroup$ – Thomas Andrews Jul 31 '14 at 14:57
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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ With $n+p$ prime (digit sum.) $\endgroup$ – Thomas Andrews Jul 31 '14 at 14:58
  • 2
    $\begingroup$ And $n+1$ prime (number of digits). $\endgroup$ – Semiclassical Jul 31 '14 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$ – Semiclassical Jul 31 '14 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$ – Thomas Andrews Jul 31 '14 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$ – Stella Biderman Jul 31 '14 at 15:23
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$ ...

|cite|improve this answer
$\endgroup$
6
$\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.

|cite|improve this answer
$\endgroup$
  • $\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$ – Semiclassical Jul 31 '14 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$ – Robert Israel Jul 31 '14 at 16:31
  • $\begingroup$ Hmm, that is pretty consistent (aside from obvious deviations for small lengths.) $\endgroup$ – Semiclassical Jul 31 '14 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 '14 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.