×

# "Maths+Programming " makes life easier !

This note is about some math concepts that can be converted into $$\color{Red}{\textbf{Python programs}}$$ that you can easily write, they'll define some useful things in maths, which are generally not in the modules, but are needed at times.

So, these programs can really help you reduce calculations, they can do the calculations for you...

This is a program to print prime numbers till a range. (This is not written by me, but i felt like sharing because it's way useful)

Input $$\textbf{get_primes(n)}$$ and it prints a list of all primes till the number $$n$$.

img

If you want it to get simple, just add the line $$\text{li=get_primes(n)}$$ and then wanted changes in $$li$$.

$$\mathbf{1.}\quad \quad\textbf{Inverse of a modulo b}$$

$$\bullet \quad$$This function is defined for coprime integers $$a$$ and $$b$$, that $$m$$ is inverse of $$a$$ modulo $$b$$ if $$\displaystyle m\times a \equiv 1 \pmod{b}$$

$$\bullet \quad$$It is used when you want to perform actions like division in modulo, and also, it is used in the application of CRT (The Chinese Remainder Theorem).

$$\bullet \quad$$ The Python program that prints the Inverse of a number is as follows, after you type this program and input $$\textbf{mod_inv(a,b)}$$ , it will return the inverse of $$a$$ modulo $$b$$.

img

$$\mathbf{2.}\quad \quad\textbf{ Binomial Coefficient} \dbinom{a}{b}$$

$$\dbinom{a}{b}$$ is the number of ways of choosing $$b$$ objects from a set of $$a$$ identical objects.

$$\bullet \quad$$It is defined as $$\dbinom{a}{b} = \dfrac{a!}{b!(a-b)!}$$ (where $$a!$$ is factorial notation)

$$\bullet \quad$$It is useful in many (almost all) Combinatorics Problems and some Number Theory problems can be designed on them.

$$\bullet \quad$$The Python program that prints $$\dbinom{a}{b}$$ value is as follows

mg

So when you input $$\textbf{binom(a,b)}$$ after typing this program, you'll obtain the output as $$\binom{a}{b}$$

$$\mathbf{3.}\quad \quad\textbf{Order of a modulo b (a special case, of coprimes)}$$

$$\bullet \quad$$It is defined as the number of congruences of powers of $$a$$, after which the remainder starts repeating.

For example,
$$3\equiv 3 \pmod{5} \\ 3^2\equiv 4\pmod{5} \\ 3^3 \equiv 2 \pmod{5} \\ 3^4 \equiv 1 \pmod{5} \\ 3^5 \equiv 3 \pmod{5} \dots$$

See that the congruence will repeat again after $$3^5$$, that means the remainder is repeating after multiplying by $$3^4$$, so order of $$3$$ modulo $$5$$ is $$\boxed{4}$$

$$\bullet$$ >>> Note that order can be mentioned as the least positive integer $$m$$ for which $$a^m\equiv 1 \pmod{b}$$ (This can be treated as the definition for $$gcd(a,b)=1$$).

It's easy to see that if $$gcd(a,b) > 1$$ , then we'll have, $$a^m \equiv c \pmod{b} \implies gcd(a,b) \mid c$$

For example, if $$gcd(a,b)\neq 1$$, say for numbers $$8$$ and $$14$$ ,

$$\quad\quad\quad 8\equiv 8 \pmod{14} \\ \quad\quad\quad 8^2\equiv 8\pmod{14} \\\quad\quad\quad\quad\quad ... \\ \implies 8^n\equiv 8 \pmod{14}$$

So order of 8 modulo 14 is $$1$$. (Though $$8^1 \not\equiv 1 \pmod{14}$$

This is an extremely important thing in modular arithmetic and tedious calculations of remainder are reduced to simpler ones.

However, it's not that easy to find order of larger integers modulo some other large integers. So here is the python code that prints Order of $$a$$ modulo $$b$$ ( if $$gcd(a,b)=1$$), when you input $$\textbf{mod_order(a,b)}$$

img

Note+Exercise:- Try to extend this program to numbers with $$gcd(a,b)\neq 1$$ (A simple manipulation will do)

$$\bullet$$ This note might perhaps seem obvious to expert people, so note that it is for beginners and learners.

$$\bullet$$ When I think of some new program related to Maths, I will be adding to this note.

$$\bullet$$ If you all have any suggestions (additions), i would like to learn the new techniques of converting maths to Programming. Please comment and I will make sure it's included in the note.

2 years, 6 months ago

Sort by:

Superb note! Also congrats on being selected as Moderator!! · 2 years, 6 months ago

Of course this is a good idea, but as someone who has written Python code for a living I feel compelled to suggest a few improvements:

1) Finding modular inverse using brute force is exponential in the size of the input. We can easily make it polynomial by adapting Euclid's algorithm for GCD a bit:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def get_invs(a,b): if a == 0 or b == 0: return [-1, -1] if a == 1: return [1-b, 1] if b == 1: return [1, 1-a] if a > b: [x, y] = get_invs(b, a) return [y, x] r = b % a d = b // a [x, y] = get_invs (r, a) return [y-d*x, x] def get_inv(a, b): return get_invs(a, b)[0] def main(): print(get_inv(11,19)) # just to test: returns 7 if __name__ == '__main__': main() 

2) Finding factorials is expensive. We can do much better by using a tuple as a representation of a fraction and using the fact that nCk = (n/k) x (n-1)C(k-1):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 def gcd(a, b): if a > b: a, b = b, a while a > 0: a, b = b % a, a return b def reduce_frac(a, b): c = gcd(a, b) return (a//c, b//c) def get_binom1(n, k): if k == 0: return (1,1) (a, b) = get_binom1(n-1, k-1) return reduce_frac(a * n, b * k) def get_binom(n, k): if n < k or k < 0: return (0,1) if k > n - k: k = n - k return get_binom1(n, k)[0] def main(): print (get_binom(11,3)) if __name__ == '__main__': main() 

Alternatively, if you are okay with multiplying large numbers but don't like taking gcds each time,

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from functools import reduce from operator import mul def get_binom(n, k): if n < k or k < 0: return 0 if k > n - k: k = n - k return reduce (mul, range (n - k + 1, n + 1), 1) // reduce (mul, range (1, k + 1), 1) def main(): print (get_binom(11, 8)) if __name__ == '__main__': main() 

3) For the gcd = 1 case we don't even need to keep the list:

  1 2 3 4 5 6 7 8 9 10 11 12 13 def mod_order(a, b): c = 1 for i in range(1, b): c = (c * a) % b if c == 1: return i return -1 def main(): print (mod_order(8, 15)) if __name__ == '__main__': main() 

For the gcd != 1 case we do need something but a dict is probably the better solution. Something like this:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def mod_order(a, b): c = 1 d = {1:0} for i in range(1, b): c = (c * a) % b if c in d: return i - d[c] d[c] = i return -1 def main(): print (mod_order(8, 14)) if __name__ == '__main__': main() 
· 2 years, 6 months ago

Congratulations Aditya on being selected as moderator · 2 years, 6 months ago

Thanks friend ! I'll give all efforts possible to make Brilliant free of problematic problems and spam comments... · 2 years, 6 months ago

Thank you. I know C , But not python. I will learn it. I love programming a lot. · 2 years, 6 months ago

Sympy module in python is amazing. · 2 years, 4 months ago

Sir, How to create a program that inputs 2 numbers then get the GCF of it? in C language please. · 2 years, 6 months ago

@Jep Iglesia , I'm your age, 1 year younger as per what your account shows, So don't call me sir... I'm not knowing C that much, I learn Python..... but I've got a friend who can help you... I'll ask him to post that

@Aamir Faisal Ansari · 2 years, 6 months ago

Sir Thank you sir. You know I'm used to call Sir/Ma'am in Internet. Its a kind of showing respect. · 2 years, 6 months ago

Use Euclid Algorithm: see http://stackoverflow.com/questions/19738919/gcd-function-for-c · 2 years, 4 months ago

You guys may also want to look into IPython, Numpy, SciPy and Sage. · 2 years, 6 months ago

@L N IPython and Sage both use Numpy, SciPy and and other libraries to make programming easier. In particular Sage focuses on math. In fact in Sage:

sage: n = 2005
sage: inverse_mod(3,n)
1337


And for binomial coefficients:

sage: from sage.rings.arith import binomial
sage: binomial(5,2)
10


Don't know about mod order, but there may be something like it in sage. Examples taken from the docs. This doesn't even scratch the surface of what you can do with Sage. · 2 years, 6 months ago

Comment deleted Oct 27, 2014

Yes, I have been trying to make a program such that when you input a string of letters or numbers, like the word COMBINATORICS , then it will print the number of ways in which the letters/numbers can be arranged. I am working on that, and will add when succeed. · 2 years, 6 months ago

Comment deleted Oct 27, 2014

There is also Python's itertools library, which eliminates the need for all of these for loops.

from itertools import permutations

for p in permutations("ABC"):
print ''.join(p)


The ''.join(p) converts ('A', 'B', 'C') to 'ABC', by joining all the letters together with the empty string, '' · 2 years, 6 months ago

Wow, and if i want the number of permutations, then simply instead of "print" i can append to some list and then $$\textbf{len(list)}$$ . Thanks a lot ! · 2 years, 6 months ago

You should probably not do this - it may unnecessarily make your program use too much memory. itertools.permutations is great because instead of a list it returns a generator: https://wiki.python.org/moin/Generators. So if you create a list just to take the length, then you are taking up the memory for the list for no good reason. To find the length, we can just use a reduce which works fine on permutations:

  1 2 3 4 5 6 7 8 9 10 import itertools, functools def len_generator(gen): return functools.reduce(lambda x, y: x + 1, gen, 0) def main(): print (len_generator(itertools.permutations("asdrgfgbcd"))) if __name__ == '__main__': main() 
· 2 years, 6 months ago

Thanks, Daniel. I have seen someone else using this. But I didn't know exactly how it is used. Now I know. Thanks. · 2 years, 6 months ago

Thanks for the reply. I actually solved the COMBINATORICS problem on Brilliant.org. But I did it with a spreadsheet. I can actually do the permutation but I need to use 13 "for-in-range" statements since there are 13 letters to permutate. There is an built-in way. · 2 years, 6 months ago

In Python there's a much easier way to handle nested "for-in-range" loops (which can get a little nasty sometimes). In the module itertools there is a function called product which is an immense help when dealing with nested for loops. Let me give you an example:

 1 2 3 4 5 6 7 total = 0 for a in xrange(10): for b in xrange(10): for c in xrange(10): for d in xrange(10): total += a*b*c*d print total 

Is the same as...

 1 2 3 4 5 from itertools import product total = 0 for a,b,c,d in product(xrange(10),repeat=4): total += a*b*c*d print total 
· 2 years, 1 month ago

No need of 13 statements, use

li=sorted(str) , then use the binomial definition in bove note and make it

binom(len(li) ,li.count(i) )

Then for next one (i+1), use binom(len(li)-li.count(li[i]) , li.count(li[i+1]) · 2 years, 6 months ago

Aditya, can you show an actual example. I will wait for your COMBINATORICS example. Thanks. · 2 years, 6 months ago

Awesome....Have you heard about pygame module of python @Aditya Raut ?If yes,have you created any game using it? · 2 years, 6 months ago

Not heard, I am still a learner and I learn Python from self study... So I don't know what pygame is, will search ! · 2 years, 6 months ago