3 ms·
To check if a number is divisible by 3, you can sum the digits of your number. If the sum of the digits is divisible by 3, then so was the original number. (e.
by bloaf 13y ago
To check if a number is divisible by 3, you can sum the digits of your number. If the sum of the digits is divisible by 3, then so was the original number. (e.g. 5832 -> 5+8+3+2=18) Therefore, if you recursively sum the digits of your number until you get a single-digit number and that digit is 3, 6, or 9, then the original number was divisible by 3. (e.g. 5832 -> 18 -> 9 so 5832 is divisible by 3)
To check if a number is divisible by 5, just check if the last digit is 0 or 5.
- gamegoblin 13y agoI thought about this, but there isn't a super efficient way to extract the individual digits without modulus or division or casting to a string, unless I am missing something obvious.
- waps 13y agoMaybe 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]
- gamegoblin 13y agoAh, clever! But I think >> does constitute division!