Waste less time on Facebook — follow Brilliant.
×

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


New addition here

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

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

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

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

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.

Note by Aditya Raut
3 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

Superb note! Also congrats on being selected as Moderator!!

Shreya R - 3 years, 2 months ago

Log in to reply

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()

Ww Margera - 3 years, 2 months ago

Log in to reply

Congratulations Aditya on being selected as moderator

Usama Khidir - 3 years, 2 months ago

Log in to reply

Thanks friend ! I'll give all efforts possible to make Brilliant free of problematic problems and spam comments...

Aditya Raut - 3 years, 2 months ago

Log in to reply

Thank you. I know C , But not python. I will learn it. I love programming a lot.

পদ্মা মাঝি - 3 years, 2 months ago

Log in to reply

Sympy module in python is amazing.

Mharfe Micaroz - 3 years ago

Log in to reply

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

Jep Iglesia - 3 years, 2 months ago

Log in to reply

@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

Aditya Raut - 3 years, 2 months ago

Log in to reply

Sir Thank you sir. You know I'm used to call Sir/Ma'am in Internet. Its a kind of showing respect.

Jep Iglesia - 3 years, 1 month ago

Log in to reply

Use Euclid Algorithm: see http://stackoverflow.com/questions/19738919/gcd-function-for-c

Happy Melodies - 3 years ago

Log in to reply

You guys may also want to look into IPython, Numpy, SciPy and Sage.

L N - 3 years, 2 months ago

Log in to reply

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.

L N - 3 years, 2 months ago

Log in to reply

Comment deleted Oct 27, 2014

Log in to reply

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.

Aditya Raut - 3 years, 2 months ago

Log in to reply

Comment deleted Oct 27, 2014

Log in to reply

@Chew-Seong Cheong 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, ''

Daniel Ploch - 3 years, 2 months ago

Log in to reply

@Daniel Ploch 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 !

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut 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()

Ww Margera - 3 years, 2 months ago

Log in to reply

@Daniel Ploch Thanks, Daniel. I have seen someone else using this. But I didn't know exactly how it is used. Now I know. Thanks.

Chew-Seong Cheong - 3 years, 2 months ago

Log in to reply

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.

Chew-Seong Cheong - 3 years, 2 months ago

Log in to reply

@Chew-Seong Cheong 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

Brock Brown - 2 years, 9 months ago

Log in to reply

@Chew-Seong Cheong 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])

Aditya Raut - 3 years, 2 months ago

Log in to reply

@Aditya Raut Aditya, can you show an actual example. I will wait for your COMBINATORICS example. Thanks.

Chew-Seong Cheong - 3 years, 2 months ago

Log in to reply

Awesome....Have you heard about pygame module of python @Aditya Raut ?If yes,have you created any game using it?

Harsh Shrivastava - 3 years, 2 months ago

Log in to reply

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

Aditya Raut - 3 years, 2 months ago

Log in to reply

Congrats for being selected as a moderator.

Harsh Shrivastava - 3 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...