# Prime number riddle

Staff Emeritus
Homework Helper
First a definition: given a natural number ##a_na_{n-1}...a_0##, a subnumber is any number of the form ##a_k a_{k-1}...a_{l+1}a_l## for some ##0\leq l \leq k \leq n##. I think an example will be the easiest way to illustrate this definition: the subnumbers of ##1234## are
$$1,~2,~3,~4,~12,~23,~34,~123,~234,~1234$$

Question 1: What is the largest possible number such that all subnumbers are prime? Is there such a largest possible number?

Some remarks: ##0## and ##1## are not prime. We work in the decimal system.

Question 2: How many numbers are there such that all subnumbers are prime.

Question 3: From now on we change the definitions accepting ##1## to also be a prime. What is now the largest number such that all subnumbers are prime? Is there a largest possible number now?

Question 4: How many numbers are there now?

Note: why allow ##1## to be prime? We have defined ##1## to be nonprime for good reasons, but there would also be good reasons to allow ##1## to be prime.

Last edited:

I'm pretty sure that there isn't such a beast beyond 2 digits. I'm also mildly sure that the largest 2 digit number would be 73.

Staff Emeritus
Homework Helper
I'm pretty sure that there isn't such a beast beyond 2 digits. I'm also mildly sure that the largest 2 digit number would be 73.

Staff Emeritus
Homework Helper

Oh, it doesn't actually. 73 is too small.

Really? The remaining prime numbers are 79,83,89,97 under 100. I'm I'm pretty sure it can't be either of those. So am I wrong about no such number can occur over 2 digits?

Staff Emeritus
Homework Helper
Really? The remaining prime numbers are 79,83,89,97 under 100. I'm I'm pretty sure it can't be either of those. So am I wrong about no such number can occur over 2 digits?

Yes, I have one with 3 digits.

ZVdP
I got 373.
The other possible 3 digit numbers that are larger would be
537
573
737
But they are all composite.

Going to 4 digits leads to 3737, which is composite.

Staff Emeritus
Homework Helper
I got 373.
The other possible 3 digit numbers that are larger would be
537
573
737
But they are all composite.

Right, that's what I got for question 1.

ZVdP
Listing all possibilities, I count 9 numbers for Q2.

micromass
Pepper Mint
I may misunderstand what you are asking but I think given a number of n digits, you will always have primes in its total number of ordered permutated partitions.
For example,
12345 = {1,2,3,4,5,12,13,14,15,123,124...}
1234567890={1,2,3,4,5,12,13,14,15,123,124...}
137={1,3,7,13,17,37,137}
so in order for one set to be containing all primes, I guess its component digits must be all primes or 1's ,or {1,3,5,7}. We can write a method to check against prime lists for numbers with such digits.
Am I wrong ?

ZVdP
Question 3: From now on we change the definitions accepting ##1## to also be a prime. What is now the largest number such that all subnumbers are prime? Is there a largest possible number now?
Would this be a 4 digit number?
3137 ?

First digit 1:
137->prime, 1371 composite, 1373 prime -> 13731 and 13737 both composite
173->prime, but both 1731 and 1737 are composite

First digit 2:
231 -> composite

First digit 3:
313->prime->3131 composite, 3137 prime->both 31371 and 31373 composite
317 -> prime, but 3173 and 3171 both composite
371->composite
373->prime, but 3731 composite

First digit 5:
513, 531 ->composite
517->composite
571->prime-> 5713 composite, 5717 prime, but 717 composite

First digit 7:
713,717,731,737 -> all composite
If it's correct, I'll leave the counting to someone else.

ZVdP
so in order for one set to be containing all primes, I guess its component digits must be all primes or 1's ,or {1,3,5,7}
Am I wrong ?
You can add 2 as well, but 2 and 5 can only occur as the leading digit.
You can eliminate extra numbers by considering that you can't have repeating digits, otherwise you would get a subnumber divisible by 11.

Mentor
2022 Award
Q3. At least one: 3137.

Staff Emeritus
Homework Helper
Would this be a 4 digit number?
3137 ?

First digit 1:
137->prime, 1371 composite, 1373 prime -> 13731 and 13737 both composite
173->prime, but both 1731 and 1737 are composite

First digit 2:
231 -> composite

First digit 3:
313->prime->3131 composite, 3137 prime->both 31371 and 31373 composite
317 -> prime, but 3173 and 3171 both composite
371->composite
373->prime, but 3731 composite

First digit 5:
513, 531 ->composite
517->composite
571->prime-> 5713 composite, 5717 prime, but 717 composite

First digit 7:
713,717,731,737 -> all composite
If it's correct, I'll leave the counting to someone else.
That is correct!

Mentor
2022 Award
I've tested some candidates up to 7 digits and found none. I wondered if there would be an elegant proof.

ZVdP
I've tested some candidates up to 7 digits and found none. I wondered if there would be an elegant proof.
If you didn't find any canditate with n digits, you cannot find a canditate with n+1 or more digits either.
I quickly tried all combinations by hand (there aren't that many possible combinations) until all paths ended at 4 digits, but perhaps micromass has a more elegant way of producing these numbers?

fresh_42
Mentor
2022 Award
If you didn't find any canditate with n digits, you cannot find a canditate with n+1 or more digits either.
I quickly tried all combinations by hand (there aren't that many possible combinations) until all paths ended at 4 digits, but perhaps micromass has a more elegant way of producing these numbers?
Of course, shame on me. I haven't thought about it, simply used my test program that was left over from the coding competition and watched whether my field becomes red or not.