{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ This Jupyter notebook[1] is part of the Klopper Letures on Discrete Matheamtics and covers *the inclusion-exclusion principle*\n",
"+ Created by me, Dr Juan H Klopper\n",
" + Head of Acute Care Surgery\n",
" + Groote Schuur Hospital\n",
" + University Cape Town\n",
" + Email me with your thoughts, comments, suggestions and corrections \n",
" The Klopper Lectures on Discrete Mathematics study notes is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.\n",
"\n",
"+ [1] Fernando Pérez, Brian E. Granger, IPython: A System for Interactive Scientific Computing, Computing in Science and Engineering, vol. 9, no. 3, pp. 21-29, May/June 2007, doi:10.1109/MCSE.2007.53. URL: http://ipython.org"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from IPython.core.display import HTML\n",
"#css_file = 'numericalmoocstyle.css'\n",
"#css_file = \"custom.css\"\n",
"css_file = 'style.css'\n",
"HTML(open(css_file, 'r').read())"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import sympy as sym\n",
"import numpy as np\n",
"from array import array"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"sym.init_printing(use_latex = \"mathjax\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Inclusion-exclusion principle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## In this lesson"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Follow these links\n",
"- [Recap of the counting principle](#Recap-of-the-counting-principle)\n",
"- [Counting principles of disjoint sets](#Counting-principles-of-disjoint-sets)\n",
"- [The inclusion-exclusion principle](#The-inclusion-exclusion-principle)\n",
"- [The applications of the inclusion-exclusion principle](#The-applications-of-the-inclusion-exclusion-principle) (for those interested in number theory)\n",
" - [Sieve of Eratosthenes](#Sieve-of-Eratosthenes)\n",
" - [Euler's phi function](#Euler's-phi-function)\n",
" - [Derangements](#Derangements)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Recap of the counting principle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The **modulus**, also referred to as the **cardinality** of a set is the number of elements in a set. Sets can be **finite** (when there modulus is either $ 0 $ or a natural number. **Infinite** sets can be **countable**, that is when their elements can be arranged as a sequence or **uncountable** if not. Finite sets are countable."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Back to the top](#In-this-lesson)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Counting principles of disjoint sets"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Disjoint sets** are sets that have no elements in common. Their intersection is thus $ \\emptyset $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following **lemmas** apply for disjoint sets under set operations (that's some fancy math speak right there)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- $ n \\left( A \\cup B \\right) = n \\left( A \\right) + n \\left( B \\right) $\n",
"- If $ S $ is the disjoint union of two finite sets, $ A $ and $ B $, the $ S $ is finite and $ n \\left( S \\right) = n \\left( A \\right) + n \\left( B \\right) $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If $ A $ and $ B $ are finite sets then the following **corollary** applies\n",
"- $ n \\left( A - B \\right) = n \\left( A \\right) - n \\left( A \\cap B \\right) $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For any given set, $ A $, the disjoint union of $ A $ and $ {A}^{c} $ is $ \\mathbb{U} $. This gives us another **corollary**\n",
"- $ n \\left( {A}^{c} \\right) = n \\left( \\mathbb{U} \\right) - n \\left( A \\right) $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Back to the top](#In-this-lesson)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The inclusion-exclusion principle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This principle applies when finite sets are not disjoint. The **theorem** of the **inlusion-exclusion principle** then states that\n",
"- $ n \\left( A \\cup B \\right) = n \\left( A \\right) + n \\left( B \\right) - n \\left( A \\cap B \\right) $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For three sets we have the **corollary**\n",
"- $ n \\left( A \\cup B \\cup C \\right) = n \\left( A \\right) + n \\left( B \\right) + n \\left( C \\right) - n \\left( A \\cap B \\right) - n \\left( A \\cap C \\right) - n \\left( B \\cap C \\right) + n \\left( A \\cap B \\cap C \\right) $"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"We have to extend this to an arbitrary number, say $ n $, of finite sets. Remember that they are all finite $ \\left| {A}_{i} \\right| < \\infty $.\n",
"Let's start with a proof for $ n = 2 $. If they are not disjoint and both in some universal set, then we can make up the following disjoint sets: $ \\left( A \\cap {B}^{c} \\right) $, $ \\left( A \\cap B \\right) $ and $ \\left( {A}^{c} \\cap B \\right) $. Together these disjoint sets make up $ A \\cup B $.\n",
"Because they are disjoint we can calculate the modulus then as $$ \\left| A \\cup B \\right| = \\left| A \\cap {B}^{c} \\right| + \\left| A \\cap B \\right| + \\left| {A}^{c} \\cap B \\right| $$\n",
"Now, if we concentrate on $ A $ only we note that it can be written as $ A = \\left( A \\cap {B}^{c} \\right) \\cup \\left( A \\cap B \\right) $ and because they are disjoint we have $ \\left| A \\right| = \\left| A \\cap {B}^{c} \\right| + \\left| A \\cap B \\right| $.\n",
"For the same reasons $ \\left| B \\right| = \\left| {A}^{c} \\cap B \\right| + \\left| A \\cap B \\right| $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With some algebraic rearangment of the last two modulus euqations, we now have three equations $$ \\left| A \\cup B \\right| = \\left| A \\cap {B}^{c} \\right| + \\left| A \\cap B \\right| + \\left| {A}^{c} \\cap B \\right| \\\\ \\left| A \\cap {B}^{c} \\right| = \\left| A \\right| - \\left| A \\cap B \\right| \\\\ \\left| {A}^{c} \\cap B \\right| = \\left| B \\right| - \\left| A \\cap B \\right| $$\n",
"Substituting the last two equation into the first leaves $$ \\left| A \\cup B \\right| = \\left| A \\right| - \\left| A \\cap B \\right| + \\left| B \\right| - \\left| A \\cap B \\right| + \\left| A \\cap B \\right| $$\n",
"Cancellation leaves us with our required equation $$ n \\left( A \\cup B \\right) = n \\left( A \\right) + n \\left( B \\right) - n \\left( A \\cap B \\right) $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When attempting the inevitable word problems that appear in textbooks remember to see **or** as $ \\cup $ and **and** as $ \\cap $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To attempt a proof for $ n = 3 $ we must take note of the concept of **fundametal products**. It states that for any numbers of sets (all part of a universal set) we can make them up by the union of disjoint sets. These disjoint sets are the fundamental products. There are $ {2}^{n} $ fundamental products for the union of $ n $ sets. The last fundamental product is the complement of the union of all the sets. Together all the fundamental products make up the universal set.\n",
"For our proof for $ n = 3 $ we consider all the fundamental products except the last one. So we consider $ {2}^{3} - 1 = 7 $ fundamental products. They are $$ A\\cap B\\cap C\\\\ A\\cap B\\cap { C }^{ c }\\\\ A\\cap { B }^{ c }\\cap C\\\\ A\\cap { B }^{ c }\\cap { C }^{ c }\\\\ { A }^{ c }\\cap B\\cap C\\\\ { A }^{ c }\\cap { B }^{ c }\\cap C\\\\ { A }^{ c }\\cap B\\cap { C }^{ c } $$\n",
"So the modulus of $ A \\cup B \\cup C $ is the sum of the moduli of all of these fundamental products. We need only expand each set as we did for $ n = 2 $ and substitute to get to $$ n \\left( A \\cup B \\cup C \\right) = n \\left( A \\right) + n \\left( B \\right) + n \\left( C \\right) - n \\left( A \\cap B \\right) - n \\left( A \\cap C \\right) - n \\left( B \\cap C \\right) + n \\left( A \\cap B \\cap C \\right) $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is the general form of the equation we are after $$ \\left| { A }_{ 1 }\\cup{ A }_{ 2 }\\cup\\dots \\cup{ A }_{ n } \\right| =\\left| \\bigcup _{ i=1 }^{ n }{ { A }_{ i } } \\right| =\\sum _{ i=1 }^{ n }{ \\left| { A }_{ i } \\right| } -\\sum _{ i,j|i If you dissect it for resonable values of $ n $ (just so as to spare some paper), you will get to the equations for $ n = 2 $ and $ n = 3 $ above."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Back to the top](#In-this-lesson)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The applications of the inclusion-exclusion principle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This section is for those that are interested in **number theory**."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Sieve of Eratosthenes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The first example comes from counting the number of primes between $ 1 $ and some integer $ n $. This can be implemented as a dynamically growing sieve of Eratosthenes.\n",
"The Eratosthenes procedure follows this path:\n",
"- List all positive integers\n",
"- Remove all the multiples of $ 2 $, except for $ 2 $\n",
"- Keep the next integer after $ 2 $, which is $ 3 $ and remove all multiples of $ 3 $ except $ 3 $\n",
"- Keep the next integer after $ 3 $, which is $ 5 $ and remove all multiples of $ 5 $ except $ 5 $\n",
"- Keep the next integer after $ 5 $, which is $ 7 $ and ..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The primes would be $ \\left\\{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \\dots \\right\\} $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The *Number Theory* library of *sympy* contains the class ```sieve```. It grows a sieve of Eratosthenes."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# 1 is not a prime\n",
"1 in sym.sieve"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can create a list of number and check if they are prime."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 \t False\n",
"2 \t True\n",
"3 \t True\n",
"4 \t False\n",
"5 \t True\n",
"6 \t False\n",
"7 \t True\n",
"8 \t False\n",
"9 \t False\n",
"10 \t False\n",
"11 \t True\n",
"12 \t False\n",
"13 \t True\n",
"14 \t False\n",
"15 \t False\n",
"16 \t False\n",
"17 \t True\n",
"18 \t False\n",
"19 \t True\n",
"20 \t False\n",
"21 \t False\n",
"22 \t False\n",
"23 \t True\n",
"24 \t False\n",
"25 \t False\n",
"26 \t False\n",
"27 \t False\n",
"28 \t False\n",
"29 \t True\n"
]
}
],
"source": [
"# Create a for loop using a numpy range of the values 1 to 29\n",
"for i in np.arange(1, 30):\n",
" print(i, \"\\t\", i in sym.sieve)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 \t 2\n",
"2 \t 3\n",
"3 \t 5\n",
"4 \t 7\n",
"5 \t 11\n",
"6 \t 13\n",
"7 \t 17\n",
"8 \t 19\n",
"9 \t 23\n",
"10 \t 29\n"
]
}
],
"source": [
"# Printing a list of the primes 1 through 10\n",
"for i in np.arange(1, 11):\n",
" print(i, \"\\t\", sym.sieve[i])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, what if we want to exclude all the primes numbers between $ 1 $ and $ $, which are divisible by $ 2, 3, 5, 7 $?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Python™ has a function ```%``` which returns a remainder. So, $ 3 $ goes into $ 4 $ once with a remainder of $ 1 $."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$$1$$"
],
"text/plain": [
"1"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Python code\n",
"4 % 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So, if we get a remainder of $ 0 $, it means that one number is divisible by another without a remainder, which is what we want. We can create a simple ```for``` loop with an ```if``` and ```else``` conditionals."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\n",
"\n",
"\n",
"11\n",
"13\n",
"17\n",
"19\n",
"23\n"
]
}
],
"source": [
"for i in np.arange(1, 10):\n",
" if sym.sieve[i] % 2 == 0:\n",
" print()\n",
" elif sym.sieve[i] % 3 == 0:\n",
" print()\n",
" elif sym.sieve[i] % 5 == 0:\n",
" print()\n",
" elif sym.sieve[i] % 7 == 0:\n",
" print()\n",
" else:\n",
" print(sym.sieve[i])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Sympy* also has the ```sympy.prime``` and ```sympy.isprime``` keywords."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Is 5 a prime?\n",
"sym.isprime(5)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$$2$$"
],
"text/plain": [
"2"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# What is the first prime?\n",
"sym.prime(1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We could have created the ```for``` loop and ```if else``` conditionals above with these ```.isprime()``` and ```.prime``` functions."
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Now, though what if we want to calculate all the integers between $ 1 $ and a $ 1000 $, which are not divisible by $ 2, 3, 5 $ and $ 7 $?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can make use of the inclusion-exclusion principle. Let's construct four sets taken from the universal set $ \\mathbb{U} = \\left\\{ x \\quad | \\quad 1 \\le x \\le 1000 \\right\\} $\n",
"- $ {A}_{1} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 2\n",
"- $ {A}_{2} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 3\n",
"- $ {A}_{3} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 5\n",
"- $ {A}_{4} $ is the set of all the elements of $ \\mathbb{U} $ divisible by 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Therefor, we must have complements\n",
"- $ {A}_{1}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 2\n",
"- $ {A}_{2}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 3\n",
"- $ {A}_{3}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 5\n",
"- $ {A}_{4}^{c} $ is the set of all the elements of $ \\mathbb{U} $ not divisible by 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So we are looking for $ \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap {A}_{3}^{c} \\cap {A}_{4}^{c} \\right| $. By **De Morgan's law** we have $ {A}_{1} \\cap {A}_{2} \\cap {A}_{3} \\cap {A}_{4} = {\\left( {A}_{1} \\cup {A}_{2} \\cup {A}_{3} \\cup {A}_{4} \\right)}^{c} $.\n",
"We also have that $ \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap {A}_{3}^{c} \\cap {A}_{4}^{c} \\right| = \\left| {\\left( {A}_{1} \\cup {A}_{2} \\cup {A}_{3} \\cup {A}_{4} \\right)}^{c} \\right| = \\left| \\mathbb{U} \\right| - \\left| {A}_{1} \\cup {A}_{2} \\cup {A}_{3} \\cup {A}_{4} \\right| $. Let's calculate the right-hand side."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The modulus of the initial sets are\n",
"- $ \\left| \\mathbb{U} \\right| = 1000 $\n",
"- $ \\left| {A}_{1} \\right| = \\frac{1000}{2} = 500 $\n",
"- $ \\left| {A}_{2} \\right| = \\frac{1000}{3} = 333 $ with a remainder of $ 1 $, thus $ \\left\\lfloor \\frac { 1000 }{ 3 } \\right\\rfloor =333 $\n",
"- $ \\left| {A}_{3} \\right| = \\frac{1000}{5} = 200 $\n",
"- $ \\left| {A}_{4} \\right| = \\frac{1000}{7} = 142 $ with a remainder of $ 6 $, thus $ \\left\\lfloor \\frac { 1000 }{ 7 } \\right\\rfloor =142 $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Remember our equation $$ \\left| { A }_{ 1 }\\cup{ A }_{ 2 }\\cup\\dots \\cup{ A }_{ n } \\right| =\\left| \\bigcup _{ i=1 }^{ n }{ { A }_{ i } } \\right| =\\sum _{ i=1 }^{ n }{ \\left| { A }_{ i } \\right| } -\\sum _{ i,j|i\n",
"(the $ \\left\\lfloor \\quad \\right\\rfloor $ symbol is used for floor division)\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3 } \\right\\rfloor =166 $\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 3 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 5 } \\right\\rfloor = 100 $\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 7 } \\right\\rfloor = 71 $\n",
"- $ \\left| { A }_{ 2 }\\cap { A }_{ 3 } \\right| = \\left\\lfloor \\frac { 1000 }{ 3\\times 5 } \\right\\rfloor = 66 $\n",
"- $ \\left| { A }_{ 2 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 3\\times 7 } \\right\\rfloor = 47 $\n",
"- $ \\left| { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 5\\times 7 } \\right\\rfloor = 28 $\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 3 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3\\times 5 } \\right\\rfloor =33 $\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3\\times 7 } \\right\\rfloor = 23 $\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 5\\times 7 } \\right\\rfloor = 14 $\n",
"- $ \\left| { A }_{ 2 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 3\\times 5\\times 7 } \\right\\rfloor = 9 $\n",
"- $ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap { A }_{ 3 }\\cap { A }_{ 4 } \\right| = \\left\\lfloor \\frac { 1000 }{ 2\\times 3\\times 5\\times 7 } \\right\\rfloor =4 $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Getting all the signs right and calculating the right-hand side we have $$ 1000 - \\left( 500 + 333 + 200 + 142 - 166 - 100 - 71 - 66 - 47 - 28 + 33 + 23 + 14 + 9 - 4 \\right) = 228 $$\n",
"This then is the number of integeres between $ \\left[ 1, 1000 \\right] $ not divisible by $2, 3, 5, $ and $ 7 $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Just for interest's sake, there are much easier ways using python™ code. Here we will create a *list* with the values $ 1 $ to $ 1000 $. Then we will run through a ```for``` loop $ 1000 $ times starting at $ 1 $. Everytimes the loop runs we have to make sure the number is still in the *list* or else we will run into problems. If it is, we will check to see if the remainder of dividing that number by $ 2, 3, 5 $ or $ 7 $ is $ 0 $. If so, we remove it from the list. Here is the code."
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"answer = []\n",
"\n",
"for i in range(1, 1001):\n",
" answer.append(i)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"for i in range(1, 1001):\n",
" if i in answer:\n",
" if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 or i % 7 == 0:\n",
" answer.remove(i)\n",
" else:\n",
" answer = answer\n",
" else:\n",
" answer = answer"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$$228$$"
],
"text/plain": [
"228"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Checking how many numbers we have left\n",
"len(answer)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Back to the top](#In-this-lesson)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Euler's phi function"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"The Euler $ \\phi $ function uses the concept of **relative prime numbers**. Relative prime numbers are positive integers that only have $ 1 $ as a common divisior. So $ 2 $ and $ 5 $ are relative prime numbers, because their ownly common divisor is $ 1 $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We define a positive integer, $ n $. Then we have $ \\phi \\left( n \\right) $ as the number of relative prime numbers in the interval $ \\left[ 1, n \\right] $, which are relatively prime to $ n $.\n",
"So, $ \\phi \\left( 4 \\right) = 2 $. Let's see how that works. On the interval $ \\left[ 1, 4 \\right] $ we have the combinations $ \\left( 1, 4 \\right) $, $ \\left( 2, 4 \\right) $, $ \\left( 3, 4 \\right) $ and $ \\left( 4, 4 \\right) $. In the combination $ 1, 4 $ both only share the common divisor of $ 1 $. In the combination $ 2, 4 $ both are divisible by $ 1 $ and $ 2 $, so they are not relative prime numbers. In the combination $ 3, 4 $ both only share the common divisor of $ 1 $, but again, not so for $ 4, 4 $.\n",
"$ \\phi \\left( 5 \\right) = 4 $, since the combinations $ 1, 2, 3 $ and $ 4 $ with $ 5 $ are all each relatively prime. The combination $ 5, 5 $ has common divisors $ 1 $ and $ 5 $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We also need the notion of a **prime factor**. It is a list of prime numbers in the interval $ \\left[ 1, n \\right] $ that divide into $ n $. So for the numbers $ \\left\\{ 1, 2, 3, 4, 5 \\right\\} $ and thus $ n = 5 $, we have the prime numbers $ \\left\\{ 2, 3, 5 \\right\\} $ and of those only $ 5 $ divides $ 5 $ (without a remainder that is)."
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$$\\left [ 5\\right ]$$"
],
"text/plain": [
"[5]"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sym.ntheory.primefactors(5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have to develop some reasoning for calculating the Euler $ \\phi $ function. Suppose we define the distinct prime divisors of $ n $ as $ {p}_{1}, {p}_{2}, \\dots , {p}_{k} $ and the universal set $ \\mathbb{U} = \\left\\{ 1, 2, \\dots, n \\right\\} $. Then we have the subsets of $ \\mathbb{U} $, named $ {A}_{i} $, consisting of those integers divisible by $ {p}_{i} $. We are looking for all the integers in $ \\mathbb{U} $ that are not divisible by $ {p}_{i} $, therefor $ \\phi \\left( n \\right) = \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap \\dots \\cap {A}_{k}^{c} \\right| $. To calculate $ \\phi \\left( n \\right) $ we thus have $$ \\phi \\left( n \\right) = \\left| \\mathbb{U} \\right| - \\left| {A}_{1} \\cup {A}_{2} \\cup \\dots \\cup {A}_{k} \\right| $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider that if we take a positive integer $ d $ and $ d $ divides $ n $ then there are $ \\frac{n}{d} $ multiples of $ d $ in $ \\mathbb{U} $. So if $ \\mathbb{U} = \\left\\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \\right\\} $, then $ n = 10 $. If $ d = 2 $ then $ \\frac{n}{d} = \\frac{10}{2} = 5 $. So there are $ 5 $ multiples of $ 2 $ in $ \\mathbb{U} $, which is indeed $ \\left\\{ 2, 4, 6, 8, 10 \\right\\} $, with a modulus of $ 5 $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, consider this $$ \\left| { A }_{ i } \\right| =\\frac { n }{ { p }_{ i } } \\\\ \\forall \\quad i\\neq j,\\quad \\left| { A }_{ i }\\cap { A }_{ j } \\right| =\\frac { n }{ { p }_{ i }{ p }_{ j } } $$\n",
"This is what we just saw above. This means we have $$ \\left| { A }_{ 1 }\\cap { A }_{ 2 }\\cap \\dots \\cap { A }_{ k } \\right| =\\frac { n }{ { p }_{ 1 }{ p }_{ 2 }\\dots { p }_{ k } } $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Since $ \\left| \\mathbb{U} \\right| = n $ we only need $ \\left| {A}_{1} \\cup {A}_{2} \\cup \\dots \\cup {A}_{k} \\right| $. $$ \\phi \\left( n \\right) =n-\\left[ \\sum _{ i=1 }^{ k }{ \\frac { n }{ { p }_{ i } } } -\\sum _{ i=1,j=1,i\n",
"So for $ \\left\\{ 1, 2, 3 \\right\\} $, i.e. $ n = 3 $ we have the permutations $$ \\left\\{ 1,2,3 \\right\\} \\\\ \\left\\{ 1,3,2 \\right\\} \\\\ \\left\\{ 2,1,3 \\right\\} \\\\ \\left\\{ 2,3,1 \\right\\} \\\\ \\left\\{ 3,1,2 \\right\\} \\\\ \\left\\{ 3,2,1 \\right\\} $$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We note the derangements $ \\left\\{ 2,3,1 \\right\\} $ and $ \\left\\{ 3,1,2 \\right\\} $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To use the inclusion-exclusion principle we define the sets $ {A}_{i} $ to be all the permutations of $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} $ which keeps the element in position $ i $ in its natural place, i.e. where it started off in $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} \\quad \\forall \\quad i = 1, 2, 3, \\dots , n$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As per usual we define a universal set. Here, its is all the permutations of $ \\left\\{ 1, 2, 3, \\dots , n \\right\\} $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we define $ {D}_{n} = \\left| {A}_{1}^{c} \\cap {A}_{2}^{c} \\cap \\dots {A}_{n}^{c} \\right| = \\left| \\mathbb{U} \\right| -\\left| { A }_{ 1 }\\cup { A }_{ 2 }\\cup \\dots \\cup { A }_{ n } \\right| $"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The modulus of $ {A}_{1} $ is $ \\left( n-1 \\right)! $. This is the same for all $ \\left| {A}_{i} \\right| $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We are going to build up a summation equation again. For the first term we will have $$ \\sum _{ i=1 }^{ n }{ \\left| { A }_{ i } \\right| } =\\begin{pmatrix} n \\\\ 1 \\end{pmatrix}\\left( n-1 \\right) ! $$\n",
"Next up we will have $$ \\sum _{ i