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

Question

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.

Answer 1

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.

Answer 2

Mathematica 26*.9 ==23.4

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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");

Easy to read version:

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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")

Answer 12

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.

Answer 13

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'

Answer 14

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");
}

Answer 15

Ruby 34x0.8 = 27.2

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

Answer 16

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.

SCORE 53.49

Answer 17

Ocaml

let p n =
   if ((n>0) &&(n mod (40 mod 27)) = 0) then "yes" else "no"

13 = x+13 mod x.

Answer 18

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

Answer 19

Q, 30 * 0.9 = 27

{$[0=x mod "i"$"\r";`yes;`no]}

Answer 20

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

Answer 21

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.

Answer 22

JavaScript: 74*0.8 = 59.2

function a(b){alert(eval(String.fromCharCode(98,37,49,51))==0?'Yes':'No')}

Try it out here

Answer 23

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.

Answer 24

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

Answer 25

Julia, 30*0.9=27

f(x) = x%endof("            ")==0?"yes":"no"

Answer 26

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

Answer 27

~-~! - 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)

Answer 28

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

Answer 29

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.

Answer 30

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:

$`no`yes@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" ($`no`yes@) based on that result.

  $`no`yes@12<(+/14_vs)/ 39
"yes"
  f:$`no`yes@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 $`no`yes@1=(+/14_vs)/1+.