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