# Determine if a number is divisible by 13 (without using 13 itself) [closed]

Your challenge, should you choose to accept it, is to create a function or a program that outputs "yes" if a given number is divisible by 13 and outputs "no" if it isn't.

Rules:
- You're not allowed to use the number 13 anywhere.
- No cop-out synonyms for 13 either (like using 15 - 2).
- Bonus points will be awarded for not using modulus, additional bonus for not using division.

Scoring:
- Your score will be the number of bytes in your code (whitespace not included) multiplied by your bonus.
- If you didn't use modulus, that bonus is 0.90; if you didn't use division, that bonus is 0.90.
- If you didn't use either, that bonus is 0.80.
- The lower your score, the better.

The input will always be an integer greater than 0 and less than 2^32.
Your output should be a simple "yes" or "no".

Clarifications:
- Using some roundabout method of generating the number 13 for use is acceptable. Simple arithmetic synonyms like (10 + 3) are not allowed.
- The function or program must literally output "yes" or "no" for if the given number is divisible by 13.
- As always, clever solutions are recommended, but not required.

• is 'true' or 'false' a valid output? – Blazer Feb 23 '12 at 19:09
• JavaScript (27 chars) function f(n){return "yes"}. This will return 'yes' for all the numbers that can be divided by 13 – ajax333221 Feb 23 '12 at 21:59
• "(whitespace not included)" always have been resulted in one of these two situation : a program encodes its content in whitespace, or a program written in Whitespace (programming language). – JiminP Feb 23 '12 at 22:29
• Using some roundabout method of generating the number 13 for use is acceptable. How do you determine what is "roundabout enough"? – Cruncher Apr 17 '14 at 15:57
• @Rusher To be honest, I didn't notice that it was 2 years old, it just recently became active. As for your suggestion, I'd rather not ninja-change as non-OP a question with 2 pages of answers.. – Cruncher Apr 17 '14 at 18:59

49 characters in Burlesque: 0\/r@{1\/.-<-12\/.-<-}{L[1.>}w!L[{"no" "yes"}\/!! (assuming the number to check is already on the stack. see here in action.)

Does not use division, does not use modulo. It actually does not use any arithmetic at all... just list manipulation.

• 48. The whitespace between "no" and "yes" is optional. If input comes from stdin and output is expected on stdout prepend ps and append sh leading to 52 characters. – mroman Sep 12 '12 at 12:27

# Mathematica 26*.9 ==23.4

If[2 n~Mod~26 == 0, "yes", "no"]


# Delphi XE3 114*0.8 = 91.2

function d(n:integer):string;var i:int8;begin d:='No';while n>0do for I:=0to 5do n:=n-2;if n=0then exit('Yes')end;


### Ungolfed

function d(n:integer):string;
var
i:int8;
begin
d:='No';
while n>0do
for I:=0to 5do
n:=n-2;
if n=0then exit('Yes')
end;


Does not use division, does not use mod, does not contain the number 13

# Python 2: 33 * 0.9 = 29.7 points

print['yes','no'][input()*2%26>0]


n*2%26 is equivalent to n%13. input()*2%26 will give a number from 0 to 12, and only numbers with 0 should print yes. To solve that, we add >0. 0>0 == False but all(map(lambda n:n>0,range(1, 13))) == True. False gets implicitly converted to 0, and True to 1, and the string in the appropriate index is printed.

# Python2.7, 57B

x=input()
while x>50:x=x//10+x%10*4
print x==x//10+x%10*4


No *2%26 bullshit trickery here. I think it would be more interesting if all non-zero multiples of 13 were forbidden.

Alternative (per wikipedia) algorithm in slightly more interesting code in 77B:

print not(sum([int(s)*[1,-3,-4,-1,3,4][i%6]for i,s in enumerate(x[::-1])]))


C# 98 chars (score 98*.80 = 76.8)

Shorter version:

int l="ThisIsLongNo?".Length;while(i>0)i-=l;if(i==0)Console.Write("yes");else Console.Write("no");


int length = "ThisIsLongNo?".Length;
while (input > 0)
input -= length;
if (input == 0)
Console.Write("yes");
else
Console.Write("no");

• This takes a ridiculously long time for input 4294967287. – primo Apr 19 '14 at 16:04
• Use inline if ?: to save a few chars. – Peter van der Heijden Apr 20 '14 at 12:12

# BASH, 57.6 (72*0.8) 58.4

The x file:

set - factor $1 17 shift while(($1<12))
do
shift
done
(($1>16)) && echo no || echo yes  The size: $ cat x | tr -d ' \t\n' | wc -c
72


The run:

$for i in 1 12 13 14 142 143 144 4294967295; do echo$i - $(bash x$i) ; done
1 - no
12 - no
13 - yes
14 - no
142 - no
143 - yes
144 - no
4294967295 - no

• Nice idea, if you use backticks instead of $( ... ) you have one char less. – Peter van der Heijden Apr 20 '14 at 12:15 • @PetervanderHeijden: Thanks! – user19214 Apr 20 '14 at 14:28 PHP ~84 characters.$n=26;// e.g. function m($n){$x=ord(4)/4;while($n>=$x){$n-=$x;}return $n|0;}echo m($n)?'no':'yes'; 

I actually prefer this method for getting 13 though (below in function form):  function a(){ return (int)((int)true.floor(pi())); } 

## Javascript, ES6, 74.4

Program 106*.8 = 84.8:

alert((f=n=>(n=n.toString(14).split("").reduce((r,x)=>+("0x"+x)+r,0))<14?n>12?"yes":"no":f(n))(+prompt()))


Function 93*.8 = 74.4:

f=n=>(n=n.toString(14).split("").reduce((r,x)=>+("0x"+x)+r,0))<14?alert(n>12?"yes":"no"):f(n)


The number in base 14 is divisible by 13 if and only if sum of its digits is divisible by 13.
Repeat summing digits until number will be 1 digit in base 14.
The answer is "yes" when this number is 13 or 0.
We can ignore 0 as it can be in result only when initial number is 0 (which is out of range by the rules), so it have to be greater than 12.

No explicit divisions and modulus, no any whitespaces, also no 13 in any form.

# Befunge, 27 non-whitespace bytes * 0.9 = 24.3

"_v#%\*4"#&<@,,<"no
>"sey",      ^


Multiplies the input by 4, then checks whether the result is divisible by 52. The 4 and the 52 both come from the 4 literal in the code, which is used for its ASCII value of 52 when read from left to right, then as the number 4 when read from right to left after the < reverses direction.

# JavaScript, Score 73 68*0.8=58.4 54.4

for(i=prompt();(i=(i&15)+3*(i>>4))>16;);alert(((i+3)&15)?"no":"yes")


99 * 0.9 = 89,1 (Used division but no mod)

var = float.Parse(Console.ReadLine())* 2 / 26;
if (s == (int)s) Console.Write("Yes");
else Console.Write("No");


This is in C#. Probably not a very good language to golf in. Feel free to improve it in different languages (or in c#) aslong as the method is the same.

• I think you meant var s at the beginning. Also, try to get rid of useless whitespace (ex: *2/26 instead of * 2 / 26) – Cristian Lupascu Apr 28 '12 at 9:58
• the last two lines can be rewritten as Console.Write(s==(int)s?"Yes":"No") – Cristian Lupascu Apr 28 '12 at 9:59

PYTHON 2.6

Now, this is not the shortest code, but the idea should be very easy to comprehend. Does not work with n = 0 but that can be fixed with if not n or s[-2:] == '.5' or '.' not in s.

def foo(n):
s = str(n/26.0)
return 'yes' if s[-2:] == '.5' or '.' not in s else 'no'


# C Language

include <stdio.h>

void main()
{
int number = 45;
int i=0;

while(number >=12)
{
for(i=0;i<=12;i++)
number -=1;
}

if (number==0)
printf("Divisible");
else
printf("Not Divisible");
}

• Hi Sim. Welcome to code golf! The idea behind Code-Golf challenges is to write as short of code as possible that solves the problem. This is done by using shorter variable names like n instead of number, or by cleverly combining loops or code sequences together. Also, the spec is defined to be 100% objective and ambiguous. You'll notice, for example, that the spec defines the output as yes or no. Please conform to the spec with your code and identify your score in the header to your post. Thanks, and welcome to the community! – mellamokb Feb 28 '12 at 20:56

# Ruby 34x0.8 = 27.2

p gets.to_i.gcd(0xD)==0?"yes":"no"


# QBasic - 164 CHARS

i = 9
s = 0
WHILE s < i
s=s+NOT-14
IF s=i THEN
? "YES"
ELSEIF s > i THEN
? "NO"
END IF
WEND


Set i to the number you want to test. Will Print Y if divisible by 13, otherwise, will print no. Updated to not use simple addition for to generate 13. Actual Non-Whitespace Characters is 66. No Division. No Modulus.

• Have you tested this for numbers larger than 13? It would appear that it would print out YES/NO many times.. I think you want your output to occur after the WEND. Also, you should be able to golf the output more using something like ? MID$("NO YES", (s=i)*3+1,3) – mellamokb Feb 28 '12 at 21:00 • works fine for numbers larger than 13. Will only print yes or no when it reaches the number, or if it finds that it goes past the number. After this, the loop exits. – Kibbee Feb 28 '12 at 21:11 • Ah. I missed ELSEIF s > i. Good call. – mellamokb Feb 29 '12 at 1:33 Ocaml let p n = if ((n>0) &&(n mod (40 mod 27)) = 0) then "yes" else "no"  13 = x+13 mod x. • Why *0.8? You're blatantly using mod. – Peter Taylor Feb 25 '12 at 8:23 • I didn't get it right, my bad – Joseph Elcid Feb 25 '12 at 8:29 • Still not quite right: you get a multiplier of 0.9 for using mod but not div. – Peter Taylor Feb 27 '12 at 9:01 ## Python, 108 x 0.8 = 86.4 def F(n):s=oct(n);return F(abs(sum(int(s[-1-i])*[1,-5,-1,5][i&3]for i in range(len(s)))))if n>7 else'yneos'[n>0::2]  Not going to win, but does an interesting trick by iterating over the octal digits of the number and reducing them modulo 13 (e.g. the "hundreds" digit is multiplied by -1 since 8^2==12==-1 mod 13). # Q, 30 * 0.9 = 27 {$[0=x mod "i"$"\r";yes;no]}  ## Perl, score: 25.6 24.8 OK, my program abuses perl's regex engine. It's a little bit obfuscated to look funnier. say+(q x x x <>)=~m ?^(\?: )+$??"yes":"no"


A shorter and "more readable" version would look like this:

say+(" "x<>)=~/^(             )+$/?"yes":"no"  I'm not quite sure how to count this. I ignore whitespace, so it goes down to these 32 31 countable characters: say+(""x<>)=~/^()+$/?"yes":"no"


which of course doesn't work, but the rules are like that. Because there's no modulus or division, I use factor 0.8. Please correct me if I'm wrong here. :)

# perl, 228.8 (286 chars)

This solution is long, but it's fun. It contains no cheapo, oddball representation of 13 whatsoever. It doesn't use division or modulus. It works on any integer of any length and runs in - O(log²n) time.

In all its glory:

@x=(1,10,9,12,3,4);sub a{$a=shift;$b=0;$c=0;for(0..length($a)-1){$c=0 if$c==6;$b+=$x[$c++]*substr$a,length($a)-$_-1,1}$b}sub b{my$c;$d=shift;do{$c=$d;$d=a$c}while($d!=$c);$x[1]=-3;$e=a$c;$x[1]=10;abs$e}sub c{@d=split//,sprintf"%02d",b$_[0];$d[0]*3==$d[1]}$\=$/;print c(abs<>)?"yes":"no"  Oh wait, was this not an obfuscation contest? Oops =) Anyway, here's how it works: First, we note that the ones digit is the same modulo 13 as the millions digit, and the tens digit is the same modulo 13 as the ten millions, etc. This yields the sequence (1,10,9,12,3,4). So, we sum (sequence[digit_number % 6])*digit_value. That gives us a smaller number that is the same modulo 13 as our input. We keep doing this until we fail to get a smaller number. Any number that fails to get smaller must be in the range 0-99. So now we take that number and feed it in to the same algorithm after changing the value for the tens digit from 10 to -3 (which is the same modulo 13). This yields a number in the range -27 to 9. If a number is a multiple of -13, it is a multiple of 13 as well, so we return the absolute value, yielding a number in the range 0-27. The multiples of 13 in the 0..27 range are 0, 13, and 26. 13 and 26 have the property that the tens digit * 3 == the ones digit. If 0 is represented as 00, it has this property as well. No other number in the range 0..27 has this property. Thus, we've determined if the input number is a multiple of 13 or not. ## JavaScript: 74*0.8 = 59.2 function a(b){alert(eval(String.fromCharCode(98,37,49,51))==0?'Yes':'No')}  Try it out here # PHP, Score: 64 - 20% = 51.2 $a=$argv[0];while($b-$i<$a){$b+=14;$i++;}echo($b-$i==$a?yes:no);  14 is added to $b in every cycle, and then it check if $b-$i (where $i is the n° of cycles) is greater of equal the input number. If it is equal, it is a multiple of 13, otherwise it's not. # Python- 38 chars I hope this doesn't count as a cop-out, but here it goes: print["no","yes"][input()%ord("\x0D")==0]  Explanation:  ord("\x0D") ---i.e. 13 input()%ord("\x0D")==0 ---the divisibility check ["no","yes"][input()%ord("\x0D")==0] ---the bool we get is used as an index print["no","yes"][input()%ord("\x0D")==0] ---and we print the result  # Julia, 30*0.9=27 f(x) = x%endof(" ")==0?"yes":"no"  • SE's markdown interpreter strips consecutive spaces. You can get around it by putting your code inside a code block, which also makes it a nice monospace font. – undergroundmonorail Apr 17 '14 at 18:06 # PowerShell: 65.6 Characters: 82 Multiplier: 0.8 (No modulus or division.) Total: 65.6 Golfed Code for($y=read-host;$x-lt$y;$x+='StackExchange'.length){}if($x-eq$y){"yes"}else{"no"}  Un-Golfed & Commented # Set up a for loop to add 13 (derived from the length of a string) to an initially null variable ($x) until it meets or exceeds a user-input value ($y). for($y=read-host;$x-lt$y;$x+='StackExchange'.length){} # After for loop exits, check final value of$x against $y. # If values match,$y is divisible by 13.
if($x-eq$y){"yes"}else{"no"}


If you're going to use a string length to get to 13, you may as well make the string interesting.

(May take a long time for very large values of $y.) # ~-~! - 38 * 0.9 (no modulus) = 34.2 '=~~~~,~~~+~:''=|*/','==*[|yes|]|no||:  ~-~! only supports integer division - thus, */',' (x/13*13)is equivalent to *-*;' (x-x%13). This checks whether x/13*13 == x and returns the appropriate string (yeah, it's a function, decimal console input is a huge pain) ## Pure Bash 40=50*0.8 File x: j=$1*2
while ((j>0))
do
((j-=26))
done && echo no || echo yes


Use as, e.g., bash x 13 or bash x 14. Character count:

$tr -d '[:space:]' < x | wc -c 50  Older was: File x: for ((j=$1*2;j>0;j-=26))
do
:
done
((j)) && echo no || echo yes


Use as, e.g., bash x 13 or bash x 14. Character count:

\$ tr -d '[:space:]' < x | wc -c
52


# C#, 74 * 0.8 = 59.2

void f(int n)
{
while (n >= 14)
n = (n >> 1) + 7 * (n & 1);

Console.Write(n <= 12 ? "no" : "yes");
}


Explanation

Write n as n = 2 a + b, i.e. a = n / 2 = (n >> 1) and b = n % 2 = (n & 1)

n          = 0    (mod 13)
2 a + b    = 0    (mod 13)
14 a + 7 b = 0    (mod 13)
a + 7 b    = 0    (mod 13)


So n is divisible by 13 if (and only if) a + 7 b is. Replace n by a + 7 b. Keep doing this until n is smaller than 14. n is now 13 if the starting value was divisble by 13 else n is some positive number smaller than 13.

# Javascript 30*.9=27

n % '\r'.charCodeAt() ? 'no' : 'yes'


Second approach 32*.9=28.8 (in case of the first one be invalid)

This code will only work in the 13th day of each month

n % new Date().getDay() ? 'no' : 'yes'

• No cop-out synonyms for 13 either (like using 15 - 2). I believe '\r'.charCodeAt() is a synonym for 13. – user12205 May 9 '14 at 12:31
• @ace: Let's wait for what others will say. It is as synonym as ' '.length. – Fabricio May 9 '14 at 12:34