# 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? Feb 23, 2012 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 Feb 23, 2012 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). Feb 23, 2012 at 22:29
• Using some roundabout method of generating the number 13 for use is acceptable. How do you determine what is "roundabout enough"? Apr 17, 2014 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.. Apr 17, 2014 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. Sep 12, 2012 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. Apr 19, 2014 at 16:04
• Use inline if ?: to save a few chars. Apr 20, 2014 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. Apr 20, 2014 at 12:15 • @PetervanderHeijden: Thanks! – user19214 Apr 20, 2014 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) Apr 28, 2012 at 9:58
• the last two lines can be rewritten as Console.Write(s==(int)s?"Yes":"No") Apr 28, 2012 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! Feb 28, 2012 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) Feb 28, 2012 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. Feb 28, 2012 at 21:11 • Ah. I missed ELSEIF s > i. Good call. Feb 29, 2012 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. Feb 25, 2012 at 8:23 • I didn't get it right, my bad Feb 25, 2012 at 8:29 • Still not quite right: you get a multiplier of 0.9 for using mod but not div. Feb 27, 2012 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. Apr 17, 2014 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. # k2, 22 char * 0.8 = 17.6 Just as you can sum the digits of a base 10 number to tell if it is divisible by 9, so too can you tell if a number is divisible by 13 if repeatedly summing its digits gives 13. As a function returning a string: $noyes@12<(+/14_vs)/


14_vs expands the input into base 14, and then +/ sums up the "digits". Wrapping that up into (...)/ repeats the process until it produces no change, that is, the result is less than 14. then we simply check whether our result is greater than 12 with 12<, and select the string "yes" or "no" ($noyes@) based on that result. $noyes@12<(+/14_vs)/ 39
"yes"
f:$noyes@12<(+/14_vs)/ f 38 "no" f' 167 168 169 170 171 ("no" "no" "yes" "no" "no") f 0 "no"  0 gives a "no" under this algorithm, but that's okay because the input is always greater than 0, according to the question. If we had to fix that, we would want to increment the number before and check for equality to 1, getting the 23 character $noyes@1=(+/14_vs)/1+.