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.

Are we only allowed to use the above operators? Otherwise, modulo would make this way too easy. — Jwosty, Jun 23 '14 at 3:40
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

aditsu · Accepted Answer · 2014-06-23 07:41:02Z

31

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.

edited Jun 23 '14 at 7:41

answered Jun 23 '14 at 7:31

aditsu

22.3k3 gold badges49 silver badges98 bronze badges

1

\$\begingroup\$ +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. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 23 '14 at 7:56
\$\begingroup\$ @DigitalTrauma inequality operators are allowed, not banned \$\endgroup\$ – aditsu Jun 23 '14 at 17:59
\$\begingroup\$ @aditsu Oops! I need to read more carefully sometimes! +1 great answer! \$\endgroup\$ – Digital Trauma Jun 23 '14 at 18:01
\$\begingroup\$ @aditsu, sorry I'm noob, how exactly does this work? \$\endgroup\$ – Kartik_Koro Jun 24 '14 at 5:22
2

\$\begingroup\$ @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 \$\endgroup\$ – aditsu Jun 24 '14 at 5:56

| show 3 more comments

Greg Hewgill · Accepted Answer · 2014-06-23 08:39:58Z

17

Python, 3 2 tokens

Brute force solution, but it works.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Thanks to Howard for the 1 token reduction.

edited Jun 23 '14 at 8:39

answered Jun 23 '14 at 4:00

Greg Hewgill

2,6417 silver badges21 bronze badges

\$\begingroup\$ Wow! Your solution is probably the shortest (3 tokens), but I want to encourage other answers too. \$\endgroup\$ – qwr Jun 23 '14 at 4:05
11

\$\begingroup\$ There is even a 2 token solution: 0x9......>>x&1. \$\endgroup\$ – Howard Jun 23 '14 at 5:00

add a comment |

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ · Accepted Answer · 2014-06-23 06:58:05Z

6

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

edited Jun 23 '14 at 6:58

answered Jun 23 '14 at 6:52

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

5,67319 silver badges39 bronze badges

1

\$\begingroup\$ 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 \$\endgroup\$ – qwr Jun 23 '14 at 7:05
\$\begingroup\$ 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 \$\endgroup\$ – aditsu Jun 23 '14 at 7:11
\$\begingroup\$ Rats, even 43 = (2^7 + 1)/3 works, not sure how I missed it. Edited now. \$\endgroup\$ – aditsu Jun 23 '14 at 7:16

add a comment |

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ · Accepted Answer · 2014-06-23 06:29:16Z

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.

edited Jun 23 '14 at 6:29

answered Jun 23 '14 at 4:13

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

5,67319 silver badges39 bronze badges

\$\begingroup\$ +1: interestingly this works for n up to 512 (actually n = 590), but I'm not quite sure why. \$\endgroup\$ – Paul R Jun 23 '14 at 6:01
\$\begingroup\$ @PaulR: It won't work for bigger numbers due to carry (note that I used addition in the calculation). Also note the repeated lines. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 23 '14 at 6:06
\$\begingroup\$ Yes, I'm just not sure why it works for 9 bit values, since it only seems to be testing 8 bits? \$\endgroup\$ – Paul R Jun 23 '14 at 6:16
\$\begingroup\$ 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 \$\endgroup\$ – phuclv Jun 23 '14 at 6:50
1

\$\begingroup\$ 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 \$\endgroup\$ – phuclv Jun 23 '14 at 7:09

add a comment |

ɐɔıʇǝɥʇuʎs · Accepted Answer · 2014-06-23 08:15:17Z

2

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Or

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Or

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x

answered Jun 23 '14 at 8:15

ɐɔıʇǝɥʇuʎs

4,44914 silver badges24 bronze badges

2

\$\begingroup\$ Duplicate of Howard's comment \$\endgroup\$ – aditsu Jun 23 '14 at 8:31
\$\begingroup\$ @aditsu ... Great minds think alike? I swear I didn't see that before I posted this. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jun 23 '14 at 8:32

add a comment |

Tyilo · Accepted Answer · 2014-06-23 17:14:28Z

2

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.

answered Jun 23 '14 at 17:14

Tyilo

1,3729 silver badges16 bronze badges

\$\begingroup\$ Should be 4 tokens: =, *, |, == \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 25 '14 at 7:55
1

\$\begingroup\$ I don't think variable assignment counts as a token. \$\endgroup\$ – Tyilo Jun 26 '14 at 19:22

add a comment |

aditsu · Accepted Answer · 2014-06-23 07:17:49Z

1

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

edited Jun 23 '14 at 7:17

answered Jun 23 '14 at 6:50

aditsu

22.3k3 gold badges49 silver badges98 bronze badges

add a comment |

user15259user15259 · Accepted Answer · 2014-06-23 14:33:03Z

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

AndoDaan · Accepted Answer · 2014-06-23 22:02:13Z

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.

unclemeat · Accepted Answer · 2014-06-23 23:59:14Z

1

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.

answered Jun 23 '14 at 23:59

unclemeat

2,3021 gold badge12 silver badges21 bronze badges

\$\begingroup\$ Are loops allowed? \$\endgroup\$ – sergiol Jan 28 '17 at 13:57

add a comment |

Not that Charles · Accepted Answer · 2014-06-24 14:35:39Z

1

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

edited Jun 24 '14 at 14:35

answered Jun 23 '14 at 22:09

Not that Charles

1,9059 silver badges25 bronze badges

\$\begingroup\$ Wouldn't a token in the OP's sense be only one of the above listed in the question? \$\endgroup\$ – C5H8NNaO4 Jun 23 '14 at 22:25
\$\begingroup\$ @C5H8NNaO4 So what? 0? \$\endgroup\$ – Not that Charles Jun 24 '14 at 2:28
\$\begingroup\$ @C5H8NNaO4 maybe 4 for constants? \$\endgroup\$ – Not that Charles Jun 24 '14 at 3:15

add a comment |

Dylan Madisetti · Accepted Answer · 2014-07-06 19:57:04Z

1

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

edited Jul 6 '14 at 19:57

answered Jun 23 '14 at 15:24

Dylan Madisetti

3,3813 gold badges10 silver badges13 bronze badges

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

add a comment |

qwr · Accepted Answer · 2014-06-23 04:13:47Z

0

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

edited Jun 23 '14 at 4:13

answered Jun 23 '14 at 4:00

qwr

8,9195 gold badges29 silver badges58 bronze badges

add a comment |

William Barbosa · Accepted Answer · 2014-06-23 12:31:16Z

0

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)

answered Jun 23 '14 at 12:31

William Barbosa

3,2692 gold badges16 silver badges41 bronze badges

\$\begingroup\$ How did you come to that conclusion? I count about 37 tokens. \$\endgroup\$ – nyuszika7h Jun 23 '14 at 12:38
\$\begingroup\$ "A token is any of the above excluding constants and variables". How did you count 37? \$\endgroup\$ – William Barbosa Jun 23 '14 at 12:39
1

\$\begingroup\$ Oh, I see. The OP seems to disagree with the info page of atomic-code-golf. \$\endgroup\$ – nyuszika7h Jun 23 '14 at 12:42
\$\begingroup\$ Actually, now I'm not sure whether I'm right or not. My score would be 70+ according to the atomic code golf fiddle. \$\endgroup\$ – William Barbosa Jun 23 '14 at 12:46
1

\$\begingroup\$ 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. \$\endgroup\$ – aditsu Jun 23 '14 at 13:55

add a comment |

C5H8NNaO4 · Accepted Answer · 2014-06-23 21:40:44Z

0

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

edited Jun 23 '14 at 21:40

answered Jun 23 '14 at 21:34

C5H8NNaO4

1,3406 silver badges17 bronze badges

2

\$\begingroup\$ I have to say, I'm not sure what rules apply to this challenge. Are functioncalls and propertyaccesses allowed? \$\endgroup\$ – C5H8NNaO4 Jun 23 '14 at 21:47

add a comment |

sergiol · Accepted Answer · 2018-04-10 14:03:21Z

0

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!

answered Apr 10 '18 at 14:03

sergiol

3,0551 gold badge10 silver badges25 bronze badges

\$\begingroup\$ 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! \$\endgroup\$ – sergiol Apr 10 '18 at 14:38
\$\begingroup\$ Another fail:**87 bytes** proc T n {expr {[expr [join [split [expr [join [split $n ""] +]] ""] +]] in {0 3 6 9}}} Try it online! \$\endgroup\$ – sergiol Apr 10 '18 at 14:59

add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Determine if an integer is divisible by 3

16 Answers 16

C - 2 tokens

Python, 3 2 tokens

C - 5 4 (?) tokens

Reference

C - 15 (?) tokens

Python (2 tokens?)

JavaScript - 3 tokens

C - 4 tokens

bash – ???

Befunge 93 - 5 tokens

Batch - 7 Tokens

Ruby, 6(?) tokens

Python 0

Edit: Removed unnecessary lambda

Edit: Golfed further (117 chars) still no tokens

Killed direct access for python's nifty getitem Longer at 132 char

Python - 25 tokens

JavaScript - 3 Tokens

Tcl, 83 bytes

Not the answer you're looking for? Browse other questions tagged restricted-source atomic-code-golf or ask your own question.

Linked

Hot Network Questions

Determine if an integer is divisible by 3

16 Answers 16

C - 2 tokens

Python, 3 2 tokens

C - 5 4 (?) tokens

Reference

C - 15 (?) tokens

Python (2 tokens?)

JavaScript - 3 tokens

C - 4 tokens

bash – ???

Befunge 93 - 5 tokens

Batch - 7 Tokens

Ruby, 6(?) tokens

Python 0

Edit: Removed unnecessary lambda

Edit: Golfed further (117 chars) still no tokens

Killed direct access for python's nifty getitem Longer at 132 char

Python - 25 tokens

JavaScript - 3 Tokens

Tcl, 83 bytes

Not the answer you're looking for? Browse other questions tagged restricted-source atomic-code-golf or ask your own question.

Linked

Related

Hot Network Questions