# "Maths+Programming " makes life easier !

This note is about some math concepts that can be converted into $\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...

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.

6 years, 2 months ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$

Sort by:

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

- 6 years, 2 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() 

- 6 years, 2 months ago

Congratulations Aditya on being selected as moderator

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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

- 6 years, 2 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 !

- 6 years, 2 months ago

Congrats for being selected as a moderator.

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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.

- 6 years, 2 months ago

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

- 6 years, 2 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

- 6 years, 2 months ago

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

- 6 years, 2 months ago

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

- 6 years ago

Sympy module in python is amazing.

- 6 years ago