Ad
nzimmtvs.WestwardLand968

Divisibility by 3 - No direct modulus

Version with no modulus or division operators at all.

Uses this fact:

Even powers of two are 3k - 1 (2^5 = 32 = 33 - 1, etc.) for some k
Odd powers of two are 3k + 1 (2^4 = 16 = 15 + 1, etc.) for some k

Any given binary number is a sum of powers of 2; some are odd powers and some are even powers.

10011 = 1 * (3a - 1) + 0 * (3b + 1) + 0 * (3c - 1) + 1 * (3d + 1) + 1 * (3e - 1) = (3a - 1) + (3c - 1) + (3d + 1) = 3(a+c+d) - 1

It stands to reason that this is not divisible by 3 (and 10011 = 19 which is not divisible by 3)

For any binary number, it is 3k + count_odd_bits - count_even_bits for some integer k. Thus, it is only divisible by 3 if count_odd_bits - count_even bits is divisible by three

Code
Diff
  • def divisibility_by_3(x):
    e, o = 0, 0
    while x > 0:
        e += x & 1
        o += (x >> 1) & 1
        x >>= 2
        if x == 0:
            x, e, o = abs(e - o), 0, 0
            if x == 1 or x == 2:
                return False
    return True
    • def divisibility_by_3(x):
    • list_of_values = [int(d) for d in str(x)]
    • summation = sum(list_of_values)
    • if summation % 3 == 0:
    • return True
    • else:
    • return False
    • e, o = 0, 0
    • while x > 0:
    • e += x & 1
    • o += (x >> 1) & 1
    • x >>= 2
    • if x == 0:
    • x, e, o = abs(e - o), 0, 0
    • if x == 1 or x == 2:
    • return False
    • return True