Determine if an integer is divisible by 3

Question

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.

Answer 1

C - 2 tokens

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

Seems to work up to 2³¹-1.

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

Answer 2

Python, 3 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

Answer 3

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 2³² 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

• Labor of Division - ridiculousfish.com
• Hacker's Delight - Magic Number
• Wikipedia - Modular multiplicative inverse

Answer 4

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 4ⁿ ≡ 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.

Answer 5

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

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

Answer 12

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.

Answer 13

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!

Answer 14

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 ||.

Answer 15

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)

Answer 16

JavaScript
_{not sure about the token#}

function mod3 (i) { return {'undefined':'100','0':'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 ()]}