Maybe you can look at in hexadecimal. Let's see. The proof for sum-of-numbers = divisibility by 3 goes as follows. 1 % 3 = 1 10 % 3 = 1 100 % 3 = 1 ...

Maybe you can look at in hexadecimal. Let's see. The proof for sum-of-numbers = divisibility by 3 goes as follows. 1 % 3 = 1 10 % 3 = 1 100 % 3 = 1 ... since things congruent modulo 3 are either both divisable by 3 or neither we can do this (because 10 and 3 are relatively prime): (a * 1000 + b * 100 + c * 10 + d) % 3 = (a + b + c + d) % 3 Hmmm 16 and 3 are relatively prime as well, and: 16 % 3 = 1 256 % 3 = 1 4096 % 3 = 1 ... Ergo the sum of hexadecimal digits follows the same rule in hexadecimal ! Hurray ! So : def divby3(x): s = 0 while x != 0: s += x & 15 x = x >> 4 if s >= 16: return divby3(s) return s in [0,3,6,9,12,15] Also, 5 works "like 3" in hexadecimal: def divby5(x): s = 0 while x != 0: s += x & 15 x = x >> 4 if s >= 16: return divby5(s) return s in [0,5,0xa,0xf]