Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime number riddle

  1. Jul 5, 2016 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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: Jul 5, 2016
  2. jcsd
  3. Jul 5, 2016 #2

    MarneMath

    User Avatar
    Education Advisor

    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.
     
  4. Jul 5, 2016 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That answers question 1. I added 3 others :woot:
     
  5. Jul 5, 2016 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Oh, it doesn't actually. 73 is too small.
     
  6. Jul 5, 2016 #5

    MarneMath

    User Avatar
    Education Advisor

    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?
     
  7. Jul 5, 2016 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, I have one with 3 digits.
     
  8. Jul 5, 2016 #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.
     
  9. Jul 5, 2016 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Right, that's what I got for question 1.
     
  10. Jul 5, 2016 #9
    Listing all possibilities, I count 9 numbers for Q2.
     
  11. Jul 5, 2016 #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
     
  12. Jul 5, 2016 #11
    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.
     
  13. Jul 5, 2016 #12
    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. Jul 5, 2016 #13

    fresh_42

    Staff: Mentor

    Q3. At least one: 3137.
     
  15. Jul 5, 2016 #14

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That is correct!
     
  16. Jul 5, 2016 #15

    fresh_42

    Staff: Mentor

    I've tested some candidates up to 7 digits and found none. I wondered if there would be an elegant proof.
     
  17. Jul 5, 2016 #16
    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?
     
  18. Jul 5, 2016 #17

    fresh_42

    Staff: Mentor

    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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prime number riddle
  1. Prime Numbers (Replies: 3)

  2. Prime numbers (Replies: 1)

  3. 2 missing number riddles (Replies: 19)

  4. A riddle (Replies: 23)

Loading...