How to check divisibility of a number not in base 10 without converting?

Let's say I have a number of base 3, 1211. How could I check this number is divisible by 2 without converting it back to base 10?

Update

The original problem is from TopCoder

The digits 3 and 9 share an interesting property. If you take any multiple of 3 and sum its digits, you get another multiple of 3. For example, 118*3 = 354 and 3+5+4 = 12, which is a multiple of 3. Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9. For example, 75*9 = 675 and 6+7+5 = 18, which is a multiple of 9. Call any digit for which this property holds interesting, except for 0 and 1, for which the property holds trivially. A digit that is interesting in one base is not necessarily interesting in another base. For example, 3 is interesting in base 10 but uninteresting in base 5. Given an int base, your task is to return all the interesting digits for that base in increasing order. To determine whether a particular digit is interesting or not, you need not consider all multiples of the digit. You can be certain that, if the property holds for all multiples of the digit with fewer than four digits, then it also holds for multiples with more digits. For example, in base 10, you would not need to consider any multiples greater than 999.

Notes

- When base is greater than 10, digits may have a numeric value greater than 9. Because integers are displayed in base 10 by default, do not be alarmed when such digits appear on your screen as more than one decimal digit. For example, one of the interesting digits in base 16 is 15.

Constraints

- base is between 3 and 30, inclusive.

This is my solution:

class InterestingDigits {
public:
    vector<int> digits( int base ) {
        vector<int> temp;
   开发者_如何学Go     for( int i = 2; i <= base; ++i )
            if( base % i == 1 )
                temp.push_back( i );
        return temp;
    }
};

The trick was well explained here : https://math.stackexchange.com/questions/17242/how-does-base-of-a-number-relate-to-modulos-of-its-each-individual-digit

Thanks,

Chan

---

If your number k is in base three, then you can write it as

k = a0 3^n + a1 3^{n-1} + a2 3^{n-2} + ... + an 3^0

where a0, a1, ..., an are the digits in the base-three representation.

To see if the number is divisible by two, you're interested in whether the number, modulo 2, is equal to zero. Well, k mod 2 is given by

k mod 2 = (a0 3^n + a1 3^{n-1} + a2 3^{n-2} + ... + an 3^0) mod 2
        = (a0 3^n) mod 2 + (a1 3^{n-1}) mod 2 + ... + an (3^0) mod 2
        = (a0 mod 2) (3^n mod 2) + ... + (an mod 2) (3^0 mod 2)

The trick here is that 3^i = 1 (mod 2), so this expression is

k mod 2 = (a0 mod 2) + (a1 mod 2) + ... + (an mod 2)

In other words, if you sum up the digits of the ternary representation and get that this value is divisible by two, then the number itself must be divisible by two. To make this even cooler, since the only ternary digits are 0, 1, and 2, this is equivalent to asking whether the number of 1s in the ternary representation is even!

More generally, though, if you have a number in base m, then that number is divisible by m - 1 iff the sum of the digits is divisible by m. This is why you can check if a number in base 10 is divisible by 9 by summing the digits and seeing if that value is divisible by nine.

---

You can always build a finite automaton for any base and any divisor:

Normally to compute the value n of a string of digits in base b you iterate over the digits and do

n = (n * b) + d

for each digit d.

Now if you are interested in divisibility you do this modulo m instead:

n = ((n * b) + d) % m

Here n can take at most m different values. Take these as states of a finite automaton, and compute the transitions depending on the digit d according to that formula. The accepting state is the one where the remainder is 0.

For your specific case we have

n == 0, d == 0: n = ((0 * 3) + 0) % 2 = 0
n == 0, d == 1: n = ((0 * 3) + 1) % 2 = 1
n == 0, d == 2: n = ((0 * 3) + 2) % 2 = 0
n == 1, d == 0: n = ((1 * 3) + 0) % 2 = 1
n == 1, d == 1: n = ((1 * 3) + 1) % 2 = 0
n == 1, d == 2: n = ((1 * 3) + 2) % 2 = 1

which shows that you can just sum the digits 1 modulo 2 and ignore any digits 0 or 2.

---

Add all the digits together (or even just count the ones) - if the answer is odd, the number is odd; if it's even, the nmber is even.

How does that work? Each digit from the number contributes 0, 1 or 2 times (1, 3, 9, 27, ...). A 0 or a 2 adds an even number, so no effect on the oddness/evenness (parity) of the number as a whole. A 1 adds one of the powers of 3, which is always odd, and so flips the parity). And we start from 0 (even). So by counting whether the number of flips is odd or even we can tell whether the number itself is.

---

I'm not sure on what CPU you have a number in base-3, but the normal way to do this is to perform a modulus/remainder operation.

if (n % 2 == 0) {
    // divisible by 2, so even
} else {
    // odd
}

How to implement the modulus operator is going to depend on how you're storing your base-3 number. The simplest to code will probably be to implement normal pencil-and-paper long division, and get the remainder from that.

    0 2 2 0
    _______
2 ⟌ 1 2 1 1 
    0
    ---
    1 2
    1 1
    -----
      1 1
      1 1
      -----
        0 1 <--- remainder = 1 (so odd)

(This works regardless of base, there are "tricks" for base-3 as others have mentioned)

---

Same as in base 10, for your example: 1. Find the multiple of 2 that's <= 1211, that's 1210 (see below how to achieve it) 2. Substract 1210 from 1211, you get 1 3. 1 is < 10, thus 1211 isn't divisible by 2

how to achieve 1210: 1. starts with 2 2. 2 + 2 = 11 3. 11 + 2 = 20 4. 20 + 2 = 22 5. 22 + 2 = 101 6. 101 + 2 = 110 7. 110 + 2 = 112 8. 112 + 2 = 121 9. 121 + 2 = 200 10. 200 + 2 = 202 ... // repeat until you get the biggest number <= 1211 it's basically the same as base 10 it's just the round up happens on 3 instead of 10.