# Logic Puzzle in Base 8

1. Sep 14, 2016

### PhotonSSBM

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

$abcdefg$

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)

Similarly:

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

and

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

and

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

and

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. Sep 14, 2016

### lewando

[deleted].

3. Sep 15, 2016

### PhotonSSBM

Bump, no takers???

4. Sep 16, 2016

### lewando

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.

5. Sep 16, 2016

### SammyS

Staff Emeritus
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
6. Sep 17, 2016

### PhotonSSBM

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.

7. Sep 18, 2016

### SammyS

Staff Emeritus
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.

Example:
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​
or
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.
.

8. Sep 24, 2016

### SammyS

Staff Emeritus
@PhotonSSBM ,

Have you found any solutions to this?

9. Sep 24, 2016

### PhotonSSBM

Yes! They're turned in though. I can post them when I get the assignment back.

Edit: too busy to reproduce them now.

10. Sep 24, 2016

### SammyS

Staff Emeritus
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