┌─────────────────────────────────────────────────────────────────────────┐ │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←