"Maths+Programming " makes life easier !

This note is about some math concepts that can be converted into Python programs\color{#D61F06}{\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 get_primes(n)\textbf{get\_primes(n)} and it prints a list of all primes till the number nn.

img img

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


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

\bullet \quad This function is defined for coprime integers aa and bb, that mm is inverse of aa modulo bb if m×a1(modb)\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 mod_inv(a,b)\textbf{mod\_inv(a,b)} , it will return the inverse of aa modulo bb.

img img



2. Binomial Coefficient(ab)\mathbf{2.}\quad \quad\textbf{ Binomial Coefficient} \dbinom{a}{b}

(ab)\dbinom{a}{b} is the number of ways of choosing bb objects from a set of aa identical objects.

\bullet \quad It is defined as (ab)=a!b!(ab)!\dbinom{a}{b} = \dfrac{a!}{b!(a-b)!} (where a!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 (ab)\dbinom{a}{b} value is as follows

mg mg

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



3.Order of a modulo b (a special case, of coprimes)\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 aa, after which the remainder starts repeating.

For example,
33(mod5)324(mod5)332(mod5)341(mod5)353(mod5) 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 353^5, that means the remainder is repeating after multiplying by 343^4, so order of 33 modulo 55 is 4\boxed{4}

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

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

For example, if gcd(a,b)1gcd(a,b)\neq 1, say for numbers 88 and 1414 ,

88(mod14)828(mod14)...    8n8(mod14) \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 11. (Though 81≢1(mod14)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 aa modulo bb ( if gcd(a,b)=1gcd(a,b)=1 ), when you input mod_order(a,b)\textbf{mod\_order(a,b)}

img img

Note+Exercise:- Try to extend this program to numbers with gcd(a,b)1gcd(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
5 years, 1 month ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Shreya R - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

Congratulations Aditya on being selected as moderator

Usama Khidir - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

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

পদ্মা মাঝি - 5 years, 1 month 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 - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

Congrats for being selected as a moderator.

Harsh Shrivastava - 5 years, 1 month ago

Log in to reply

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

L N - 5 years, 1 month 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 - 5 years, 1 month 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 - 5 years, 1 month 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 - 5 years, 1 month 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 - 5 years ago

Log in to reply

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

Happy Melodies - 4 years, 11 months ago

Log in to reply

Sympy module in python is amazing.

Mharfe Micaroz - 4 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...