┌─────────────────────────────────────────────────────────────────────────┐
  │A BT number is divisible by 2 iff the sum of its digits is divisible by 2│
  └─────────────────────────────────────────────────────────────────────────┘

For example:

    bt 265      ⍝ BT representation of odd number
1 0 1 ¯1 1 1

    +/bt 265    ⍝ sum of digits is odd
3

Staying  within  the  BT  number  system, where 3 → 1 0, we can apply the rule a
second time to see whether 1 0 is divisible by 2: +/1 0 → 1. In general, repeat-
ed  summing of the digits of a BT number will result in ¯1, 0 or 1. We can disp-
lay  the  resulting  sequence  using  the function "trajectory" operator [traj].
See dfns.dws/notes.traj.

    )copy dfns traj

    +/∘bt traj 265          ⍝ odd number → 1
265 3 1

    +/∘bt traj 100          ⍝ even number → 0
100 2 0

    +/∘bt traj 5            ⍝ odd number → ¯1
5 ¯1

    +/∘bt traj ¯314159265   ⍝ odd number → ¯1
¯314159265 ¯7 ¯1

We can prove this by induction over the vector of BT digits.

The  assertion  clearly  holds  for  the three single digit BT numbers (¯1 0 1),
where the sum of the digits is the same as the number itself:

    ¯1  odd     (+/¯1 → ¯1)
     0  even    (+/ 0 →  0)
     1  odd     (+/ 1 →  1)

Now, suppose the property is true for a BT number with digits i j ··· k. We must
prove  that if the parity (divisibility by 2) of (i j ··· k) is p, then the par-
ity of (i j ··· k)+1 is ~p. In other words, we prove that adding 1 to a BT numb-
er changes the parity of the sum of its digits:

Any (positive or negative) BT number falls into one of three cases, depending on
its least significant digit:

i ··· j ¯1      (case ¯1)
i ··· j  0      (case  0)
i ... j  1      (case  1)

Adding  1 to a (case ¯1) number produces i ··· j 0, so the sum of its digits in-
creases by exactly 1, thus changing its parity.

Similarly,  adding  1 to a (case 0) number produces i ··· j 1, so the sum of its
digits also increases by exactly 1, thus changing its parity.

Adding  1  to a (case 1) number causes overflow into the next digit position and
produces  i ··· (j+1) ¯1. The least significant digit changes from 1 to ¯1, pro-
ducing  a  nett  increase of ¯2 to the sum of the digits and so no change in the
parity.  Now  i ··· (j+1)  is  the same as i ··· j + 1, so we can apply the same
argument recursively to these remaining digits.

Stictly  speaking, this sort of reductive proof holds only for "natural" or non-
negative  whole  numbers. However because of the symmetry of BT numbers with re-
pect to sign, it is clear that:

    parity(-n) → parity(digit_sum(-n))
               → parity(-digit_sum(n))      // negation rule for BT numbers.
               → parity(digit_sum(n))       // (2|⍵) = 2|-⍵
               → parity(n)
Q.E.D.

This  property of the BT number system is reminiscent of (and possibly derivable
from)  the property of "standard" multi-digit number systems: A base-n number is
divisible  by  n-1  if the sum of its digits is divisible by n-1. For example, a
decimal number is divisible by 9 if the sum of its digits is divisible by 9, and
a  hexadecimal number is divisible by 0xf, if the sum of its digits is divisible
by 0xf.

Back to: →bta←