Will Code for Food.

For my normal friends, this disclaimer is a must -: Most of the words and sentences in this blog are full of geek and the dreaded mathematics. But you can magically make this nerdy blog go away. The trick is to press the keys Ctrl and W together and even before you finish reading this sentence, the blog will be gone, gone far away in some parallel universe in which it will be pressing Ctrl + W and you will be the one disappearing away!.

It was a drowsy Saturday night when before starting some boring TV serial to fall asleep, I decided to check what’s new on Facebook. I see my friend Janko describing some nice mathematical problem on project-euler with absurd words along with gigantic adjectives ;) Moreover, there is steak on offer. Yes, you read it correct, there is steak on offer for the problem solver. The first thing to flash after reading has to be this cartoon.

The problem had to be solved. It will be an injustice to the steak, if it goes unserved. The only thing on mind now: Mission 498.

I start thinking about the problem. Thought of an solution which would work in . But algebra is a bitch and does not go hand in hand with number theory; else my solution would had worked like a charm. The problem is in is the algebraic remainder and does correlate with the numeric remainder. Only if this was true, the problem would had been a cakewalk. But then one does not get steak for crappy code. The wheels in the brain have to be turned. The pages of the scratchpad have to be made dirty. Some Greek symbols have to be used to add dignity to the solution.

Another look at the problem and you know what has to be done. Why should you be dividing by when you can divide by . Yes, one can always substitute . This makes trivial i.e. last terms of binomial expansion of . To spell it out -:

Now that it has become a piece of cake, it’s time to code.. While traditionally I would had chosen C++ to code, but with recent ventures with Gospodice Princess I decided to show off python. Oh! You don’t know Gospodice Princess.

• He is atomic.
• Don’t know atomic, He is Aleksandar Tomic.
• Don’t know Aleksandar Tomic, He is Aleksandar Tomic (SQL).
• Don’t know Aleksandar Tomic (SQL), then go to savski most, close your eyes and jump into the river :D.

Cool, now that we know who Gospodice Princess is, we can proceed to the code. I wouldn’t want to leave an opportunity to show-off awesomeness of python, especially to my dear friend, Gospodice Princess. Just because I want the code to remain readable, the code is lengthy i.e. 18 lines; Yes, a python code with 18 lines is considered lengthy.

def ncr (n,r,p):
    num, dem = 1, 1;
    for i in range(r):
        num, dem = (num * (n-i) ) % p , (dem * (i+1)) % p ;
    return (num * pow(dem, p-2, p)) % p ;

def lucas(n, m, p):
    if n == 0 and m == 0 : return 1; np, mp  = n % p, m % p; return 0 if
    mp > np else lucas(n//p, m//p, p) * ncr ( np, mp, p);

def solve(n,m,d,p):
    return (lucas(n,d,p) * lucas(n-d-1, m-d-1,p)) % p;

if __name__ == '__main__' :
    if solve(6,3,1,999999937) != 24 : print ("Test1 Failed") ;
    if solve(100,10,4,1000000000000037) != 227197811615775: print ("Test2 Failed") ;
    print (solve(10**13, 10**12, 10**4,999999937));
    

So, now that the minor problem has been solved with a beautiful python code, the complex problem still remains. The problem of getting the steak lunch when the two parties are 6000 miles apart. I will leave this part for Janko to solve.

For honesty, I did take a little help from a friend (Fernando) to simplify the summation of combinatorial coefficients, but rest is my own work.

Cheers and Pozdrav.