Prime number riddle

  • Thread starter micromass
  • Start date
  • #1
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,316
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:

Answers and Replies

  • #2
MarneMath
Education Advisor
549
198
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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,316
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:
 
  • #5
MarneMath
Education Advisor
549
198
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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,316
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
ZVdP
14
5
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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,316
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
ZVdP
14
5
Listing all possibilities, I count 9 numbers for Q2.
 
  • #10
Pepper Mint
92
138
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
ZVdP
14
5
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
ZVdP
14
5
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
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,178
3,316
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
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,325
I've tested some candidates up to 7 digits and found none. I wondered if there would be an elegant proof.
 
  • #16
ZVdP
14
5
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?
 
  • #17
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,325
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:
 

Suggested for: Prime number riddle

  • Last Post
Replies
10
Views
400
  • Last Post
Replies
5
Views
1K
Replies
12
Views
402
Replies
7
Views
511
  • Last Post
2
Replies
43
Views
3K
  • Last Post
Replies
2
Views
2K
Replies
10
Views
460
  • Last Post
Replies
4
Views
875
  • Last Post
Replies
14
Views
2K
Replies
4
Views
1K
Top