4
$\begingroup$

My question is most easily explained via an example: Consider the number $n=1967$. It contains the prime numbers $7$, $19$, $67$ and $967$ as all those are primes and you can find them in the decimal expansion of $1967$. In contrast, the part $196$ for example is not prime.

Given a fixed number of digits, $k$ say, what can be said about the maximal number of primes you can find in the decimal expansion of a $k$-digit number? I will call this number $m(k)$. The above example then teaches us that $m(4)\ge 4$.

Clearly, $m(k) \ge k$ e.g. by considering the number with digit $3$ $k$-times. The same argument shows that $m(k+1)\ge m(k)+1$. The maximal number of subnumbers for a $k$-digit number is $\frac{k(k+1)}{2}$, so trivially $m(k)\le \frac{k(k+1)}{2}$.

The first cases are: $$m(1)=1\ (e.g. n=3)\\ m(2)=3\ (e.g. n=23)\\ m(3)=6\ (e.g. n=373).$$

$\endgroup$
3
  • $\begingroup$ Do the prime numbers have to be distinct? $\endgroup$
    – Matti P.
    Commented May 16, 2018 at 13:20
  • $\begingroup$ @Matti, apparently not, because of what he said of considering digit $3\ k$ times $\endgroup$
    – Guillermo Mosse
    Commented May 16, 2018 at 13:46
  • $\begingroup$ @MattiP.: No, primes do not have to be distinct. $\endgroup$
    – Marcel
    Commented May 16, 2018 at 13:48

2 Answers 2

Reset to default
3
$\begingroup$

Don't know how about digit '$0$' using (for example, $307$: $3, 7$, $\color{gray}{07}$(???) and $307$).
Therefore all examples below are without this digit.

Few bounds with examples:

\begin{array}{|c|c|c|l|} \hline k & m(k) & \frac{k(k+1)}{2} & examples \\ \hline 4 & 9 & 10 & ... \\ 5 & 13 & 15 & 31373, 37337 \\ 6 & 17 & 21 & 337397, 373373, 373379 \\ 7 & 22 & 28 & 3733797 \\ 8 & 26 & 36 & 37337397 \\ 9 & 30 & 45 & 113733797, 233133733, 373373977, 733133733 \\ 10 & 35 & 55 & 2113733797, 3733133733, 7331337337 \\ 11 & \ge 40 & 66 & 17331337337, 37331337337, 37337937337, 52379337397, ... \\ 12 & \ge 45 & 78 & 337331237337, 361373371973, 373312373373, 373313373379, ... \\ 13 & \ge 51 & 91 & 1117331337337, 3373312373373 \\ 14 & \ge 56 & 105 & 11173313373373, 31379719337397, 32917333739397, 33733123733739 \\ 15 & \ge 62 & 120 & 329173337393739, 337331237337397 \\ 16 & \ge 68 & 136 & 3291733373937397 \\ 17 & \ge 74 & 153 & 31973373312373373 \\ 18 & \ge 80 & 171 & 331973373312373373 \\ 19 & \ge 85 & 190 & 1373363733123733739, 1731373973373937397, 2331127997337337973, ... \\ \ldots & \ldots & \ldots & \ldots \end{array}

For $k\ge 11$ the search was not exhaustive.

$\endgroup$
3
  • $\begingroup$ I guess one could argue that 07 should be counted as well as 7. Otherwise you would decrease the maximal number of subnumbers possible for every 0 within the number. $\endgroup$
    – Marcel
    Commented May 17, 2018 at 7:11
  • 1
    $\begingroup$ Interestingly, the lower bound you found still only grows linearly. $\endgroup$
    – Marcel
    Commented May 17, 2018 at 7:14
  • 1
    $\begingroup$ Probably, the given values are near the optimum, if not the optimum. $\endgroup$
    – Peter
    Commented May 17, 2018 at 10:41
0
$\begingroup$

I made a python script to check if the natural upper bound is always reached. The answer seems to be no:

Answer (for each $k$ from 1 to 5):

$[1, 3, 6, 9, 13]$

Natural upper bound (for each $k$ from 1 to 5):

$[1, 3, 6, 10, 15]$

$\endgroup$
3
  • $\begingroup$ script: pasted.co/4f687732 $\endgroup$
    – Guillermo Mosse
    Commented May 16, 2018 at 14:11
  • $\begingroup$ Is your scipt able to compute $m(k)$ for large (how large?) values of $k$? This would at least give an intuition of what to expect. $\endgroup$
    – Marcel
    Commented May 16, 2018 at 15:57
  • $\begingroup$ nah, it takes too long for $k \geq 7$. Maybe I could do a more intelligent algorithm (or explore random numbers)... $\endgroup$
    – Guillermo Mosse
    Commented May 16, 2018 at 20:44

You must log in to answer this question.

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