Is there a quick parity test for integers expressed with odd radicies?

Question

For integers expressed with an odd base, is there an easy way to tell if the number is odd or even?

For an even base, if the ones digit is even, so is the integer. But this doesn't hold true for odd bases. For example, in base 3, 22 is even and 12 is odd.

One can always divide by two and see if there is a remainder. I've found (but don't have the mathematical background to formally prove) that, for odd bases, the parity of the sum of the digits is the parity of the number.

But is there any easier way to tell, just by looking? (Assume there are lots of digits.)

Answer 1

Given the simple facts that even+even=even, even+odd=odd, and odd+odd=even, we can see that if there are an even number of odd digits, the sum of the digits is even and if there is a odd number of odd digits, the sum of the digits is odd.

So, rather than summing the digits, you can simply count the number of odd digits, which has the same parity as the number itself.

Answer 2

Hint:

Each place value is odd (e.g. for base $3$, the place values are $1, 3, 9, 27,...$. The digit multiplies the place value. So if the digit is odd, the total value of that digit in that place value is odd; if the digit is even, the total value of that digit in that place value is even.

Answer 3

You are right that for odd bases the parity of the sum of digits is the parity of the number. Therefore, it it not possible to determine the parity of a number in an odd base without looking at all the digits, since you need to see all digits to know the parity of the sum. So you probably couldn't determine the parity of a number with "lots of digits" (say 1000 digits) at a glance.

Answer 4

Here's a hint.

Let's look at the first few even ternary numbers:

$2, 11, 20, 22, 101, 110, 112, 121, 200, 202, 211, 220, 222, 1001.$

And the first few odd ternary numbers:

$1, 10, 12, 21, 100, 102, 120, 122, 201, 210, 212, 221, 1000, 1002.$

I think that's the only way you can tell "just by looking." But in general that process is less than linear in $n$, where $n$ is the number.

Edit following KSmarts' answer:

An algorithm for checking odd/even by adding up the digits:

For each digit
    total = total + digit

If total is even
    "Number is even"
Else
    "Number is odd"

An algorithm for checking odd/even by adding up the number of odd digits:

For each digit
    If digit is odd
        oddDigits = oddDigits + 1

If oddDigits is odd
    "Number is odd"
Else
    "Number is even"

One may be faster than another for a particular implementation, but neither is easier than the other. You're still needing to examine every digit of the number.