blob: eea75f4d4bceeeff15c48a8965878317d7b574f8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# Euler's totient function
And now something completely different. Straight from the World of Number Theory.
Frankly, I just wanted to show off the powers of my new Estatico functionality
and give tribute to my all time hero **Leonhard Euler**.
## Definition
For a given value _n_ this function returns the number of positive integers,
relatively prime to _n_ up to _n_.
## Computing
You can compute it for instance via _Euler's product formula_, multiplying
over the distinct prime numbers dividing _p_:
$$\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$$
|
