3 ms·
Using Euclid's algorithm (not Euler's) is certainly not the easiest way of checking for divisibility by 3 - a number is divisible by 3 if and only if it's sum o
by enedil 8y ago
Using Euclid's algorithm (not Euler's) is certainly not the easiest way of checking for divisibility by 3 - a number is divisible by 3 if and only if it's sum of digits is divisible by 3. You can repeat the process until you have one digit.
- amelius 8y agoBut what if you start with a binary representation?
- firethief 8y agoDo it in quaternary. Add pairs of bits.
- avnerium 8y agoOr you can form the alternating sum of the bits, e.g. for 0b10011001 you calculate 1-0+0-1+1-0+0-1 = 0 which is divisible by three. (That's similar to the divisibility test by 11 of a number in base-10, or more generally testing if a number in base `b` is divisible by b+1)