Determine if an integer is divisible by 3

Your goal is to determine if a number is divisible by 3 without using conditionals. The input will be an unsigned 8 bit number from 0 to 255. Creativity encouraged!

You are ONLY allowed to use

• Equality/Inequality (==, !=, >, <, >=, <=)

• Arithmetic (+, -, x)

• Logical Operators (! not, && and, || or)

• Bitwise Operators (~ not, & and, | or, ^ xor, <<, >>, >>> arithmetic and logical left and right shifts)

• Constants (it would be better if you kept these small)

• Variable assignment

Output 0 if false, 1 if true.

Standard atomic code-golf rules apply. If you have any questions please leave them in the comments. Example methods here. A token is any of the above excluding constants and variables.

• @GregHewgill My typo, it should be 8 bit number. – qwr Jun 23 '14 at 3:33
• Are we only allowed to use the above operators? Otherwise, modulo would make this way too easy. – Jwosty Jun 23 '14 at 3:40
• Also, how about table lookup? – Greg Hewgill Jun 23 '14 at 3:42
• Can you clarify what you mean by no conditionals? Is it limited to IF statements, or does it apply to things like loops as well? – Ruslan Jun 23 '14 at 3:50
• @Ruslan You are only allowed to use the above. – qwr Jun 23 '14 at 3:54

C - 2 tokens

int div3(int x) {
return x * 0xAAAAAAAB <= x;
}

Seems to work up to 231-1.

Credits to zalgo("nhahtdh") for the multiplicative inverse idea.

• +1. Was baffled a bit at how the <= works, and remembered that 0xAAAAAAAB is taken to be unsigned int type, thus the result of multiplication is unsigned. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 23 '14 at 7:56
• @DigitalTrauma inequality operators are allowed, not banned – aditsu Jun 23 '14 at 17:59
• @aditsu Oops! I need to read more carefully sometimes! +1 great answer! – Digital Trauma Jun 23 '14 at 18:01
• @aditsu, sorry I'm noob, how exactly does this work? – Kartik_Koro Jun 24 '14 at 5:22
• @Kartik_Koro 0xAAAAAAAB * 3 == 1 due to overflow, so for any int x, x * 0xAAAAAAAB * 3 == x. Also y * 3 has different values for different y, therefore y = x * 0xAAAAAAAB must be the only y such that y * 3 == x. If x is a multiple of 3, then y must be x/3, otherwise it must be working through overflow. A simple way to check is to compare y with x. Also see en.wikipedia.org/wiki/Modular_multiplicative_inverse – aditsu Jun 24 '14 at 5:56

Python, 3 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

• Wow! Your solution is probably the shortest (3 tokens), but I want to encourage other answers too. – qwr Jun 23 '14 at 4:05
• There is even a 2 token solution: 0x9......>>x&1. – Howard Jun 23 '14 at 5:00

C - 5 4 (?) tokens

int div3_m2(uint32_t n) {
return n == 3 * (n * 0xAAAAAAABull >> 33);
}

Works for any unsigned 32-bit number.

This code makes use of multiplicative inverse modulo 232 of a divisor to convert division operation into multiplication operation.

Edit

My solution (posted 2 minutes after) has the same spirit as aditsu's solution. Credit to him for the use of == that improves my solution by 1 token.

Reference

• This is incredible. I knew about magic numbers from the famous inverse squareroot trick, but I didn't know it could be used for an arbitrary divisor. This is Bull :P – qwr Jun 23 '14 at 7:05
• Yep, 0xAAAAAAAB = (2^33 + 1)/3 and 171 = (2^9 + 1)/3. I picked the smallest constant that does the trick. Hmm, actually it also seems to work with 86 = (2^8 + 2)/3 – aditsu Jun 23 '14 at 7:11
• Rats, even 43 = (2^7 + 1)/3 works, not sure how I missed it. Edited now. – aditsu Jun 23 '14 at 7:16

C - 15 (?) tokens

int div3_m1(unsigned int n) {
n = (n & 0xf) + (n >> 4);
n = (n & 0x3) + (n >> 2);
n = (n & 0x3) + (n >> 2);
return n == 0 || n == 3;
}

Since 4 ≡ 1 (mod 3), we have 4n ≡ 1 (mod 3). The digit summing rule is not limited to summing the digits, but also allows us to arbitrarily break the number into sequences of digits and sum all of them up while maintaining the congruency.

An example in base 10, divisor = 9:

1234 ≡ 12 + 34 ≡ 1 + 2 + 3 + 4 ≡ 123 + 4 ≡ 1 (mod 9)

All statements in the program makes use of this property. It can actually be simplified to a loop that runs the statement n = (n & 0x3) + (n >> 2); until n < 4, since the statement simply breaks the number in base-4 at the least significant digit and add the 2 parts up.

• +1: interestingly this works for n up to 512 (actually n = 590), but I'm not quite sure why. – Paul R Jun 23 '14 at 6:01
• @PaulR: It won't work for bigger numbers due to carry (note that I used addition in the calculation). Also note the repeated lines. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 23 '14 at 6:06
• Yes, I'm just not sure why it works for 9 bit values, since it only seems to be testing 8 bits? – Paul R Jun 23 '14 at 6:16
• for 9-bit numbers after the first addition it become at most 5 bits, after the first n = (n & 0x3) + (n >> 2); the result is reduced to 3 bits and the repetition caused it to remain only 2 bits stackoverflow.com/a/3421654/995714 – phuclv Jun 23 '14 at 6:50
• oh I've made a mistake. A 5-bit number + a 4-bit number can result in a 6-bit number. But if n <= 588 adding the top 4 bits and bottom 2 bits of that 6-bit number produce an only 4-bit sum. Again adding that results in a 2-bit number. 589 and 590 results in 3 bits in the last sum but incidentally they aren't divisible by 3 so the result is correct – phuclv Jun 23 '14 at 7:09

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x
• Duplicate of Howard's comment – aditsu Jun 23 '14 at 8:31
• @aditsu ... Great minds think alike? I swear I didn't see that before I posted this. – ɐɔıʇǝɥʇuʎs Jun 23 '14 at 8:32

JavaScript - 3 tokens

function div3(n) {
var a = n * 0.3333333333333333;
return (a | 0) == a;
}

This abuses the fact that using bitwise operators on a number truncates it to an integer in JavaScript.

C - 4 tokens

int div3(int x) {
return ((x * 43) >> 7) * 3 == x;
}

Works up to 383.

Previous version (bigger constants):

int div3(int x) {
return ((x * 171) >> 9) * 3 == x;
}

Works up to 1535

bash – ???

Not sure how to score this.

seq 0 85 | awk '{print $1 * 3}' | grep -w [number] | wc -l e.g.$ seq 0 85 | awk '{print $1 * 3}' | grep -w 11 | wc -l 0$ seq 0 85 | awk '{print $1 * 3}' | grep -w 12 | wc -l 1$seq 0 85 | awk '{print $1 * 3}' | grep -w 254 | wc -l 0$seq 0 85 | awk '{print $1 * 3}' | grep -w 255 | wc -l 1 Befunge 93 - 5 tokens Fixed - division removed. v @._1.@ \ 0 + 3 >&>3-:0\| ^ < Gets input, keeps subtracting 3 until it's smaller than 0, direct the pointer up ('|'), then adds 3. If the value is 0 then the pointer moves right ("1.@" outputs '1') else moves left ("@." outputs '0'). '@' terminates the program. Batch - 7 Tokens I think @echo off for /L %%a in (0,3,%1) do set a=%%a if %a%==%1 echo 1 Returns 1 if the given number (as stdin) is divisible by three. • Are loops allowed? – sergiol Jan 28 '17 at 13:57 Ruby, 6(?) tokens I'm really not sure how to count tokens. OP, can you score me? I think it's 6... 1, 0, 0, *, 255, x Note that the * is not integer multiplication. def div3(x) ([1,0,0]*255)[x] end • Wouldn't a token in the OP's sense be only one of the above listed in the question? – C5H8NNaO4 Jun 23 '14 at 22:25 • @C5H8NNaO4 So what? 0? – Not that Charles Jun 24 '14 at 2:28 • @C5H8NNaO4 maybe 4 for constants? – Not that Charles Jun 24 '14 at 3:15 Python 0 I posted eariler but I used conditionals. Here's to using no conditionals and no tokens, just keywords def g(x): return ([[lambda : g(sum(int(y) for y in list(str(x)))),lambda: 0][[False,True].index(x in[0,1,2,4,5,7,8])], lambda: 1][[False,True].index((lambda y: y in[3,6,9])(x))])() uses the trick that multiple of 3s have digits which add to 3 Edit: Removed unnecessary lambda def g(x):return([[lambda: g(sum(int(y) for y in list(str(x)))),lambda:0][[False,True].index(x in[0,1,2,4,5,7,8])], lambda:1][[False,True].index(x in[3,6,9])])() Edit: Golfed further (117 chars) still no tokens exec"g=x:(((:g(sum(int(y)for y in str(x)),:0)[x in[0,1,2,4,5,7,8]],:1)[x in[3,6,9]])()".replace('','lambda ') Killed direct access for python's nifty getitem Longer at 132 char exec"g={0}x:((({0}:g(sum(int(y)for y in str(x))),{0}:0{1}0,1,2,4,5,7,8]),{0}:1{1}3,6,9]))()".format('lambda ',').__getitem__(x in[') http://www.codeskulptor.org/#user34_uUl7SwOBJb_0.py Python - 25 tokens To get things started, I have a lengthy solution that is a implementation of one of the answers in the link in my first post. n is input. a = (n>>7)-((n&64)>>6)+((n&32)>>5)-((n&16)>>4)+((n&8)>>3)-((n&4)>>2)+((n&2)>>1)-(n&1) print(a==0 or a==3) or is equivalent to ||. JavaScript - 3 Tokens Test it on your browser's console: a = prompt().split(''); sum = 0; do { sum = a.reduce(function(p, c) { return parseInt(p) + parseInt(c); }); a = sum.toString().split(''); } while(a.length > 1) alert([3, 6, 9].indexOf(+sum) > -1) • How did you come to that conclusion? I count about 37 tokens. – nyuszika7h Jun 23 '14 at 12:38 • "A token is any of the above excluding constants and variables". How did you count 37? – William Barbosa Jun 23 '14 at 12:39 • Oh, I see. The OP seems to disagree with the info page of atomic-code-golf. – nyuszika7h Jun 23 '14 at 12:42 • Actually, now I'm not sure whether I'm right or not. My score would be 70+ according to the atomic code golf fiddle. – William Barbosa Jun 23 '14 at 12:46 • The problem is not about the number of tokens, but about what operations you're using. I don't think toString, parseInt, loops, arrays, etc. are allowed. – aditsu Jun 23 '14 at 13:55 JavaScript not sure about the token# function mod3 (i) { return {'undefined':'100','0':'0'}[[i]][i.toString (3).split('').pop ()]} or if the output for 0 is allowed to be 1; function mod3 (i) { return '100'[i.toString (3).split('').pop ()]} • I have to say, I'm not sure what rules apply to this challenge. Are functioncalls and propertyaccesses allowed? – C5H8NNaO4 Jun 23 '14 at 21:47 Tcl, 83 bytes proc T n {while \$n>9 {set n [expr [join [split $n ""] +]]};expr {$n in {0 3 6 9}}}

Try it online!

• Failed outgolf: 96 bytes proc T n {set n [expr [join [split [expr [join [split $n ""] +]] ""] +]];expr {$n in {0 3 6 9}}} Try it online! – sergiol Apr 10 '18 at 14:38
• Another fail:**87 bytes** proc T n {expr {[expr [join [split [expr [join [split \$n ""] +]] ""] +]] in {0 3 6 9}}} Try it online! – sergiol Apr 10 '18 at 14:59

protected by Community♦Jun 24 '14 at 1:02

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?