# Writeup for Death Sequence (Algorithms 100)
This challenge was about following sequence:> 1, 1, 1, 1, 10, 46, 217, 1027, 4861, 23005, ...
Our task was to determine last 9 digits of nth element of the sequence and last 9 digits of sum of n first elements.The main difficulty of this task was that n could be even 10^18. It is worth to mention, than we are counting positions from 1, not from zero (following task's description).
Firstly we managed to write formula for our sequence:>f(x) = 1, for x in in range <1,4> (inclusive)  >f(x) = 10, for x = 5   >f(x) = 5*f(x-1)-f(x-2)-f(x-3)-f(x-4)-f(x-5)
Another helpful observation is:>Let name sum(x) that sum(x) = f(1)+f(2)+...+f(n), now:  >sum(1) = 1      >sum(2) = 2   >sum(3) = 3   >sum(4) = 4   >sum(5) = 14  >sum(x) = 5*sum(x-1)-sum(x-2)-sum(x-3)-sum(x-4)-sum(x-5), for x > 5
Now we have to face the problem of very large n.We can't simply calculate f(x) and sum(n) in linear time.[Here](http://fusharblog.com/solving-linear-recurrence-for-programming-contest/) is an article about very useful technique which allows us to calculate such information in log(n) time.
I will try to explain this algorithm shortly, but if you want to fully understand it, it would be better to read this article.
So, we created two 6x6 matrices, one for nth element and one for sum:``` pythonbaseMatrix = [[ 5,  -1,  -1,  -1,  -1, 10],	[ 1,  0,  0,  0,  0,  1],	[ 0,  1,  0,  0,  0,  1],	[ 0,  0,  1,  0,  0,  1],	[ 0,  0,  0,  1,  0,  1],	[ 0,  0,  0,  0,  0,  0]]
baseMatrixSum = [[ 5,  -1,  -1,  -1,  -1, 14],  [ 1,  0,  0,  0,  0,  4],  [ 0,  1,  0,  0,  0,  3],  [ 0,  0,  1,  0,  0,  2],  [ 0,  0,  0,  1,  0,  1],  [ 0,  0,  0,  0,  0,  0]]```
Now if we calculate ```pow(baseMatrix, n)```, the nth number of sequence will be present in ```pow(baseMatrix, n)[0][5]``` and ```pow(baseMatrixSum, n)``` will give us sum of first n elements in ```pow(baseMatrixSum, n)[0][5]```
The operation of ```pow(a, n)``` can be calculated in log(n) time.Code for ```pow(int a, int n)``` (it works same for matrix, except you have another multiplication operator):```c++int pow(int a, int n){    if(n==0)return 1;    if(n==1)return a;    if(n%2==0){        int tmp = pow(a, n/2);        return tmp*tmp;    }    return pow(a, n-1)*a;}```
Unfortunately resulting numbers can still be very large, but all we want are last 9 digist, so we can calculate everything modulo.
Finally, the code - it is made of two pieces, one for communicating with server and another one for calculating sequences (this approach was useful because during the contest we've tried several implementations of sequence part). Both are in python 2.7:```python#server partimport socketimport sslimport subprocessimport time#openssl s_client -connect programming.pwn2win.party:9001
HOST = "programming.pwn2win.party"PORT = 9001
HOST = socket.getaddrinfo(HOST, PORT)[0][4][0]print(HOST)
sock = socket.socket()sock.connect((HOST, PORT))
sock = ssl.wrap_socket(sock,cert_reqs=ssl.CERT_NONE)
ctr=0while 1:	serv = sock.read();	print "from server: " + serv.rstrip()	if serv.startswith("WRONG"):		break	proc = subprocess.Popen(["python py_seq.py " + serv], stdout=subprocess.PIPE, shell=True)	(ans, err) = proc.communicate()	print "sending " + ans.rstrip() + " as result"	sock.write(ans)	ctr+=1print "finished after " + str(ctr) + " steps"```
```python#sequence partfrom copy import deepcopyimport sys
baseMatrix = [[ 5,  -1,  -1,  -1,  -1, 10],	[ 1,  0,  0,  0,  0,  1],	[ 0,  1,  0,  0,  0,  1],	[ 0,  0,  1,  0,  0,  1],	[ 0,  0,  0,  1,  0,  1],	[ 0,  0,  0,  0,  0,  0]]
baseMatrixSum = [[ 5,  -1,  -1,  -1,  -1, 14],    [ 1,  0,  0,  0,  0,  4],    [ 0,  1,  0,  0,  0,  3],    [ 0,  0,  1,  0,  0,  2],    [ 0,  0,  0,  1,  0,  1],    [ 0,  0,  0,  0,  0,  0]]
identityMatrix = [[ 1,  0,  0,  0,  0, 0],    [ 0,  1,  0,  0,  0,  0],    [ 0,  0,  1,  0,  0,  0],    [ 0,  0,  0,  1,  0,  0],    [ 0,  0,  0,  0,  1,  0],    [ 0,  0,  0,  0,  0,  1]]
emptyMatrix = [[ 0,  0,  0,  0,  0, 0],    [ 0,  0,  0,  0,  0,  0],    [ 0,  0,  0,  0,  0,  0],    [ 0,  0,  0,  0,  0,  0],    [ 0,  0,  0,  0,  0,  0],	[ 0,  0,  0,  0,  0,  0]]
def dispMatrix(m):	for i in range(0,6):		toDisp=""		for j in range(0,6):			toDisp += str(m[i][j])			toDisp += " "		print toDisp
def multiMod(left, right, mod):	retVal = deepcopy(emptyMatrix)	tmpMod = 1000000000000	for i in range(0,6):		for j in range(0,6):			retVal[i][j]=0			for k in range(0,6):				retVal[i][j] += (left[i][k])*(right[k][j])				retVal[i][j] %= tmpMod	return retVal
def powerModulo(m, n, mod):	if n == 0:		return deepcopy(identityMatrix) 	if n == 1:		return deepcopy(m)	if n % 2 == 0:		tmp = powerModulo(m, n/2, mod)		return multiMod(tmp, tmp, mod)	return multiMod(powerModulo(m, n-1, mod), m, mod)
modNum = 1000000000inputFromServ = long(sys.argv[1])-4matrixA = powerModulo(baseMatrix, inputFromServ, 1000000000000000)matrixB = powerModulo(baseMatrixSum, inputFromServ, 1000000000000000)
str1 = str(matrixA[0][5]%modNum)str1 = '0'*(9-len(str1)) + str1str2 = str(matrixB[0][5]%modNum)str2 = '0'*(9-len(str2)) + str2print str1+" "+str2```
And after a while we were given a flag:>CTF-BR{It-wAs-jUsT-a-ReCURsIVe-SequenCE-to-BE-coded-In-LOGN-XwmIBVyZ5QEC}