1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Logic Puzzle in Base 8

  1. Sep 14, 2016 #1
    1. The problem statement, all variables and given/known data
    We call a seven digit number in base eight X, whose digits are given by


    No digits are zero, and none of them are the same. The following divisibility rules are true:

    (I)The number ##ab## is divisible by 2
    (II) The number ##abc## is divisible by 3
    (III)The number ##abcd## is divisible by 4
    (IV)The number ##abcde## is divisible by 5
    (V)The number ##abcdef## is divisible by 6
    (VI)X is divisible by 7

    Find all solutions that satisfy these constraints. No credit will be given to brute force or computational solutions.

    Hint: Start from proposition one and carefully reason your way through the digits.

    2. Relevant equations
    Divisibility of a number in base n by n-1 requires that the sum of the digits also be divisible by n-1

    There's probably some other rules I'm not privy to, and google hasn't produced.

    3. The attempt at a solution
    So I started from the beginning saying that a solution to ##ab## is just an even number with no zero or repeats. So:

    a can be (1,2,3,4,5,6,7) and b has to be (2,4,6)


    c, e, and g can also be (1,2,3,4,5,6,7) as long as there are no repeats


    f has to be an even number as well so f is (2,4,6)


    d has to be 4, similarly to how being divisible by 5 in base 10 means it ends in 5 or 0


    This means a, c, e, and g can only be (1,3,5,7)

    Also, the order of what a, c, e, and g, as well as b, and f are is irrelevant to proposition 6, since any order will be divisible by 7.

    I cannot figure out how to reduce this any further.
  2. jcsd
  3. Sep 14, 2016 #2


    User Avatar
    Homework Helper
    Gold Member

  4. Sep 15, 2016 #3
    Bump, no takers???
  5. Sep 16, 2016 #4


    User Avatar
    Homework Helper
    Gold Member

    Perhaps it is time to do some numerical work. For abc you will have less than 32 possibilities. How many of those are divisible by 3? Etc.
  6. Sep 16, 2016 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Actually, you are privy to some other divisibility tests. That's how you determined that b, d, and f are each even, and also deduced that f = 4.

    Unfortunately, the divisibility test for (n - 1) in base n representation isn't of any help, since in this case (n - 1) = 7 which is prime. (In decimal representation (base ten), the divisibility test for 9 also gives the divisibility test for 3, because 3 divides 9.)

    In base ten, there is a divisibility test for 11. There is a similar divisibility test for nine in base eight. Nine is written as 11[eight] . In base eight, this same test works for divisibility by 3.

    Do you know in general the basis for divisibility tests?
    Last edited: Sep 16, 2016
  7. Sep 17, 2016 #6
    I do not outside of the n-1 rule you mentioned. I know that you can derive the other divisibility rules from that one, but that's about it.
  8. Sep 18, 2016 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Use modular arithmetic. You can get pretty complicated, for a number with an arbitrary number of digits with an arbitrary base, or in this case, you can be somewhat more specific.

    The number written abc in octal is equal to a×82 + b×8 +c .
    You have abc is divisible by three, so that
    a×82 + b×8 +c ≡ 0 mod 3​
    8 ≡ 2 ≡ -1 mod 3
    82 ≡ 1 mod 3
    Therefore, in general, a×82 + b×8 +c ≡ (a -b + c) mod 3 .
    But specifically, since abc is divisible by 3, and b = 2 or 6:
    a + c - 2 = 3 m, some multiple of 3​
    a + c - 6 = 3 m', also some multiple of 3​
    It turns out that you divisibility

    Similarly (V) says the 6 divides abcdef, but as you observed this means that 2 and 3 each divide abcdef.
    You already have that divisibility by 2 gives f = 2 or 6.
    For divisibility by 3, we can extend what we did above. 8 ≡ -1 mod 3, so 82 ≡ (-1)2 = 1 mod 3, etc. Similar to taking -1 to whole number powers. 8odd ≡ -1 mod 3 and 8even ≡ 1 mod 3.

    Use that along with the fact that you know the sum, b + d + f = 12

    If 6 | abcdef, then abcdef ≡ a(-1) + b(1) + c(-1) + d(1) +e(-1) +f mod 3.

    This leads to b + d + f - (a + c + e) = 3n for some integer n.

    Rearranging gives a + c + e = 3n' , a different integer.

    That might not look all that helpful, but a, c, e, and g is each a different odd integer, their sum is 16. Only two of the four possible sums of three are divisible by 3. Therefore, you know a, c, and e must come from {1,3,5} or from {3,5,7) .

    Division of abcde by 5 is the complicated one.
    8 ≡ 3 ≡ -2 mod 5
    82 ≡ 32 ≡ -1 mod 5
    83 ≡33 ≡ 2 mod 5
    84 ≡(-1)2 ≡ 1 mod 5​
    You know that d = 4 and b = either 2 or 6. These are the only two digits multiplied by 2 or -2. That's helpful.

    Narrow the possibilities down, then include the division of abc by 3 .

    I get that there are 3 such seven digit base eight numbers.
  9. Sep 24, 2016 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    @PhotonSSBM ,

    Have you found any solutions to this?
  10. Sep 24, 2016 #9
    Yes! They're turned in though. I can post them when I get the assignment back.

    Edit: too busy to reproduce them now.
  11. Sep 24, 2016 #10


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Looking forward to that.

    I won't post anything more on details until we see a post with your results. However, I do have some comments I'll make now.

    If I were to give this exercise, I would be inclined to use slightly different numbering for the divisibility requirements. I would have:
    i) The octal number ##\ a\ ## is divisible by 1 .
    ii) The octal number ##\ ab\ ## is divisible by 2 .
    iii) The octal number ##\ abc\ ## is divisible by 3 .
    etc .​
    vi) The octal number ##\ abcdef\ ## is divisible by 6 .
    vii) The octal number ##\ abcdefg\ ## is divisible by 7 .​
    This simply gives a short-cut way to state the requirements. " The base eight number formed using the first n digits is divisible by n. " This has no significance in regard to obtaining a solution.

    Requirement i) is obviously true no mater which digit is used for ##\ a\ . ##
    Requirement vii) is true because the seven digits are all different and 1+ 6 = 2 + 5 = 3 + 4 = 7, so that 1+ 2+ 3+ 4+ 5+ 6+ 7 is a multiple of 7 .

    Those two divisibility requirements are no help whatsoever in solving the problem
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted