Can All Subnumbers of a Number Be Prime?

In summary, there is no largest possible number such that all subnumbers are prime. There are a few candidates with 4 digits, but none with 3 or 2 digits.
  • #1
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,183
3,322
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
[tex]1,~2,~3,~4,~12,~23,~34,~123,~234,~1234[/tex]

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:
Physics news on Phys.org
  • #2
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.
 
  • #3
MarneMath said:
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 :woot:
 
  • #4
micromass said:
That answers question 1. I added 3 others :woot:

Oh, it doesn't actually. 73 is too small.
 
  • #5
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?
 
  • #6
MarneMath said:
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.
 
  • #7
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.
 
  • #8
ZVdP said:
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.
 
  • #9
Listing all possibilities, I count 9 numbers for Q2.
 
  • Like
Likes micromass
  • #10
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 ? :-p
 
  • #11
micromass said:
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.
 
  • #12
Pepper Mint said:
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 ? :-p
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.
 
  • #14
ZVdP said:
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!
 
  • #15
I've tested some candidates up to 7 digits and found none. I wondered if there would be an elegant proof.
 
  • #16
fresh_42 said:
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?
 
  • Like
Likes fresh_42
  • #17
ZVdP said:
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. :woot:
 

Related to Can All Subnumbers of a Number Be Prime?

1. What is the Prime Number Riddle?

The Prime Number Riddle is a mathematical puzzle that involves finding a specific sequence of prime numbers and using them to unlock a hidden code.

2. How do I solve the Prime Number Riddle?

To solve the Prime Number Riddle, you will need to identify the sequence of prime numbers given and use a mathematical operation to manipulate them and reveal the hidden code. This may require some trial and error and knowledge of basic math concepts.

3. What is the significance of prime numbers in this riddle?

Prime numbers are essential in this riddle because they have unique properties that make them challenging to identify and manipulate. They can only be divided by 1 and themselves, making them crucial in creating a secure code.

4. Is there a specific method for finding the prime numbers in this riddle?

There is no specific method for finding the prime numbers in this riddle, but there are some strategies you can use. These include using a prime number calculator, looking for patterns in the numbers, and using divisibility rules.

5. Can I use any sequence of prime numbers to solve the riddle?

No, you cannot use any sequence of prime numbers to solve the riddle. The sequence of prime numbers given in the riddle is carefully chosen to create a unique and challenging puzzle. Using a different sequence will not result in the correct solution.

Similar threads

  • Programming and Computer Science
Replies
28
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
32
Views
3K
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
847
  • General Math
Replies
7
Views
2K
  • General Discussion
2
Replies
43
Views
4K
Replies
1
Views
883
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
Back
Top