Unlock the Prime Number Riddle

[micromass]

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.

 

[MarneMath]

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.

 

[micromass]

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.

That answers question 1. I added 3 others

 

[micromass]

That answers question 1. I added 3 others

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

 

[MarneMath]

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?

 

[micromass]

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.

 

[micromass]

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.

 

[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?

Spoiler

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.

 

[fresh_42]

Q3. At least one: 3137.

 

[micromass]

Would this be a 4 digit number?

Spoiler

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!

 

[fresh_42]

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]

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.