Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
@GregHewgill My typo, it should be 8 bit number. –  qwr Jun 23 at 3:33
2  
Are we only allowed to use the above operators? Otherwise, modulo would make this way too easy. –  Jwosty Jun 23 at 3:40
    
Also, how about table lookup? –  Greg Hewgill Jun 23 at 3:42
    
@Jwosty you are only allowed to use those, but I will take suggestions. –  qwr Jun 23 at 3:44
3  
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 at 3:50

15 Answers 15

up vote 27 down vote accepted

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.

share|improve this answer
    
+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̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 23 at 7:56
    
@DigitalTrauma inequality operators are allowed, not banned –  aditsu Jun 23 at 17:59
    
@aditsu Oops! I need to read more carefully sometimes! +1 great answer! –  DigitalTrauma Jun 23 at 18:01
    
@aditsu, sorry I'm noob, how exactly does this work? –  Kartik_Koro Jun 24 at 5:22
1  
@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 at 5:56

Python, 3 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

share|improve this answer
    
Wow! Your solution is probably the shortest (3 tokens), but I want to encourage other answers too. –  qwr Jun 23 at 4:05
10  
There is even a 2 token solution: 0x9......>>x&1. –  Howard Jun 23 at 5:00
2  
+1 for abusive use of arbitrary precision arithmetic –  James_pic Jun 23 at 8:37

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.

share|improve this answer
    
+1: interestingly this works for n up to 512 (actually n = 590), but I'm not quite sure why. –  Paul R Jun 23 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̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 23 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 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 –  Lưu Vĩnh Phúc Jun 23 at 6:50
1  
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 –  Lưu Vĩnh Phúc Jun 23 at 7:09

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

share|improve this answer
    
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 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 at 7:11
    
Rats, even 43 = (2^7 + 1)/3 works, not sure how I missed it. Edited now. –  aditsu Jun 23 at 7:16

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.

share|improve this answer
    
Should be 4 tokens: =, *, |, == –  n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 25 at 7:55
    
I don't think variable assignment counts as a token. –  Tyilo Jun 26 at 19:22

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

share|improve this answer

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

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

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
share|improve this answer

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.

share|improve this answer

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
share|improve this answer
    
Wouldn't a token in the OP's sense be only one of the above listed in the question? –  C5H8NNaO4 Jun 23 at 22:25
    
@C5H8NNaO4 So what? 0? –  Charles Jun 24 at 2:28
    
@C5H8NNaO4 maybe 4 for constants? –  Charles Jun 24 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

share|improve this answer
    
Array access [] is not allowed, though. –  n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 25 at 7:56
    
It is? After these rules, codegolf.stackexchange.com/tags/atomic-code-golf/info –  Dylan Madisetti Jun 25 at 13:21
    
Well, the question doesn't use the rule in the tag wiki. The question has restriction on operations allowed. Note the word only. –  n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 25 at 14:43
    
@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Well it's a good thing python has a native attribute for that too –  Dylan Madisetti Jun 25 at 16:04

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

share|improve this answer

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)
share|improve this answer
    
How did you come to that conclusion? I count about 37 tokens. –  nyuszika7h Jun 23 at 12:38
    
"A token is any of the above excluding constants and variables". How did you count 37? –  William Barbosa Jun 23 at 12:39
1  
Oh, I see. The OP seems to disagree with the info page of atomic-code-golf. –  nyuszika7h Jun 23 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 at 12:46
1  
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 at 13:55

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 ()]}

share|improve this answer
2  
I have to say, I'm not sure what rules apply to this challenge. Are functioncalls and propertyaccesses allowed? –  C5H8NNaO4 Jun 23 at 21:47

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.

share|improve this answer

protected by Community Jun 24 at 1:02

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.