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

## closed as unclear what you're asking by Mego♦, mbomb007, Rɪᴋᴇʀ, GamrCorps, BlueAug 10 '16 at 6:48

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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

## Java (score 60.8 59.2)

void t(int n){System.out.print(Math.cos(.483321946706122*n)>.9?"yes":"no");}


Score: (76 - 2 whitespace) chars * 0.8 = 59.2

• Ingenious. I like it! – mellamokb Feb 24 '12 at 15:40
• println -> print? – Geobits Apr 18 '14 at 1:52
• @Geobits, true. – Peter Taylor Apr 18 '14 at 9:03

ASM - 16 bit x86 on WinXP command shell

executable - 55 bytes * 0.8 = 44

source - 288 characters * 0.8 = 230.4

The number 13 doesn't even appear in the assembled .com file.

Assemble using A86.

    mov si,82h
xor ax,ax
xor cx,cx
a:  imul cx,10
lodsb
sub al,48
jnc a
inc cx
h:  mov dl,a and 255
c:  loop g
sub dl,a and 255
jz e
mov dl,4
mov dh,1
mov ah,9
int 21h
ret
g:  inc dl
cmp dl,c and 255
jne c
jmp h
k:  db 'yes$no$'

• I understand that this solution is clever, but seeing as this is code-golf, shouldn't we be upvoting shortest solutions rather than cleverest solutions? – mellamokb Feb 28 '12 at 21:04
• @mellamokb: From what I've read on meta, some people think voting is a mark of appreciation for a clever / unusual solution. If we only voted on the shortest answer, there wouldn't be any point in having voting. I guess the 'tick' goes to the shortest code as a mark of ultimate kudos. Then again, a simple solution in golfscript will always be smaller than a really clever solution in C - so who deserves the votes? In the end, the votes aren't that important, it's about having fun. – Skizz Feb 29 '12 at 0:15
• rule: The input will always be an integer greater than 0 and less than 2^32. You can't use 16bit – Fabricio May 9 '14 at 12:23
• @Fabricio: All 16bit numbers are less than 2^32. :-) – Skizz May 9 '14 at 14:44
• lol.. you're right somehow. But you can't handle 2^32-1 =p – Fabricio May 9 '14 at 22:47

# Python 3.x: 54 * 0.8 = 43.2

It may be a cop-out to have a string of length 13, but here it goes:

print('no' if any((' ' * int(input())).split('             ')) else 'yes')


It works by building a string of n spaces (the choice of delimiter is arbitrary, but I chose space for obvious reasons), and splitting away 13-space substrings until you're left with a string containing n%13 spaces.

• +1. I like the split by 13 character whitespace. Moving it to Python 2 and using a technique from my answer takes it down to score of 35.2: print 'yneos'[any((' ' * input()).split(' '))::2] – Steven Rumbalski Feb 24 '12 at 1:33
• I was about to say: you could replace ' ' with ' '*6+' ' to save 5 chars - but then I found that spaces did not count at all... – kratenko May 9 '14 at 15:50

## GolfScript, 32 chars

~){.14base{+}*.@<}do('no''yes'if


I wanted to try something different from everyone else, so my solution calculates the base 14 digital root of the number, by repeatedly converting the number to base 14 and summing the digits until the result no longer gets any smaller. This is essentially the same as calculating the remainder modulo 13, except that the result will be in the range 1 to 13 instead of 0 to 12.

Since checking whether the digital root equals 13 would be difficult without using the number 13 itself (or some lame workaround like 12+1), what I actually do is I increment the input number by one before the loop and decrement the result afterwards. That way, the result for numbers divisible by 13 will in fact be zero, which is much easier to check for.

Here's a commented version of the program:

~              # evaluate the input, turning it from a string to a number
)              # increment by one
{              # start of do-loop
.          # make a copy of the previous number, so we can tell when we're done
14 base    # convert the number to base 14
{ + } *    # sum the digits
. @ <      # check if the new number is less than the previous number...
} do           # ...and repeat the loop if so
(              # decrement the result by one
'no' 'yes' if  # output 'no' if the result is non-zero, 'yes' if it's zero


This program will actually handle any non-negative integer inputs, since GolfScript uses bignum arithmetic. Of course, extremely large inputs may consume excessive time and/or memory.

The code does not use either modulos or division directly, although it does use GolfScipt's base conversion operator, which almost certainly does some division and remainder-taking internally. I'll leave it for GigaWatt to decide whether this qualifies me for the bonus or not.

• If only everyone would comment their golfscript code so well. Kudos – skibrianski Apr 16 '14 at 0:49

## C, 68 * 0.8 = 54.4

After 24 answers, no one came up with this obvious algorithm yet:

f(x){puts("no\0yes"+3*((x*330382100LL>>32)-(~-x*330382100LL>>32)));}

• I was waiting for someone to do an integer reciprocal multiply. Not only is it an elegant solution to the challenge, but it's a useful technique in it's own right as a performance optimization. – Sir_Lagsalot Feb 27 '12 at 17:46
• Is this still valid even though it's very non-standard? – oldrinb Sep 13 '12 at 4:28
• @oldrinb, I see no requirement for standard compliance in the question. In general, strict standard compliance is awfully annoying in code golf. – ugoren Sep 13 '12 at 14:20
• Could you explain why this works? – Vedaad Shakib Jul 16 '15 at 11:45
• @user2767189, it's a technique called "reciprocal multiply" - basically a way to implement division by X using multiplication by (2^K / X). In this case X is 13, and 330382100*13 is almost exactly 2^32. – ugoren Jul 16 '15 at 14:40

## JavaScript (27.9)

Current version (31 characters * 0.90 bonus = 27.9).

alert(prompt()*2%26?'no':'yes')


Edit 1: Forgo second bonus by using modulus to lower score considerably and avoid for loop. Also eliminate ~~ and save two chars (thanks @copy).

Older version (48 characters * 0.80 bonus = 38.4)

for(n=~~prompt()*2;n-=26>0;);alert(n?'no':'yes')​

• Multiply everything by two and use 26 instead... didn't see that coming. – Mr. Llama Feb 23 '12 at 22:25
• You can omit the ~~ assuming valid input; otherwise prompt()<<1 will work too. – copy Feb 23 '12 at 22:27
• Although I will admit it technically doesn't reach the limit of 2^32 anymore using this method.. – mellamokb Feb 24 '12 at 5:45
• In fact it does work beyond 2^32 since you dropped any bitwise operators now. – copy Feb 24 '12 at 17:56
• This is still using an arithmetic quickie to determine divisibility by 13, and there was a rule saying no arithmetic cop outs... – WallyWest Apr 17 '14 at 12:22

## BrainFuck

Score: 200 * 0.8 = 160

>++++++[>++++++++<-]>>,[<[-<+>>-<]<[->+<]>>>[->++++++++++<]>[-<+>]<<[->+<],]++++
+++++++++>[>+<-<-[>>>]>>[[-<<+>>]>>>]<<<<]>[<<<[-<++>]<++++++++++++++.+.>]<<[[-<
++++++<++++++++>>]<-----.<---.>------.>]


Reads froms stdin. Probably not the most clever solution, but getting anything that works in BF is nice. It's quite compact though.

• Any explanation on how it works? It seems like by default BrainFuck would get the full 0.8 bonus because it simply doesn't have division or modulus. – Mr. Llama Feb 23 '12 at 21:19
• @GigaWatt it calculates the modulus. – copy Feb 23 '12 at 21:27
• Aye, but what I meant was that it doesn't use the modulus operator (because it doesn't have one). Therefore it'll always get the bonus for not using it. Also, nice bio pic. – Mr. Llama Feb 23 '12 at 21:37
• @GigaWatt I didn't disagree with you, just answered your question. – copy Feb 23 '12 at 21:59

Scala (38 * 0.9 = 34.2)

Similar to 0xD(hex) or 015(oct).

ASCII value of CR is 13.

def t(n:Int)=if(n%'\r'==0)"yes"else"no"

• I wondered how long it'd be before I saw someone exploit ascii values. – Mr. Llama Feb 24 '12 at 19:25
• Can you add the score to your post please? Should be 38 * 0.9 = 34.2. – mellamokb Feb 28 '12 at 21:06

## Haskell, 28 * 0.8 = 22.4

f x|gcd 26x>2="yes"|1<3="no"


Python:

f=lambda n:1==pow(8,n,79)


E.g.

[i for i in range(100) if f(i)]


gives

[0, 13, 26, 39, 52, 65, 78, 91]

• now this one I like. however there needs to be a yes/no according to the challenge criteria, and you should post your score (25*.08 = 20) – Blazer Feb 24 '12 at 23:10
• f=lambda n:pow(8,n,79)-1 and "no" or "yes" fixes it, 43*0.8=34.4 – ugoren Feb 27 '12 at 15:54

## C, 54.4 == 68 * .8   80 * .8

char*f(c){char*s=" yes\0\rno";while(c&&*s++);return c>0?f(c-*s):++s;}

• Nice use of \r - I thought it's only good for Windows support. But why c>0 when c would do? – ugoren Feb 26 '12 at 22:20
• @ugoren: it wouldn't do, think about it. – ceased to turn counterclockwis Feb 26 '12 at 23:24
• You're right, I got confused somehow. I was thinking about numbers above 2^31, where >0 is no good. But instead of noticing that your function doesn't support them, I thought == is good. – ugoren Feb 27 '12 at 7:37

### ECMAScript 6, 25 × 0.9 = 22.5

Yeah, it's a boring way of getting 13.

n => n % '             '.length ? 'no' : 'yes'

• i was trying to figure out how your score was so low, then i realized the genius in using whitespace for your number... lol – mellamokb Feb 24 '12 at 15:32
• +1 for abusing the rules. If I stated them, it would be "not counting REMOVABLE whitespace". So is anyone going to give us a 0 byte solution? – ugoren Feb 27 '12 at 15:59
• @ugoren Wish granted – TuxCrafting Aug 6 '16 at 18:16

## APL ((21 - 1) × 0.8 = 16)

'yes' 'no'[1=⎕∨⌊⍟9*6]


⎕IO should be set to 0 for this to work properly in Dyalog APL. To generate 13, we take the floor (⌊) of the natural logarithm (⍟) of 9 to the power of 6 (9*6). After that, we find the GCD (∨) of our input (⎕) and 13, and we then test if that equals 1. This is used to index ([...]) the vector of answers.

If anyone wants to be pedantic about the mention of bytes in the scoring specification, the score for the UTF-8 encoded version of this is (29 - 1) × 0.8 = 22.4. :)

• I so want to be pedantic about bytes. – Steven Rumbalski Feb 26 '12 at 3:38
• Ohhhhhhhh snap you di-int. – Dillon Cower Feb 26 '12 at 4:19

## C, 88

Fibonacci trick.

f(n){return n<2?n:f(n-1)+f(n-2);}main(x){printf("%s",x%f(7)?"No":"Yes",scanf("%d",&x));}

• You're using 13 via f(7)... That's kinda bending the rules a bit... – WallyWest Apr 18 '14 at 2:21

## Perl - 44 × 0.8 = 35.2

#!perl -p
map$_+=4*chop,($_)x10;$_=chop^$_*3?'no':yes


Counting the shebang as one byte.

I'm a bit late to the game, but I thought I'd share the algorithm, as no other posts to this point have used it.

This works under the observation that if n is divisible by 13, then ⌊n/10⌋+n%10*4 is also divisible by 13. The values 13, 26 and 39 cycle onto themselves. All other multiples of 13 will eventually reach one of these values in no more than log10 n iterations.

In Other Bases

Admittedly, chop is a bit of a cop-out. With a base 10 representation, it's equivalent to divmod. But the algorithm works prefectly well in other bases, for example base 4, or 8.

Python style pseudo-code of the above algorithm (base 10):

def div13(n):
while n > 40:
q, r = n // 10, n % 10
n = q + 4*r
return n in [13, 26, 39]


In base 2:

def div13(n):
while n > 40:
q, r = n >> 1, n & 1
n = q + 7*r
return n in [13, 26, 39]


In base 4:

def div13(n):
while n > 40:
q, r = n >> 2, n & 3
n = q + 10*r
return n in [13, 26, 39]


In base 8:

def div13(n):
while n > 40:
q, r = n >> 3, n & 7
n = q + 5*r
return n in [13, 26, 39]


etc. Any base smaller than 13 works equally well.

## Javascript: 59*0.8 = 47.2 (?)

function r(n){
for(c=0;n>c;n-=12,c++);
return n==c?'yes':'no';
}


Including mellamokb's improvement (57*0.8 = 45.6):

function r(n){
for(c=0;n>c;n-=12,c++);
return n-c?'no':'yes'
}

• You can save two chars by changing return to return n-c?'no':'yes' and omitting the second semicolon. – mellamokb Feb 24 '12 at 15:39
• @mellamokb Good catch. Could probably improve further by writing it in Ruby, or something that allows more compact function definitions. – Supr Feb 24 '12 at 16:27
• There is also an accepted standard on CG to use prompt for input and alert for output, which makes the program interactive and saves a few chars. – mellamokb Feb 24 '12 at 22:01

Perl: (51-4 spaces)*0.9 = 42.3

say+<>%(scalar reverse int 40*atan2 1,1)?'no':'yes'


40*atan2(1,1) -> 31.41592 (PI*10)

# Perl (19.8)

21 bytes * .9

say2*<>%26?"no":"yes"


note: My first Perl program ever. Weakly typed is good for golf i guess.

• I've found that a good way to measure your knowledge of a language is to try and golf in it. Usually requires knowing edge cases. Also, your score is actually 23 * 0.90 (whitespace doesn't count). – Mr. Llama Feb 24 '12 at 19:10
• Thought I had accounted for the whitespace. Fixed now. Thanks for pointing that out. – Steven Rumbalski Feb 24 '12 at 19:18
• Wow. No love for Perl. Can't say I like it either. – Steven Rumbalski Feb 28 '12 at 17:55

in C (K&R): 47 * 0.8 = 37.6

f(i){for(;i>0;i-=__LINE__);puts(i?"no":"yes");}


EDIT1: okay removed all dependencies on external functions, the above will work as long as you put this line on the 13th line of the file! :) If __LINE__ is okay to be replaced by say 0xd then can save a further 5 characters (score: 33.6)

• If this needs to be on 13th line, you need to add 12 newlines to your code, and therefore, to your score: it becomes 59 * 0.8 = 47.2 – Vereos Apr 18 '14 at 9:45

## J - 22.4 = 28 * 0.8

Based on mxmul's clever cyclic method.

f=:<:{('yes',~12 3$'no ')$~]


Examples:

   f 13
yes
f 23
no
f 13*513
yes
f 123456789
no


# JavaScript (108 less 0 for whitespace) => 108, x 0.8 (no modulus, no division) = 86.4

b=b=>{a=z,a=a+"";return+a.slice(0,-1)+4*+a.slice(-1)};z=prompt();for(i=99;i--;)z=b();alert(b()-z?"no":"yes")

This method uses the following algorithm: 1. Take the last digit, multiply it by four, add it to the rest of the truncated number. 2. Repeat step 1 for 99 iterations... 3. Test it one more time using step 1, if the resulting number is itself, you've found a multiple of 13.

Previous update, removed var, and reversed logic at the alert to remove more chars by using subtraction-false conditional.

Technically, the end result is that you'll eventually reach a two digit number like 13, 26, or 39 which when run through step 1 again will give 13, 26, or 39 respectively. So testing for iteration 100 being the same will confirm the divisibility.

# Cheddar, 20 bytes (noncompeting)

### Score is 20 * 0.9 = 18

n->n*2%26?'no':'yes'


# Common Lisp (71 bytes * 0.8) = 56.8

Simple recursion, really.

(defun w(x)(if(> x 14)(w(- x 13))(if(> 14 x 12)(print'yes)(print'no))))

Ungolfed:

(defun w (x)
(if (> x 14)
(w (- x 13))
(if (> 14 x 12)
(print 'yes)
(print 'no))))


## Ruby (50 48 * 0.9 = 43.2)

Smart way to use eval

eval x="p gets.to_i*3%x.length == 0? 'yes':'no'"


## D 56 chars .80 bonus = 44.8

bool d(double i){
return modf(i*0,0769230769,i)<1e-3;
}


this might have been a cop-out with using 1/13 and a double can store any 32 bit number exactly

edit: this works by multiplying with 1/13 and checking the fractional part if it's different from 0 (allowing for rounding errors) or in other words it check the fractional part of i/13

• doesn't modf count as using modulus? – Blazer Feb 23 '12 at 19:05
• @Blazer not really it takes the fractional part of the first argument and returns it while storing the integral part in the second arg – ratchet freak Feb 23 '12 at 19:16
• Just a note: the result (yes/no) has to actually be output. Also, I'm somewhat curious as how this solution works. An explanation would be much appreciated! – Mr. Llama Feb 23 '12 at 19:28

## Python 2.7

(20 - 1 whitespace) * 0.9 (no division) = 17.1

print input()%015==0


yes/no instead of true/false: 31 * 0.9 (no division) = 27.9

print'yneos'[input()%015!=0::2]


takes advantage of python's int to convert other bases from strings into base 10 integers. you can see in both versions they use a different (yet same character length) base

edit: 1 char save in yes/no version

edit2: another 2 chars shaved!

edit3: thanks again to comments! even more characters shaved off by using python's builtin octal representations (015 == 13...) instead of int's base translation

• I see a cop-out with the different bases – ratchet freak Feb 23 '12 at 19:25
• 14 in base 9? I should have seen that coming. – Mr. Llama Feb 23 '12 at 19:29
• print['no','yes'][input()%int('d',14)==0 – Steven Rumbalski Feb 23 '12 at 19:32
• as far as I saw, a cop-out was defined as being something like 14-1 or 26/2. I just took creative liberty to represent 13 – Blazer Feb 23 '12 at 19:32
• @StevenRumbalski thanks for the 1 char save :P – Blazer Feb 23 '12 at 19:33

## Perl, 95 * 0.8 = 76

$_=<>; while($_>0){
$q=7*chop;$d=3*($m=chop$q);
chop$d;$_-=$d+$m}
if($_){print"no"} else{print"yes"}  The line breaks were added for clarity. I could have probably made this answer a lot shorter, but I feel that this answer represents a unique way of approaching the problem. # Python - score 27.9 (31 characters * 0.90) -- forgoes some bonus for shorter code. print'yneos'[2*input()%26>0::2]  older version: (47 characters * 0.80) -- complete rip-off of mellamokb's Javascript answer, but in Python. n=2*input() while n>0:n-=26 print'yneos'[n<0::2]  older version: (60 characters * 0.80) n=input() while n>12: for _ in'x'*12+'!':n-=1 print'yneos'[n>0::2]  older version: (105 characters * 0.80) n=abs(input()) while n>12:n=abs(sum(int(x)*y for x,y in zip(n[::-1],n*(1,-3,-4,-1,3,4)))) print'yneos'[n>0::2]  • Hmm, this is a nifty method. That 1,-3,-4 pattern is similar to what I saw on wikipedia. Still cool to see it in code. – Mr. Llama Feb 23 '12 at 19:35 • @GigaWatt: That's where I got it. The other pattern (1,10,9,12,3,4) would save 1 character but would not resolve to a value less than 13. – Steven Rumbalski Feb 23 '12 at 19:47 ## In Q: d:{$[0=x mod "I"$((string 6h$"q")[1 2]);yes;no]}
50*.9=45

• Welcome to CodeGolf.SE. You should put your code in a codeblock, and which point you can use backticks where you mean backticks as they no longer have formatting meaning. I've done the first part for you, please check it and fix any errata I've introduced. – dmckee Mar 2 '12 at 19:02

# Right Linear Grammar - ∞ points

S->ε
S->1A
S->0S
S->9I
S->3C
S->5E
S->4D
S->2B
S->7G
S->6F
S->8H
F->3K
K->0F
A->2L
K->1G
A->5B
A->0J
B->7A
J->5A
G->6K
G->8S
H->9K
F->5S
K->2H
I->6E
I->5D
J->4S
D->8I
B->6S
K->9B
F->6A
G->9A
K->6L
K->4J
C->1E
L->8K
E->5C
B->4K
C->0D
J->2K
D->2C
A->9F
J->7C
C->6J
C->8L
E->0K
L->0C
B->9C
E->2S
L->6I
I->0L
J->0I
B->2I
I->3B
H->1C
I->7F
C->4H
F->1I
G->4I
I->0G
C->3G
F->8C
D->0A
E->3A
I->9H
A->7D
C->2F
H->7I
A->8E
F->9D
E->8F
A->6C
D->6G
G->0E
D->5F
E->9G
H->2D
D->7H
H->3E
I->2A
K->3I
C->9S
C->7K
E->4B
D->1B
L->1D
J->9E
I->1S
E->1L
J->8D
D->9J
L->2E
J->3L
B->5L
B->8B
L->7J
L->9L
G->1F
A->4A
K->5K
B->3J
H->6H
E->7E
J->1J
D->4E
G->2G
J->6B
D->3D
E->6D
H->4F
I->4C
C->5I
F->0H
H->5G
K->7S
G->3H
L->5H
H->8J
A->3S
H->0B
B->1H
G->7L
K->8A
F->2J
F->7B
L->4G
F->4L
A->1K
B->0G
G->5J
L->3F


Then depending on how you choose to 'run' it, it will output 'yes' or 'no'.

Not a serious entry, just some fun ;)

EDIT: Perhaps I should explain a bit.

A grammar is a set of rules (productions) which define a language. A language can be thought of as all of the possible strings formed by an alphabet, that conform to the rules of it's grammar.

Here the alphabet is the set of all decimal digits. The grammar's rules are that all strings must form decimal integers that are divisible by 13.

We can use the grammar above to test whether a string belongs to our language.

The rules of the grammar contain terminal symbols (which are elements in the language) as well as non-terminal symbols which are replaced recursively.

It's easier to explain what's going on with an example:

Lets say for example that the string we are testing is 71955.

There is always a start symbol (which is non-terminal), in the case of the grammar above this is 'S'. At this point we have not read any characters from our string:

current pattern                    symbol read
S                                  ε


Now, we read the first symbol in our string which is '7', then we look for a rule in the grammar which has any of the non-terminals in our current pattern in the left hand side of the '->' and that has our symbol in the right hand side of the '->'. Luckily there is one (S->7G), so we replace the non-terminal symbols in our current pattern with the right hand side of the new rule:

current pattern                    symbol read
7G                                 7


Now we have the non-terminal 'G' in our pattern, and the next symbol to be read is '1', So we look for a rule in our grammar that begins with 'G->1". We find there is one (G->1F), so we replace the non terminal with the RHS of our new rule:

current pattern                    symbol read
71F                                1


Keep repeating this process:

Next rule: F->9D

current pattern                    symbol read
719D                               9


Next rule: D->5F

current pattern                    symbol read
7195F                              5


Next rule: F->5S

current pattern                    symbol read
71955S                             5


At this point we have no more symbols in our string, but we have another non-terminal symbol in there. We see from the first rule in the grammar that we can replace 'S' with the empty string (ε): S->ε

Doing so gives us the current patter: 71955ε which is the equivalent to 71955.

We have read all of the symbols in our string, and the pattern contains no non-terminal symbols. Which means that the string belongs to the language and therefore 71955 is in fact divisible by 13.

I.e. the goal is to have pattern = string. If you are left with any non-terminal symbols, after reading all of the symbols in your string, the string doesnt belong to the language. Likewise, if you still have more symbols in your string to read, but there are no rules in the grammar allowing you to go forward, then the string does not belong to the language.