> This is one of the 100 recipes of the [IPython Cookbook](http://ipython-books.github.io/), the definitive guide to high-performance scientific computing and data science in Python.


# 15.5. A bit of number theory with SymPy


```python
from sympy import *
init_printing()
```


```python
import sympy.ntheory as nt
```

## Prime numbers

Test whether a number is prime.


```python
nt.isprime(2011)
```

Find the next prime after a given number.


```python
nt.nextprime(2011)
```

What is the 1000th prime number?


```python
nt.prime(1000)
```

How many primes less than 2011 are there?


```python
nt.primepi(2011)
```

We can plot $\pi(x)$, the prime-counting function (the number of prime numbers less than or equal to some number x). The famous *prime number theorem* states that this function is asymptotically equivalent to $x/\log(x)$. This expression approximately quantifies the distribution of the prime numbers among all integers.


```python
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
```


```python
x = np.arange(2, 10000)
plt.plot(x, list(map(nt.primepi, x)), '-k', label='$\pi(x)$');
plt.plot(x, x / np.log(x), '--k', label='$x/\log(x)$');
plt.legend(loc=2);
```

Let's compute the integer factorization of some number.


```python
nt.factorint(1998)
```


```python
2 * 3**3 * 37
```

## Chinese Remainder Theorem

A lazy mathematician is counting his marbles. When they are arranged in three rows, the last column contains one marble. When they form four rows, there are two marbles in the last column, and there are three with five rows. The Chinese Remainer Theorem can give him the answer directly.


```python
from sympy.ntheory.modular import solve_congruence
```


```python
solve_congruence((1, 3), (2, 4), (3, 5))
```

There are infinitely many solutions: 58, and 58 plus any multiple of 60. Since 118 seems visually too high, 58 is the right answer.

> You'll find all the explanations, figures, references, and much more in the book (to be released later this summer).

> [IPython Cookbook](http://ipython-books.github.io/), by [Cyrille Rossant](http://cyrille.rossant.net), Packt Publishing, 2014 (500 pages).

08bb133dad476abb4fa85a06d715cab81115b171
ipynb
Jupyter Notebook
notebooks/chapter15_symbolic/05_number_theory.ipynb
hidenori-t/cookbook-code
750f546ed87b09d28532884b8074b96cd8d32a38
BSD-2-Clause
2015-01-01T18:15:54.000Z
2022-03-06T16:15:07.000Z
notebooks/chapter15_symbolic/05_number_theory.ipynb
bndxn/cookbook-code
90c31341edccf039187e6a3809fb336f83bb758f
BSD-2-Clause
2015-02-25T22:08:09.000Z
2018-09-28T08:41:38.000Z
notebooks/chapter15_symbolic/05_number_theory.ipynb
bndxn/cookbook-code
90c31341edccf039187e6a3809fb336f83bb758f
BSD-2-Clause
2015-01-02T13:53:11.000Z
2022-03-18T21:05:16.000Z
Qwen/Qwen-72B
1. YES
2. YES