1707 lines
53 KiB
Plaintext
1707 lines
53 KiB
Plaintext
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 34,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"# Alle har de nødvendige imports og inits printing\n",
|
||
"from discrete import *"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Extended euclidean algorithm"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## Polynomier"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 49,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAASkAAAAaCAYAAADrAKo1AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAKl0lEQVR4Ae2c25EUOwyGm60NYOFkABnAEsGBDFiIAMgAiid4oyADlgi4ZABEwCUDyOAskwHn/9yWy93t7unrTM9iVXl9k2VJlmXZPXDlz58/RYZSAy9evDhR6ZnXx3WfP1T7xpdzljWQNbBjDRzteL5Fp5MzeaR0Z8IkrzT+qU9nonOh9H0CvTw0ayBroKcGtO/epFAvjZOSgPck4C3ln1OC9myrO7lXGnddNG/2HJ/RsgayBsZrgCDhU334pXBSEsxd05Q/rgs4sM74bwPHZPSsgayBGTSg/ftLZD4ofxKTu3IZ3qQkFN4X4c5j4aaWRY9I6p7yG1Np5fFZA3+LBrRfuNXwtsu7LgEEb7o4IJ5PaAOonyrxvFLZt6r/VDu3IvcWfKwCg9iMXGmMwEeVDZgEGOUERB+6b5Wg/Vl13npmA8//qfK7sxEVIdGDb3eFnJPuZaHl9fNB8gRjWqtsnlezwfeqT424dyaqeCWquHFIPItf9joOCUf0Urz/UO5A5e9Kt6j4csVBlVgFb1Osl/MVOCkInSlnU/JI/FHliiNRnUkh/ljJTaB6LxA+DGLISz1APxX9lKC9+EshiVfkxXGvfgOm+F+qTXrhwMJ4MEBOQfS0eohskE/Zn1bPcJVBHGocNFR711nj5vFLeq8cBqrjcN3juMrsr5ct7LOfeZ86UdocRUgutIrqoShEHBnO4KYnHvoGFDDsJeCRiM5meJKPjUcIeldpQ923DeZd4+4owd9qYApPGos+ONAwvnerEaoHI8jt0aZ8WOkx07wo4psoir13SHBNzOKEAkgGDjj21Lkv40uSzlft+CKCm/sQOOZPT7AHZa5Aq1CahCH6A4y3sjbyr+jhoPD0OCmjzYYcKy8LQ1oTrJGnXeiH5wBOdzZAhmU1kPptIU7L9hHRuJXbOGFPc6M7H+Kk8I7AmhaZ03FOw+NKyiauXE1l2JWwVf0ZDk8D2MpBRVGHp+KS4/pB4A/8a8p/+PIF5S3y8Xg+OJKyh+nKPVKTsanxkhAFuI/yyN5pEOrnGsTmJ2LB8fHA9lp5oZwHWSI2d81UPRkWqv+2UqfT1Fj4sysX+A+ViJgeKAFfjb7yq2XT/v8O4Xv/3I7jYCkZRZf1xSaxn/+UsEXsrGK7qjsQPrjgAdjIG7U5+1WOc2Os2Q6HNXYLPnvik3BeK4FjNkWZN5XGHlBbnTdsmy/IzvZVLlQ2m2Uv8RYc3lxV7sUPdFYE6PfM8xOXu1jEifEmdXLchUUfSMrY5M6pqB4chsosBg6FuyYG4UBlFo47Z1C89VmuPhTP/RTnhocNuCrz7hG+AtiYRA5v2966MBaMqlDOwx2hJo6JKx1XO5QWZFJ5LXCofA/R3+wyak3ZxPbV0dmk2uzNsuI01I7DoI8PQuaUaPupOm9BjMe2sRXwgu2oXKgNG/6tfKOciN5dYZRzwMJD5dBTextvd9THXoAO8Exl5jT84KTU14cfPn6F/egoJv4IB/tnjiHAXjWHs3WccNEFY3jPxIfgG0zOrvG2r68fJ7Dqj+OcGCxAReF+HAuRUgiLhZPhJwfbwjrnKISH13TMK8f5JU89P69l11RoXQzRQSk4IQPoozSiKYDxcb9r3PefQ+V7iN6WkFE0T8QDNskGj+2CstsoNR5xPCFqoo9xfiyOi34SgPOiLxymqmM/ALYbO0Da4SWA+rt4gy62WSi/qeyrH4gzCHKoD4fSix8/vjMTPXd4dyJN78Th2i8Chvw6wOlD019LOSkU5k6ELv6EgzJZOFNoQFcfBkGd8Hebk+KUwFHgUMwAHvThQfgsvHlcFRvwTXTCIqsXZQVjVV/vE6FBOWoQnbYTyRmx+lPGAB9t80/mewGeIolnKU6WMcEFdoTDiCMP0NjclWjZ64cvt2Zz4Bmwbtg2PBIBYGfU6+vIHgDq8zk7K7vC3768sf9sz/AmEx/WffmJbT4wsOuC5ODm4vhXGfkbfgXdKplDilkM+zrlpGLErjKLBqQmKHvKu7yVkzkMKrHIz5S422MQ9j6QHBM1MrdzBFFbKIqWLba11Rfd2iflmqduvI6e2ona2jZC65xz8D03T63MjuyYQ8bE1KxvHNEUmgd7wlYtArFhDVw6hA8uY3gSwL4AnBx9Fdpq4k0qHHrgeIB23XE15hO9Bm82p3Jsh/5Ax/rU1saPCwoiPKHuB8QDvHM1JaFTbmgNJ6X2t7Qr1R2r7euLKU7KiMJMGxhOW7+1u0hKjLpNrcawMIYwNRdtFhZew4mqNse78s1U+kuNP1S+h+hjDhn9WrKeKWdUqD84mA5c2LYDJ9iJ2tpuBNhUjMc8ZmdE19SdjanYizfGeODQ/qjxLpIjtw7lbfywfxz/zFsbEw0vi+pvuwE0cKOGrhtAhObe78wpsb9NrwEHHlXho0HqRmF624x2UiJsJwinSWqhYIb3ga0gWoS4GBELwztWvCBd43GCJkwFTzRoZ377yoKSWPDYcboHysrAPVcOle+62pBDKbmOY2XsohnNH68vzS7aoaDxbGLsFnujKcWfe3YABwQPOJ7Kwal+7CsVoWFnNgf9jH2vBMQ0qbfxBm2ukrbJ2RdWVtHRrPODbIDNVR9T9kZ/JUPDcUTdo4uiC+8XytED8lOuyw79t0qpdvpCJHVEzQOKAayzrHX//Vfd9z1TMSaek6tbOL3izpYyXh3h3rX0p5p5DztNdagN5ZiCkC3cccEXb/Q13tPo2zMcCt//eD017EW6Rd989freosvBMm6jqf6N5sLecAwO1MbGxaa+lS3u+mGbgk2OkwggfKKw98qDQ1AZeshTt0uub4X66zYOrrXxUGxf7Ybw5mSAthJl+3lP4espfsDDKXAQ42jr/KppZ8D+Nx3GZccAMiiha3i09XB90R/kQZbNlefPn1OBEDkLChAZ9X1AZxwMYSQA9fDFRJNAE6+OYQIsVuoOWsC4UsVw3IiWP8KFJsJeVdnmd9iqs5DI5RZYdZwmRgt9Ng/evRIBqm1W8PMNepPSmEX5HsNTrBSNt+gY3cMr734YGmsXTneVbWM1/v2j+kbJ2EVT8xeeLqczhw9OlE2wUcIOaKt8bRY+7QBvoMnf9wkHObFn+gOo/kSVxj/89fhcX5Cf65rbhMqReQhv6BnbLjQ21msbP0afMYvbNnylQLzCH7xzMHCA4Q/skFDRBRXwyrrQjmM1h6ZqCWojaOEHoGer+a9axAzOjA09yHEI/7fG8bsqO71KKVfwVzzhFAc5qaXZ3iVPfq4h1/et4i9Bc+ukGWHnGtA6E0hwOJwf7Xx2P6Em57Ufb2nAzw4GOSg/kDt47+jLJttRzmlBWhPskqfbWtO55V+C5prW56/nRTZzIiUQtLj3teM9auSB5uZez70dhgjHxwCO7otSI2QcQ2zOMZJrjdHdTnjyhsY1ajZYguZszGVCc2oAv+C+bEJ0b5GU5n6pxCMld/tT5WOiqELjeBPhSsHVKsN6NPBIa/J6ZnaWoDkzi5ncDBog4AhBx2repKYIps1AePhFOb/0zZA1kDVwoBrQHubLJD9fCQfcpXBSrIeEIpLivSJ4YNozZA1kDRyGBrR37ZcBlTfmfV73ZtWcBOS6yL9e5xNohqyBrIHD0wABRuPX5/8DyrILYB7+gLcAAAAASUVORK5CYII=",
|
||
"text/latex": [
|
||
"$\\displaystyle \\operatorname{Poly}{\\left( x^{2} + x + 1, x, domain=\\mathbb{Z} \\right)}$"
|
||
],
|
||
"text/plain": [
|
||
"Poly(x**2 + x + 1, x, domain='ZZ')"
|
||
]
|
||
},
|
||
"execution_count": 49,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# Example usage\n",
|
||
"x = symbols('x', real=True)\n",
|
||
"\n",
|
||
"# Indskriv de to polynomier du vil tjekke\n",
|
||
"N = Poly(x**4 + x**3 - 2*x**2 + 3*x - 43, x)\n",
|
||
"M = Poly(x**2 + 2*x - 6, x)\n",
|
||
"\n",
|
||
"N,M\n",
|
||
"\n",
|
||
"A = Poly(x**3-1)\n",
|
||
"B = Poly(x**3+2*x**2+2*x+1)\n",
|
||
"\n",
|
||
"A, B\n",
|
||
"\n",
|
||
"gcd(A,B)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 5,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/html": [
|
||
"<div>\n",
|
||
"<style scoped>\n",
|
||
" .dataframe tbody tr th:only-of-type {\n",
|
||
" vertical-align: middle;\n",
|
||
" }\n",
|
||
"\n",
|
||
" .dataframe tbody tr th {\n",
|
||
" vertical-align: top;\n",
|
||
" }\n",
|
||
"\n",
|
||
" .dataframe thead th {\n",
|
||
" text-align: right;\n",
|
||
" }\n",
|
||
"</style>\n",
|
||
"<table border=\"1\" class=\"dataframe\">\n",
|
||
" <thead>\n",
|
||
" <tr style=\"text-align: right;\">\n",
|
||
" <th></th>\n",
|
||
" <th>k</th>\n",
|
||
" <th>r_k(x)</th>\n",
|
||
" <th>s_k(x)</th>\n",
|
||
" <th>t_k(x)</th>\n",
|
||
" </tr>\n",
|
||
" </thead>\n",
|
||
" <tbody>\n",
|
||
" <tr>\n",
|
||
" <th>0</th>\n",
|
||
" <td>0</td>\n",
|
||
" <td>x⁴ + x³ - 2*x² + 3*x - 43</td>\n",
|
||
" <td>1</td>\n",
|
||
" <td>0</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>1</th>\n",
|
||
" <td>1</td>\n",
|
||
" <td>x² + 2*x - 6</td>\n",
|
||
" <td>0</td>\n",
|
||
" <td>1</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>2</th>\n",
|
||
" <td>2</td>\n",
|
||
" <td>-15*x - 7</td>\n",
|
||
" <td>1</td>\n",
|
||
" <td>-x² + x - 6</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>3</th>\n",
|
||
" <td>3</td>\n",
|
||
" <td>-1511/225</td>\n",
|
||
" <td>x/15 + 23/225</td>\n",
|
||
" <td>-x³/15 - 8*x²/225 - 67*x/225 + 29/75</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>4</th>\n",
|
||
" <td>4</td>\n",
|
||
" <td>0</td>\n",
|
||
" <td>*</td>\n",
|
||
" <td>*</td>\n",
|
||
" </tr>\n",
|
||
" </tbody>\n",
|
||
"</table>\n",
|
||
"</div>"
|
||
],
|
||
"text/plain": [
|
||
" k r_k(x) s_k(x) \\\n",
|
||
"0 0 x⁴ + x³ - 2*x² + 3*x - 43 1 \n",
|
||
"1 1 x² + 2*x - 6 0 \n",
|
||
"2 2 -15*x - 7 1 \n",
|
||
"3 3 -1511/225 x/15 + 23/225 \n",
|
||
"4 4 0 * \n",
|
||
"\n",
|
||
" t_k(x) \n",
|
||
"0 0 \n",
|
||
"1 1 \n",
|
||
"2 -x² + x - 6 \n",
|
||
"3 -x³/15 - 8*x²/225 - 67*x/225 + 29/75 \n",
|
||
"4 * "
|
||
]
|
||
},
|
||
"execution_count": 5,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"df_results = extended_euclidean_algorithm_polys(N, M, x, true)\n",
|
||
"df_results.head(10)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## Numbers"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 6,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAEUAAAAVCAYAAAAQAyPeAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACzElEQVRYCeWY7XHTQBBAjYcCTOhAdJCQCog7cFJC0gH8tP9CB4EKMqGDhBJwB3YHgDsw7x06ISvWSLJOhoGdOe3earVf2ts7abTdbkflMZ/Ps/L8X6f3xTselWCxWLxlelpi/Q9klsddxPrMShC4MQOdg98FRuUC32TdM86gN5XbI3gZvPjsa+jvzuEvq7J9511tId/ku8WwQe6jvoWkMJlAfwGfyYyQ8z8xN0ADVfkL+DtJYW5CbsFTcADo9xAam0I//uL2v7a1hZwxNfoePUL+K/Qb8CYuHwO4jQIRK8C4ZNzAu4v8PdjnlSmAZ6wak2d1pYRWtjr4Hn0zfnWPYlKuUBJKJ0p0xBfIr9Dh2ymDFTKBbyWlgkFs5fGbh8mYi71k3dNjg1+ja2dZlXRWk1W61Zkc0pZ5uHrOxT7Qa82TjMua0MJOxv1kzXZgW+Zh6vKxga5qgjqYjfMmxGUTd6SDdTU9mNCWechMiqXt7pIabLCfcfhDasV79KWyZR5CUk4g6nrBHvvNLBJhJ7fH1C2rZiUtJRLbsqdMrJSkgJPXKDwBF2eWpAZKygawFQrEpFgySXYHnHQnewUuKgTaY7S9JSkMZCu0EpNiyfR2GidtrPs+E0xU0bOQ6/0C2trCblewUtZuyUvGeYunX+YyT3oQTppUm90jdPVkfAEvNFuwCfkBXjJ2Pily3Y2I51rZqiiq9b0ip09Lk+LxvfYojhPxnidJ4R6e1fUAjqfgB+Y6az+pgkkPgLyfDaGZgT3pbuK9DriVLfWhv43vZdPGeBP+pfBPYcU4Pda/E2zNGJNj2WtjB38yxkrZcZ6mJx9Z5fQNQNt7DqmSAVwpVHrI/P1BiIMug0F2icJkTmDLvvKtyv+Tc3xy6Rt/aAexUvTJbbTaJOWnhmuMH+OU28Vv4y5+fRR/3tSQZ2z2FzrdJcBOssTqjzA/R9wAAvwEUJC9piPR6rYAAAAASUVORK5CYII=",
|
||
"text/latex": [
|
||
"$\\displaystyle \\left( 12, \\ 21\\right)$"
|
||
],
|
||
"text/plain": [
|
||
"(12, 21)"
|
||
]
|
||
},
|
||
"execution_count": 6,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indskriv de to tal\n",
|
||
"a = 12\n",
|
||
"b = 21\n",
|
||
"\n",
|
||
"a,b"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 7,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/html": [
|
||
"<div>\n",
|
||
"<style scoped>\n",
|
||
" .dataframe tbody tr th:only-of-type {\n",
|
||
" vertical-align: middle;\n",
|
||
" }\n",
|
||
"\n",
|
||
" .dataframe tbody tr th {\n",
|
||
" vertical-align: top;\n",
|
||
" }\n",
|
||
"\n",
|
||
" .dataframe thead th {\n",
|
||
" text-align: right;\n",
|
||
" }\n",
|
||
"</style>\n",
|
||
"<table border=\"1\" class=\"dataframe\">\n",
|
||
" <thead>\n",
|
||
" <tr style=\"text-align: right;\">\n",
|
||
" <th></th>\n",
|
||
" <th>k</th>\n",
|
||
" <th>r_k</th>\n",
|
||
" <th>s_k</th>\n",
|
||
" <th>t_k</th>\n",
|
||
" </tr>\n",
|
||
" </thead>\n",
|
||
" <tbody>\n",
|
||
" <tr>\n",
|
||
" <th>0</th>\n",
|
||
" <td>0</td>\n",
|
||
" <td>12</td>\n",
|
||
" <td>1</td>\n",
|
||
" <td>0</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>1</th>\n",
|
||
" <td>1</td>\n",
|
||
" <td>21</td>\n",
|
||
" <td>0</td>\n",
|
||
" <td>1</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>2</th>\n",
|
||
" <td>2</td>\n",
|
||
" <td>12</td>\n",
|
||
" <td>1</td>\n",
|
||
" <td>0</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>3</th>\n",
|
||
" <td>3</td>\n",
|
||
" <td>9</td>\n",
|
||
" <td>-1</td>\n",
|
||
" <td>1</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>4</th>\n",
|
||
" <td>4</td>\n",
|
||
" <td>3</td>\n",
|
||
" <td>2</td>\n",
|
||
" <td>-1</td>\n",
|
||
" </tr>\n",
|
||
" <tr>\n",
|
||
" <th>5</th>\n",
|
||
" <td>5</td>\n",
|
||
" <td>0</td>\n",
|
||
" <td>None</td>\n",
|
||
" <td>None</td>\n",
|
||
" </tr>\n",
|
||
" </tbody>\n",
|
||
"</table>\n",
|
||
"</div>"
|
||
],
|
||
"text/plain": [
|
||
" k r_k s_k t_k\n",
|
||
"0 0 12 1 0\n",
|
||
"1 1 21 0 1\n",
|
||
"2 2 12 1 0\n",
|
||
"3 3 9 -1 1\n",
|
||
"4 4 3 2 -1\n",
|
||
"5 5 0 None None"
|
||
]
|
||
},
|
||
"execution_count": 7,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"df_results = extended_euclidean_algorithm_integers(a,b)\n",
|
||
"df_results.head(10)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Inverse of mod\n",
|
||
"\n",
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 8,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Does not exist\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"#Insert values:\n",
|
||
"n = 6\n",
|
||
"mod = 9\n",
|
||
"\n",
|
||
"try:\n",
|
||
" print(f\"The multiplicative invers is : {mod_inverse(n,mod)}\")\n",
|
||
"except:\n",
|
||
" print(\"Does not exist\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 9,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"The multiplicative invers is : 1\n",
|
||
"The multiplicative invers is : 3\n",
|
||
"The multiplicative invers is : 2\n",
|
||
"The multiplicative invers is : 4\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"values = [1,2,3,4]\n",
|
||
"mod = 5\n",
|
||
"\n",
|
||
"for n in values:\n",
|
||
" try:\n",
|
||
" print(f\"The multiplicative invers is : {mod_inverse(n,mod)}\")\n",
|
||
" except:\n",
|
||
" print(\"Does not exist\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Hvis svarmulighed ikke forkommer, så tjek forskellen mellem mod og n, eksempelvis: $(15 \\mod{17} = -2 \\mod{17})$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Chinese remainder therom (system of congruences)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 57,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"x ≡ 1 (mod 10)\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Definer modulo\n",
|
||
"moduli = [2, 5, ]\n",
|
||
"\n",
|
||
"# Define the remainders\n",
|
||
"remainders = [1, 1, 7]\n",
|
||
"\n",
|
||
"# Solve using the Chinese Remainder Theorem\n",
|
||
"solution, modulus = crt(moduli, remainders)\n",
|
||
"\n",
|
||
"# Print the solution\n",
|
||
"print(f\"x ≡ {solution} (mod {modulus})\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Andet eksempel\n",
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Til denne del beskrives alt som:\n",
|
||
"$$\n",
|
||
"y \\cdot x \\equiv a \\mod{b}\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Start med at analysere ligningen $2x\\equiv a \\mod{6}$.\n",
|
||
"Her udregner vi gcd(2,6). For at denne ligning har en løsning, skal $gcd(2,6) \\mid a$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 11,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAAkAAAAOCAYAAAD9lDaoAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA3UlEQVQoFW2RvRGCQBCFD7UAxhIgNXI0J8AO1BK0BEJItQMMTTU0w4DE1A6gBMYOzu+dg4PIzrzZ27dvf+7Os9aaLMsCY0wCZAvQgAT+KWIMJMghtlEU3cCpLMsZ3Bn/IK5HBAewB1+jQF1f4CJSohhUJHwRHbtz9uEDiRTUBKocMt9o8SGkaVoBUtaN+6um6xxSF3I31rgh08JXxEeX7I9iRA6KLv/TicodlVP8qtt+0gYk1pxD/KbDaa/P4iS06BLffk2rU2HjMV/qAui9+hZTGGqcBBJqn765D34Dzrdx4/BA7EwAAAAASUVORK5CYII=",
|
||
"text/latex": [
|
||
"$\\displaystyle 2$"
|
||
],
|
||
"text/plain": [
|
||
"2"
|
||
]
|
||
},
|
||
"execution_count": 11,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"g = gcd(2,6)\n",
|
||
"g"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Vi kan nu sige Hvis 2 deler a, sæt a=2k, så får vi $2x \\equiv 2k \\mod{6}$.\n",
|
||
"Ved at dividere alt igennem med 2 får vi:\n",
|
||
"$$\n",
|
||
"x \\equiv k \\mod{3}\n",
|
||
"$$\n",
|
||
"Men heldigvis skal du ikke tænke over dette, så det er bare at nyde det nedstående"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 12,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"x ≡ 21 (mod 42) or 21 + 42ℤ\n",
|
||
"No solution. ∅\n",
|
||
"x ≡ 7 (mod 42) or 7 + 42ℤ\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indskriv værdier\n",
|
||
"a_val = [0,1,2]\n",
|
||
"for a in a_val:\n",
|
||
" # Inskriv formler\n",
|
||
" equations = [\n",
|
||
" (2, a, 6), # 2x ≡ a (mod 6)\n",
|
||
" (1, 7, 14) # x ≡ 7 (mod 14)\n",
|
||
" ]\n",
|
||
"\n",
|
||
" res = solve_system_congruences(equations)\n",
|
||
" if res is None:\n",
|
||
" print(\"No solution. ∅\")\n",
|
||
" else:\n",
|
||
" sol, mod = res\n",
|
||
" print(f\"x ≡ {sol} (mod {mod}) or {sol} + {mod}ℤ\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Ekstra eksempel\n",
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 13,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"x ≡ 4 (mod 22) or 4 + 22ℤ\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indskriv værdier\n",
|
||
"a_val = [4]\n",
|
||
"for a in a_val:\n",
|
||
" # Inskriv formler\n",
|
||
" equations = [\n",
|
||
" (34,a,44) # 34x ≡ 4 (mod 44)\n",
|
||
" ]\n",
|
||
"\n",
|
||
" res = solve_system_congruences(equations)\n",
|
||
" if res is None:\n",
|
||
" print(\"No solution. ∅\")\n",
|
||
" else:\n",
|
||
" sol, mod = res\n",
|
||
" print(f\"x ≡ {sol} (mod {mod}) or {sol} + {mod}ℤ\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Conguence to ukendte"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 14,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"For c=2: Løsningsmængde: ∅\n",
|
||
"For c=35: Løsningsmængde: x = 9 + 13ℤ\n",
|
||
"\n",
|
||
"For at 14x ≡ c (mod 91) har løsninger, skal gcd(14,91)=7 dividere c.\n",
|
||
"Dvs. c ∈ 7ℤ.\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indsæt værdier her:\n",
|
||
"# Exempel på ligning: 14x = c(mod 91) hvor c er 2 eller 35\n",
|
||
"a, m = 14, 91\n",
|
||
"test_values = [2, 35]\n",
|
||
"\n",
|
||
"g = gcd(a, m)\n",
|
||
"for c_val in test_values:\n",
|
||
" sol = solve_linear_congruence(a, c_val, m)\n",
|
||
" if sol is None:\n",
|
||
" print(f\"For c={c_val}: Løsningsmængde: ∅\")\n",
|
||
" else:\n",
|
||
" x0, M, g = sol\n",
|
||
" # Løsningsmængde: x = x0 + MZ\n",
|
||
" print(f\"For c={c_val}: Løsningsmængde: x = {x0} + {M}ℤ\")\n",
|
||
"\n",
|
||
"# Angiv mængden af værdier af c in Z, hvor kongruensligningen har løsninger\n",
|
||
"print(f\"\\nFor at 14x ≡ c (mod 91) har løsninger, skal gcd(14,91)={g} dividere c.\")\n",
|
||
"print(f\"Dvs. c ∈ {g}ℤ.\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Calculate n choose k $n \\choose k$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 72,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"60090030 120180060\n",
|
||
"46676090050254435975722599130606507849226258221701123142545570906756415193569598983236485120000000000000\n",
|
||
"2800565403015266158543355947836390470953575493302067388552734254405384911614175938994189107200000000000000\n",
|
||
"12380966370681345810912689446840214482379749677372406391185140530874878275783882304549934428090700497046810287249817600000000000000000000\n",
|
||
"825397758045423054060845963122680965491983311824827092745676035391658551718925486969995628539380033136454019149987840000000000000000000\n",
|
||
"412698879022711527030422981561340482745991655912413546372838017695829275859462743484997814269690016568227009574993920000000000000000000\n",
|
||
"206349439511355763515211490780670241372995827956206773186419008847914637929731371742498907134845008284113504787496960000000000000000000\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indtast værdier\n",
|
||
"n = 30\n",
|
||
"\n",
|
||
"print(2*comb(n, 10), 4*comb(n,10))\n",
|
||
"\n",
|
||
"print(((factorial(3*n)))/(4*n*factorial(n)))\n",
|
||
"\n",
|
||
"print((factorial(3*n))/(2*factorial(n)))\n",
|
||
"\n",
|
||
"print(factorial(3*n)/(4*n))\n",
|
||
"\n",
|
||
"print(factorial(3*n)/(2*n**2))\n",
|
||
"print(factorial(3*n)/(4*n**2))\n",
|
||
"print(factorial(3*n)/(8*n**2))\n",
|
||
"\n",
|
||
"\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Problem: Equivalent Sets\n",
|
||
"\n",
|
||
"**conjugated** of a set. Given a universal set $U$, the **conjugated** of a set $A \\subseteq U$ is the set of all elements in $U$ that are not in $A$. Formally:\n",
|
||
"\n",
|
||
"$$\n",
|
||
"\\overline{A} = \\{ x \\in U : x \\notin A \\}\n",
|
||
"$$\n",
|
||
"\n",
|
||
"\n",
|
||
"## Question:\n",
|
||
"Given a universal set $ U $, which of the following sets are equal to $ \\overline{A \\cap (B \\cup C)} $?\n",
|
||
"\n",
|
||
"### Options:\n",
|
||
"1. $ \\text{None of these} $\n",
|
||
"2. $ (A \\cap (B \\cup C)) - U $\n",
|
||
"3. $ \\overline{A} \\cap (\\overline{B} \\cup \\overline{C}) $\n",
|
||
"4. $ A \\cup (B \\cap C) $\n",
|
||
"5. $ (U - (A \\cap B)) \\cap (U - (A \\cap C)) $"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Answer:\n",
|
||
"**Step 1: Start with the given expression**\n",
|
||
"\n",
|
||
"$$\n",
|
||
"\\overline{A \\cap (B \\cup C)}\n",
|
||
"$$\n",
|
||
"\n",
|
||
"**Step 2: Apply De Morgan's Laws**\n",
|
||
"\n",
|
||
"Using De Morgan's law:\n",
|
||
"$$\n",
|
||
"\\overline{X \\cap Y} = \\overline{X} \\cup \\overline{Y}\n",
|
||
"$$\n",
|
||
"we can rewrite:\n",
|
||
"$$\n",
|
||
"\\overline{A \\cap (B \\cup C)} = \\overline{A} \\cup \\overline{B \\cup C}\n",
|
||
"$$\n",
|
||
"\n",
|
||
"Now apply De Morgan's law again to $\\overline{B \\cup C}$:\n",
|
||
"$$\n",
|
||
"\\overline{B \\cup C} = \\overline{B} \\cap \\overline{C}\n",
|
||
"$$\n",
|
||
"\n",
|
||
"So we have:\n",
|
||
"$$\n",
|
||
"\\overline{A \\cap (B \\cup C)} = \\overline{A} \\cup (\\overline{B} \\cap \\overline{C})\n",
|
||
"$$\n",
|
||
"\n",
|
||
"This is our simplified form.\n",
|
||
"\n",
|
||
"**Step 3: Compare with the given options**\n",
|
||
"\n",
|
||
"1. **None of these:** We should check all other options first.\n",
|
||
"\n",
|
||
"2. $(A \\cap (B \\cup C)) - U$:\n",
|
||
"\n",
|
||
" Subtracting the universal set $U$ from any set results in the empty set. Thus:\n",
|
||
" $$\n",
|
||
" (A \\cap (B \\cup C)) - U = \\emptyset\n",
|
||
" $$\n",
|
||
" This clearly doesn't match $\\overline{A \\cap (B \\cup C)}$.\n",
|
||
"\n",
|
||
"3. $\\overline{A} \\cap (\\overline{B} \\cup \\overline{C})$:\n",
|
||
"\n",
|
||
" Our derived form is $\\overline{A} \\cup (\\overline{B} \\cap \\overline{C})$. Notice that:\n",
|
||
" $$\n",
|
||
" \\overline{A} \\cup (\\overline{B} \\cap \\overline{C}) \\neq \\overline{A} \\cap (\\overline{B} \\cup \\overline{C})\n",
|
||
" $$\n",
|
||
" They are not the same due to the difference in how unions and intersections distribute.\n",
|
||
"\n",
|
||
"4. $A \\cup (B \\cap C)$:\n",
|
||
"\n",
|
||
" This doesn't match the complement form we have. Substituting a few test cases quickly shows it doesn't align with $\\overline{A \\cap (B \\cup C)}$.\n",
|
||
"\n",
|
||
"5. $(U - (A \\cap B)) \\cap (U - (A \\cap C))$:\n",
|
||
"\n",
|
||
" Let's rewrite this using complements. Since $U - X = \\overline{X}$, we get:\n",
|
||
" $$\n",
|
||
" (U - (A \\cap B)) \\cap (U - (A \\cap C)) = \\overline{A \\cap B} \\cap \\overline{A \\cap C}\n",
|
||
" $$\n",
|
||
"\n",
|
||
" Apply De Morgan's law to each:\n",
|
||
" $$\n",
|
||
" \\overline{A \\cap B} = \\overline{A} \\cup \\overline{B}\n",
|
||
" $$\n",
|
||
" $$\n",
|
||
" \\overline{A \\cap C} = \\overline{A} \\cup \\overline{C}\n",
|
||
" $$\n",
|
||
"\n",
|
||
" Substitute these back:\n",
|
||
" $$\n",
|
||
" (\\overline{A} \\cup \\overline{B}) \\cap (\\overline{A} \\cup \\overline{C})\n",
|
||
" $$\n",
|
||
"\n",
|
||
" Now use the distributive law:\n",
|
||
" $$\n",
|
||
" (\\overline{A} \\cup \\overline{B}) \\cap (\\overline{A} \\cup \\overline{C}) = \\overline{A} \\cup (\\overline{B} \\cap \\overline{C})\n",
|
||
" $$\n",
|
||
"\n",
|
||
" This matches exactly with our simplified form of $\\overline{A \\cap (B \\cup C)}$.\n",
|
||
"\n",
|
||
"**Conclusion:**\n",
|
||
"\n",
|
||
"Option 5 is exactly equal to $\\overline{A \\cap (B \\cup C)}$.\n",
|
||
"\n",
|
||
"---\n",
|
||
"\n",
|
||
"# Final Answer\n",
|
||
"\n",
|
||
"$$\n",
|
||
"\\boxed{(U - (A \\cap B)) \\cap (U - (A \\cap C))}\n",
|
||
"$$\n",
|
||
"\n",
|
||
"Thus, the correct choice is **Option 5**."
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Permutations"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Consider all permutations of abcde.\n",
|
||
"1. How many do not contain abc?\n",
|
||
"2. How many contain ab or bc?\n",
|
||
"3. How many contain ab or bc but not abc?"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Count containing 'ace': 6\n",
|
||
"Count not containing 'ab, bc, cd': 64\n",
|
||
"Count not containing 'abc': 114\n",
|
||
"Count containing 'ab' or 'cd': 42\n"
|
||
]
|
||
},
|
||
{
|
||
"ename": "SyntaxError",
|
||
"evalue": "keyword argument repeated: exclude_substrings (3684453969.py, line 21)",
|
||
"output_type": "error",
|
||
"traceback": [
|
||
" \u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[77]\u001b[39m\u001b[32m, line 21\u001b[39m\n\u001b[31m \u001b[39m\u001b[31mab = pf.filter_permutations(include_substrings=['ab'], exclude_substrings=['cd'], exclude_substrings=['bc'])\u001b[39m\n ^\n\u001b[31mSyntaxError\u001b[39m\u001b[31m:\u001b[39m keyword argument repeated: exclude_substrings\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indsæt her:\n",
|
||
"pf = PermutationFilter(\"abcde\")\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc'\n",
|
||
"ace = pf.filter_permutations(include_substrings=['ace'])\n",
|
||
"print(\"Count containing 'ace':\", len(ace))\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc'\n",
|
||
"no_ab_bc_cd = pf.filter_permutations(exclude_substrings=['ab', 'bc', 'cd'])\n",
|
||
"print(\"Count not containing 'ab, bc, cd':\", len(no_ab_bc_cd))\n",
|
||
"\n",
|
||
"# All permutations not containing 'abc'½\n",
|
||
"no_abc = pf.filter_permutations(exclude_substrings=['abc'])\n",
|
||
"print(\"Count not containing 'abc':\", len(no_abc))\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc'\n",
|
||
"ab_bc = pf.filter_permutations(include_substrings=['ab', 'cd'])\n",
|
||
"print(\"Count containing 'ab' or 'cd':\", len(ab_bc))\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc'\n",
|
||
"ab = pf.filter_permutations(include_substrings=['ab'], exclude_substrings=['cd'])\n",
|
||
"print(\"Count containing 'ab':\", len(ab))\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc'\n",
|
||
"cd = pf.filter_permutations(include_substrings=['cd'], exclude_substrings=['ab', 'bc'])\n",
|
||
"print(\"Count containing 'cd':\", len(cd))\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc'\n",
|
||
"bc = pf.filter_permutations(include_substrings=['bc'], exclude_substrings=['ab', 'cd'])\n",
|
||
"print(\"Count containing 'bc':\", len(bc))\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"# All permutations containing 'ab' or 'bc' but not 'abc'\n",
|
||
"ab_bc_no_abc = pf.filter_permutations(include_substrings=['ab', 'bc'], exclude_substrings=['abc'])\n",
|
||
"print(\"Count containing 'ab' or 'bc' but not 'abc':\", len(ab_bc_no_abc))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Coefficients"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"The coefficient of $x^7 \\cdot y^2$ in $(2x+3y)^9$ is:"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 73,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"{2: 7, 3: 2, 7: 1, -1: 1}\n",
|
||
"{2: 7, 3: 2, 7: 1, -1: 1}\n",
|
||
"{2: 7, 3: 2, 7: 1, -1: 1}\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Define the variables\n",
|
||
"x, y = symbols('x y')\n",
|
||
"\n",
|
||
"# Indskriv funktionen og coefficients\n",
|
||
"expr = (1-2*x**3*y**4)**10\n",
|
||
"expr2 = (2*x**3-y**4)**10\n",
|
||
"expr3 = (x**3-2*y**4)**10\n",
|
||
"coeffs = x**15 * y**20\n",
|
||
"\n",
|
||
"# Expand the expression\n",
|
||
"expanded_expr = expand(expr)\n",
|
||
"expanded_expr2 = expand(expr2)\n",
|
||
"expanded_expr3 = expand(expr3)\n",
|
||
"\n",
|
||
"# Extract the coefficient of x^7 * y^2\n",
|
||
"coefficient = expanded_expr.coeff(coeffs)\n",
|
||
"coefficient2 = expanded_expr2.coeff(coeffs)\n",
|
||
"coefficient3 = expanded_expr3.coeff(coeffs)\n",
|
||
"\n",
|
||
"# Factorize the coefficient\n",
|
||
"factorized_coefficient = factorint(coefficient)\n",
|
||
"factorized_coefficient2 = factorint(coefficient2)\n",
|
||
"factorized_coefficient3 = factorint(coefficient3)\n",
|
||
"\n",
|
||
"print(factorized_coefficient)\n",
|
||
"print(factorized_coefficient2)\n",
|
||
"print(factorized_coefficient3)\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Aflæses som $2^93^4$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"## If it doesn't work use Binomial Theorem (Manual Approach):\n",
|
||
"\n",
|
||
"### General Term in the Expansion of $ (2x + 3y)^9 $\n",
|
||
"\n",
|
||
"The general term in the expansion of $ (2x + 3y)^9 $ is given by:\n",
|
||
"\n",
|
||
"$$\n",
|
||
"T_k = \\binom{9}{k} \\cdot (2x)^{9-k} \\cdot (3y)^k\n",
|
||
"$$\n",
|
||
"\n",
|
||
"---\n",
|
||
"\n",
|
||
"For $ x^7 \\cdot y^2 $, we have:\n",
|
||
"\n",
|
||
"$$\n",
|
||
"9 - k = 7 \\implies k = 2\n",
|
||
"$$\n",
|
||
"\n",
|
||
"---\n",
|
||
"\n",
|
||
"### Substitute $ k = 2 $:\n",
|
||
"\n",
|
||
"The coefficient of $ x^7 \\cdot y^2 $ is:\n",
|
||
"\n",
|
||
"$$\n",
|
||
"\\text{Coefficient} = \\binom{9}{2} \\cdot (2)^7 \\cdot (3)^2\n",
|
||
"$$\n",
|
||
"\n",
|
||
"### Step 2: Substitute $ k = 2 $\n",
|
||
"\n",
|
||
"The coefficient of $ x^7 y^2 $ is:\n",
|
||
"\n",
|
||
"$$\n",
|
||
"\\text{Coefficient} = \\binom{9}{2} \\cdot (2)^7 \\cdot (3)^2\n",
|
||
"$$\n",
|
||
"\n",
|
||
"---\n",
|
||
"\n",
|
||
"### Step 3: Compute Each Part\n",
|
||
"\n",
|
||
"1. **Binomial Coefficient:**\n",
|
||
" $$\n",
|
||
" \\binom{9}{2} = \\frac{9 \\cdot 8}{2} = 36\n",
|
||
" $$\n",
|
||
"\n",
|
||
"2. **Power of 2:**\n",
|
||
" $$\n",
|
||
" (2)^7 = 128\n",
|
||
" $$\n",
|
||
"\n",
|
||
"3. **Power of 3:**\n",
|
||
" $$\n",
|
||
" (3)^2 = 9\n",
|
||
" $$\n",
|
||
"\n",
|
||
"4. **Combine All:**\n",
|
||
" $$\n",
|
||
" \\text{Coefficient} = 36 \\cdot 128 \\cdot 9\n",
|
||
" $$\n",
|
||
"\n",
|
||
"---\n",
|
||
"\n",
|
||
"### Step 4: Simplify the Expression\n",
|
||
"\n",
|
||
"Simplify step-by-step:\n",
|
||
"\n",
|
||
"1. Multiply:\n",
|
||
" $$\n",
|
||
" 36 \\cdot 128 = 4608\n",
|
||
" $$\n",
|
||
"2. Multiply further:\n",
|
||
" $$\n",
|
||
" 4608 \\cdot 9 = 41472\n",
|
||
" $$\n",
|
||
"\n",
|
||
"This simplifies in terms of powers of 2 and 3:\n",
|
||
"$$\n",
|
||
"41472 = 2^9 \\cdot 3^4\n",
|
||
"$$\n",
|
||
"\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Number of derangements\n",
|
||
"Let $ D_n $ denote the number of derangements of $ n $ objects. For instance, $ D_3 = 2 $, because the derangements of $ 123 $ are $ 231 $ and $ 312 $. We will evaluate $ D_n $ for all positive integers $ n $ using the principle of inclusion–exclusion.\n",
|
||
"\n",
|
||
"---\n",
|
||
"\n",
|
||
"## **Theorem 2**\n",
|
||
"\n",
|
||
"The number of derangements of a set with $ n $ elements is:\n",
|
||
"\n",
|
||
"$$\n",
|
||
"D_n = n! \\left[ 1 - \\frac{1}{1!} + \\frac{1}{2!} - \\frac{1}{3!} + \\cdots + (-1)^n \\frac{1}{n!} \\right].\n",
|
||
"$$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 18,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAB0AAAAPCAYAAAAYjcSfAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACFUlEQVQ4Ea2U3zEEQRCH95QADhE4GRwyIANKBMiA8nT3psgAEfiTAUJwGSACXAbn+9r21N5a96Srervn1z3dPT29U81ms+q/eTQaDdsxwfrwQHy5gsbj8QBxqg5twZ/wKfhEoE3gFy3stuX7zLqPT+5Xlzb9LGM04RVyV0BCN+iLGPwU4A+u7z1sQYEjXcsbcJJFS0P4DX6Az/GdIuOkJjh2kYTRoEesDbaSeL32VKUQME9h4CZN8NlvAk19icUO/IpTtiDtBu6De7oKuYew8mvXSeB2o3Qp8UXSpAZ/Y2McvcM5i7Eb0wV+HVu7oZ7T1EUEfwUfIHvakV8I23gIH8AfsPd4j63Zbn29lkfYgtdgu+WdxmDF9ALMEUbbqGNOtPY88Rb2gqN/wYeww5Kk7x3YVABpLK8wBtP2dpGVPuB0qRGZCYfoc3eK+Q6+afjob/BIWO+3Q3bjyvWvpDhr8I67pq89pcZ4gS3K/3sRudfrGswlBfA3WUXOTSPrrDplV3BbWOH7CFvIX9QvSXH0l9hAlhOiR2X17viF/ooEnl3wxJ68TasCxJxEUhQHZxtZBqTeYSH5utj2OE1tS+HT5q+UE3yN3nyd0s/3IHx6PsIsHO/clE7KnWYAdP18baI4pCd6h8v0ghnPF628cugnYGfwOvrUpPE/AnSRCeKRTiNrn81sny0r/1/DJxLXa33sloXETHwDMNEqC36Gr8YAAAAASUVORK5CYII=",
|
||
"text/latex": [
|
||
"$\\displaystyle 265$"
|
||
],
|
||
"text/plain": [
|
||
"265"
|
||
]
|
||
},
|
||
"execution_count": 18,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# Example D_6\n",
|
||
"derangement_formula(6)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Cube graph"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 19,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Number of edges in a 4-cube: 32\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Example: Edges in a 4-cube\n",
|
||
"n = 4\n",
|
||
"print(f\"Number of edges in a {n}-cube: {count_edges_in_n_cube(n)}\")\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Other graps"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 20,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"text/plain": [
|
||
"{'Cube Graph': {'Vertices': 524288, 'Edges': 4980736},\n",
|
||
" 'Complete Graph': {'Vertices': 19, 'Edges': 171},\n",
|
||
" 'Bipartite Graph': 'Requires both partitions (n and m).',\n",
|
||
" 'Cycle Graph': {'Vertices': 19, 'Edges': 19},\n",
|
||
" 'Wheel Graph': {'Vertices': 19, 'Edges': 36}}"
|
||
]
|
||
},
|
||
"execution_count": 20,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# n (int): A parameter related to the graph type (e.g., vertices or dimension for cube).\n",
|
||
"n = 19\n",
|
||
"# m (int, optional): For bipartite graphs, the size of the second partition.\n",
|
||
"m = 2\n",
|
||
"\n",
|
||
"graph_properties_all_types = graph_properties_all(n)\n",
|
||
"graph_properties_all_types"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Min number sum (pigeonhole principle)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 21,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Minimum number of selections needed to guarantee a sum of 16: 5\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indtast tal og target:\n",
|
||
"numbers = [1, 3, 5, 7, 9, 11, 13, 15]\n",
|
||
"target = 16\n",
|
||
"\n",
|
||
"count = guaranteed_selection_count(target, numbers)\n",
|
||
"print(f\"Minimum number of selections needed to guarantee a sum of {target}: {count}\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Relation\n",
|
||
"**Reflexive:** A binary relation $ R $ on a set $ A $ is called *reflexive* if every element in $ A $ is related to itself. Formally, for every $ a \\in A $,\n",
|
||
"$$\n",
|
||
"(a, a) \\in R.\n",
|
||
"$$\n",
|
||
"\n",
|
||
"**Symmetric:** A binary relation $ R $ on a set $ A $ is *symmetric* if whenever $ a $ is related to $ b $, then $ b $ is also related to $ a $. Formally, for every $ a, b \\in A $,\n",
|
||
"$$\n",
|
||
"(a, b) \\in R \\implies (b, a) \\in R.\n",
|
||
"$$\n",
|
||
"\n",
|
||
"**Antisymmetric:** A binary relation $ R $ on a set $ A $ is *antisymmetric* if the only way for both $ a $ to be related to $ b $ and $ b $ to be related to $ a $ to hold simultaneously is when $ a = b $. Formally, for every $ a, b \\in A $,\n",
|
||
"$$\n",
|
||
"(a, b) \\in R \\text{ and } (b, a) \\in R \\implies a = b.\n",
|
||
"$$\n",
|
||
"\n",
|
||
"**Transitive:** A binary relation $ R $ on a set $ A $ is *transitive* if whenever $ a $ is related to $ b $ and $ b $ is related to $ c $, then $ a $ must also be related to $ c $. Formally, for every $ a, b, c \\in A $,\n",
|
||
"$$\n",
|
||
"(a, b) \\in R \\text{ and } (b, c) \\in R \\implies (a, c) \\in R.\n",
|
||
"$$\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 59,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"R1: {'reflexive': False, 'symmetric': False, 'antisymmetric': True, 'transitive': True}\n",
|
||
"R2: {'reflexive': False, 'symmetric': False, 'antisymmetric': True, 'transitive': False}\n",
|
||
"R3: {'reflexive': True, 'symmetric': True, 'antisymmetric': False, 'transitive': True}\n",
|
||
"R4: {'reflexive': True, 'symmetric': False, 'antisymmetric': True, 'transitive': True}\n",
|
||
"R5: {'reflexive': True, 'symmetric': False, 'antisymmetric': True, 'transitive': True}\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Indput her:\n",
|
||
"A = {'a','b','c','d'}\n",
|
||
"\n",
|
||
"R1 = {('a','a'),('a','b'),('a','c'),('a','d')}\n",
|
||
"results_R1 = check_relation_properties(A, R1)\n",
|
||
"print(\"R1:\", results_R1)\n",
|
||
"\n",
|
||
"R2 = {('a','b'),('b','c'),('c','d')}\n",
|
||
"results_R2 = check_relation_properties(A, R2)\n",
|
||
"print(\"R2:\", results_R2)\n",
|
||
"\n",
|
||
"R3 = {('a','a'),('b','b'),('c','c'),('d','d'),('a','d'),('d','a')}\n",
|
||
"results_R3 = check_relation_properties(A, R3)\n",
|
||
"print(\"R3:\", results_R3)\n",
|
||
"\n",
|
||
"R4 = {('a','a'),('b','b'),('c','c'),('d','d'),('d','c')}\n",
|
||
"results_R4 = check_relation_properties(A, R4)\n",
|
||
"print(\"R4:\", results_R4)\n",
|
||
"\n",
|
||
"R5 = {('a','a'),('b','b'),('c','c'),('d','d'),('a','b'),('a','c'),('a','d'), ('b','c'),('b','d'),('c','d')}\n",
|
||
"results_R5 = check_relation_properties(A, R5)\n",
|
||
"print(\"R5:\", results_R5)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Sets and subset sizes"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 61,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"50445672272782096667406248628\n",
|
||
"Number of subsets of A with size exactly 20: C(80, 20) = 50445672272782096667406248628\n",
|
||
"Number of subsets of A with no element greater than 60: 2^60 = 1152921504606846976\n",
|
||
"Number of subsets of A with an even number of elements: 2^(79) = 316912650057057350374175801344\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"n = 99\n",
|
||
"\n",
|
||
"# Question 1: How many subsets have size exactly 20?\n",
|
||
"# Closed form: C(80, 20)\n",
|
||
"count_size_49 = comb(n, 49)\n",
|
||
"\n",
|
||
"# Question 2: How many subsets have no element greater than 60?\n",
|
||
"# This is simply all subsets of {1, 2, ..., 60} since we can't pick anything > 60.\n",
|
||
"# Number of such subsets: 2^60\n",
|
||
"count_no_greater_than_60 = 2**60\n",
|
||
"\n",
|
||
"# Question 3: How many subsets have an even number of elements?\n",
|
||
"# For a set of size n, the number of even-sized subsets equals the number of odd-sized subsets, each is half of 2^n.\n",
|
||
"# This is because the binomial coefficients sum evenly. Thus, the count is 2^(n-1).\n",
|
||
"count_even_elements = 2**(n - 1)\n",
|
||
"\n",
|
||
"# Print the answers clearly\n",
|
||
"print(comb(99,50))\n",
|
||
"print(\"Number of subsets of A with size exactly 20: C(80, 20) =\", count_size_49)\n",
|
||
"print(\"Number of subsets of A with no element greater than 60: 2^60 =\", count_no_greater_than_60)\n",
|
||
"print(\"Number of subsets of A with an even number of elements: 2^(79) =\", count_even_elements)\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"604462909807314587353088 = $2^{79}$"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# gcd og lcm"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"Greatest common divider og lowest common multiple skrives som:"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 24,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAE8AAAAVCAYAAAAHIbMXAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAETUlEQVRYCe2Y0VHcMBCGDUMBB6mASwchVBDoAEgFQAcweYK3DHQAqSCBDgIVEOgAOghcB+T7dJKQjeHO3GVCJtkZeaXVarX6tVrLru7v76uy7O3t9cv2//oQnzZcZquC9vf3d2i+K0Svsoqfj3xE1qP0f6PD/YhPnmLGyJLoWIMtw3eDID5o69B2bPbgtg+Qn0XZVBl2jwqDC9Q3kQ0KWUX7jra+XEW5dWmpRXekveHQhyc23JxteFp36KRtcA3gxwoCeDSc/By+pDBRlAtUNkJdkE8o69RPk+6kPM51iZ0j6ofag7uIc4qg3CiTqF/DBFa/levHZ+QDeCDq9o1lLw7JLNq/gq9nYawg0+YH+GAuyg7g5Q5FcbVFZQvF75QEVIq4T/QlWdKfhH9h8ALzBOA0RN0F/KCqb6vKIrUuLHVG3sVeHsp8RtdzpC/itZ1y3gaDQig2Rnks3M1yR3O9oTtp04jO0VUY04cV/DOSulBne8xhpNfW25ww4iRevTkeT01S0WeUzZcGor6itkgtVceuYzMBc9sy6GeUvYenqG9RexBNYO8jY3cpOU09WK3V3OQNj63HYVynVtANIcsEbZFKd3fClknYgeaxJr2JAl9UmdA3pQi6/faZ88IL5IX2PK7jBoR4rQqeO/rsIJwxnAVumaKD5qFpk/nTOZrk3FKKzlT/Jkg24IJ3DV+lpEAY214c7wa2pQ2naJIvrJVZHjrVdlzyAIyaoA8pvn2+Ui6pe9ynSZsaw24GkHrKQXblhSEXpABcHGOfoJVBMLY9xnkt6XKSxKsveB6V7Aj1Z4lJ3FH1T6gL/FQogrGIMa9AOxTTgxF1ESfI4MV2k9nvRdYxFVwfR9pDz+Nfgu7wUeRcPY/tk4ThcGTgIZcUih5bI8QimFOhuOBaskYmiFIAj/Z36l5panfSoDF85A0dZY9+gfbLZNTGFOZDNQSc4BmCecKGlhfCCuPzFHfyT5AbeFbMb45uSzMuSF+bG624pGwPXW35VeWlvyR1jGLlN/DaVxcy8boVvBDu8DYSsNLxpOOkUkrOFRO4gy8GmLHmUC+2i8mONmkb3WWUHSNvLgaVoFf6M9IedtTPYzQiIffzz3U/+sIICsNUd2POc6d8i7aRTnpMMmFQp1yUSTaABbd9Bw+RmpW7VTxCzYhy552njCY/32o5inb6KigXO669Ni9dj+UpcjOvZvjVYoia/N+2aSJ355tOPfoxgJ6vb+nRx/lQPPqJjZTfkuP61RYZApOiz+Mq6F5uB+Us49pLY9B3U7TtmiXz+QXy/MmokLZr3Q7/8gDwWhAn/XeHjTVKb1I7r3k86+tTrvVxViQhd7z2lgvS7g+Tb233u5t49SOM+HBCAngs2AtiviO9xH1seNTSd+hLTLz6MazRIy1O4UKdIk/HzWu1RKywA21htJYbOoz9W1TFJ5/Q/CdZ7yOya/8ACJ03C0x8o5/C84X6F5XFpCx0DkJgAAAAAElFTkSuQmCC",
|
||
"text/latex": [
|
||
"$\\displaystyle \\left( 3, \\ 9594\\right)$"
|
||
],
|
||
"text/plain": [
|
||
"(3, 9594)"
|
||
]
|
||
},
|
||
"execution_count": 24,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"# Example\n",
|
||
"a = 123\n",
|
||
"b = 234\n",
|
||
"ab = 5292\n",
|
||
"\n",
|
||
"gcd(a,b), lcm(a,b)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": []
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Identity checker"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 25,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"Function 'f1' equals for all tested n.\n",
|
||
"Function 'f2' does NOT equal.\n",
|
||
"Function 'f3' does NOT equal.\n",
|
||
"Function 'f4' does NOT equal.\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"# Define the variable\n",
|
||
"n = Symbol('n', positive=True, integer=True)\n",
|
||
"'''\n",
|
||
"Indskriv dinne funktioner her:\n",
|
||
"'''\n",
|
||
"# Funktion som man er givet\n",
|
||
"def reference(n):\n",
|
||
" return n * (2**(n-1)) # Omskriv denne del\n",
|
||
"\n",
|
||
"# sum_{k=1}^{n} (n choose k)*k\n",
|
||
"f1 = lambda n: sum(\n",
|
||
" # Skriv funktion her\n",
|
||
" comb(n, k)*k\n",
|
||
" for k in\n",
|
||
" # Skriv range n løber mod husk at du skal plus med 1\n",
|
||
" range(1, n+1)\n",
|
||
" )\n",
|
||
"# sum_{k=0}^{n-1} (n choose k) (n choose k+1)\n",
|
||
"f2 = lambda n: sum(\n",
|
||
" comb(n, k)*comb(n, k+1)\n",
|
||
" for k in\n",
|
||
" range(n)\n",
|
||
" )\n",
|
||
"# sum_{k=1}^{n} 2^k\n",
|
||
"f3 = lambda n: sum(\n",
|
||
" 2**k\n",
|
||
" for k in\n",
|
||
" range(1, n+1)\n",
|
||
" )\n",
|
||
"# sum_{k=0}^{n-1} 2^k\n",
|
||
"f4 = lambda n: sum(\n",
|
||
" 2**k\n",
|
||
" for k in\n",
|
||
" range(n)\n",
|
||
" )\n",
|
||
"candidates = [f1,f2,f3,f4]\n",
|
||
"\n",
|
||
"# Check each candidate\n",
|
||
"for i, func in enumerate(candidates, start=1):\n",
|
||
" matches = test_formula(func,reference)\n",
|
||
" if matches:\n",
|
||
" print(f\"Function 'f{i}' equals for all tested n.\")\n",
|
||
" else:\n",
|
||
" print(f\"Function 'f{i}' does NOT equal.\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Check funktion for values\n",
|
||
""
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 26,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"# Skriv funktion ind\n",
|
||
"def f(n):\n",
|
||
" if n % 2 == 1:\n",
|
||
" return 1\n",
|
||
" else:\n",
|
||
" return 2 * f(n/2)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 27,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAADEAAAAVCAYAAADvoQY8AAAACXBIWXMAAA7EAAAOxAGVKw4bAAACZUlEQVRYCc2X7VHCQBCGwQoylhA7AOlAOkA6EDqA8Rf81Q7QErAD7cCBDqADkQ7wfcIFN1+YXOIMO3Nkd29z++7t7uVoHQ6Hlh2z2Sy08qXxefiuWobm8/lEYseoLpENHc4TtjY7DWlioEdPz2mkcD+SA7GPRoe8lP7D6Bphy/qSHZu91/MlckwQSlGgscorHekXab10S41BWl9XruJLtiuNAJ9xOT0pokV6OxXpSLpVWi/5QcNmJ8ekmsrDF3jBfQpieEpN0veNxH5S9W9SJV8OL7iDK/3QC9sCaJ/SD2TzjrGxyc2cmfdhfXyBe9imDsXQJImGjlFIvxRPoBA27BhBvaFokqr6kj2bGdITtxqbIjAyvNfc8RQ41uCd5HWRfR29hy9wR0FQJrsi51qYLOw1yADHaqixcXqxzZGHL3BHQVyLAWSGtCinU1/PqcZWgyYnM9CrZNsnR63nr9by8UVPBPERW+Samkv0ipzRC2SFACitpsjHV5QAgiAlmR11uxzomcmSdOwAwbBIbarhC9w7ggAQdZ4gB55TKzPnDFngdPVwQBJrlBWq+jLrsolbguCk6ZkJy1L/3JMSmZJM/XLMsgEtN/+tZ97XHZMyVMpXaqGu5DXfiY4YgFLnGZKeea4Y9gTLXABlFx/TXfGZEswsnKMo6yt+1fkcR/8lFMiGYBq4wA20TnQpq7vWX+/LTwju9AVwHEdY48lV3isLHj45NTnRjhdAOeaLzJ+NoibG9izpXfrm66xRQ5MOJ3ijmwSNHRONxT3Kl0Za9Nn35YrvgfO3cmztuTqbWN2l8cI4AafF9QPv0hkFUOhpSwAAAABJRU5ErkJggg==",
|
||
"text/latex": [
|
||
"$\\displaystyle \\left( 8, \\ 8\\right)$"
|
||
],
|
||
"text/plain": [
|
||
"(8, 8)"
|
||
]
|
||
},
|
||
"execution_count": 27,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"a = 232\n",
|
||
"b = 212321\n",
|
||
"(f(a*b)),(f(a)*f(b))"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 28,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"for i in range(1,10000):\n",
|
||
" if f(i) == 17:\n",
|
||
" print(\"True\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Løs sum funktioner"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 29,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAACQAAAAPCAYAAACMa21tAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACFElEQVRIDaWV7VEbMRCGNYwLcJIKuHTgJBXEdBDoIKQD8tP+x5gOoASgA5IKAu4AOoChA/M88q1Ho+iGY9iZPe3HK2l3tdKlzWaT3suLxaKDj+Hpa2uBmdUY58Gd9kkqaLlcrnr1kfEzvML2UECGxBmOcxl8C/OM/UPv+Is8RV73urL0xc8uIEB36KeM1zr6SXeMB/BrQX1jyh+4hZtj/w0HPfWCSYh3P/d9znbLRLks932jlCvsN7W91sGsaps6do/yvPShX5V6Le/lqFI6ZIwS9qY8/OM776tV2mtZXIs88l8tx5AtArKsUcoSG0egf5DYNB9zCcBmP56WtjHyZET2rvNxzGKBYc0OecZY9k64E/ZjFJv5EyzWHsonZIVis21TYWhQ3ISGq2myOnFja4BrXRLAGWzAspcnn0IcWT2p1s1kFLGwGdt33rr/CLu3dpc8sm0h1mcjGVCrd/RJUT3fpbFkE0fvjZ0jviO4bq+ItnUsYXvLBj9YvJkke93AvndDNI0js2SWuqaoULP8NZjNTMB1dkdSYb6iR5KlK+/D/HUEdIVXcE0+52uAQxvU+FijWSHAF6zlL6kmGzonnQMCdIHhidFyZ0I2kyP459ay/Z1g38BDZY/shxLwX5ebt1jzpJd9nNMkHIxWw5fV/5JN7PgdPb8PyAnZn6T9dKveILEG03y5nQu7RwTlUVnNfWw5iRcTbGNN0pw+ZwAAAABJRU5ErkJggg==",
|
||
"text/latex": [
|
||
"$\\displaystyle 0.75$"
|
||
],
|
||
"text/plain": [
|
||
"0.75"
|
||
]
|
||
},
|
||
"execution_count": 29,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"f = lambda n: sum(\n",
|
||
" # Indskriv funktion\n",
|
||
" 1/(k*(k+1))\n",
|
||
" for k in\n",
|
||
" # Indskriv range\n",
|
||
" range(1, n+1)\n",
|
||
" )\n",
|
||
"\n",
|
||
"\n",
|
||
"f(3)\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 30,
|
||
"metadata": {},
|
||
"outputs": [],
|
||
"source": [
|
||
"for n in range(1,1000):\n",
|
||
" for k in range(n):\n",
|
||
" if comb(n,k) != comb(n,n-k):\n",
|
||
" print(f\"False when k = {k} and n = {n}\")"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Terning"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 31,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAAkAAAAOCAYAAAD9lDaoAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA3UlEQVQoFW2RvRGCQBCFD7UAxhIgNXI0J8AO1BK0BEJItQMMTTU0w4DE1A6gBMYOzu+dg4PIzrzZ27dvf+7Os9aaLMsCY0wCZAvQgAT+KWIMJMghtlEU3cCpLMsZ3Bn/IK5HBAewB1+jQF1f4CJSohhUJHwRHbtz9uEDiRTUBKocMt9o8SGkaVoBUtaN+6um6xxSF3I31rgh08JXxEeX7I9iRA6KLv/TicodlVP8qtt+0gYk1pxD/KbDaa/P4iS06BLffk2rU2HjMV/qAui9+hZTGGqcBBJqn765D34Dzrdx4/BA7EwAAAAASUVORK5CYII=",
|
||
"text/latex": [
|
||
"$\\displaystyle 2$"
|
||
],
|
||
"text/plain": [
|
||
"2"
|
||
]
|
||
},
|
||
"execution_count": 31,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"from random import randint\n",
|
||
"spørgsmål_mængden = 6\n",
|
||
"\n",
|
||
"randint(0,spørgsmål_mængden)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 32,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"data": {
|
||
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAAoAAAAOCAYAAAAWo42rAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAz0lEQVQoFXWS4Q2CMBCFhQkIbqAjqBvgBsoGOkf/GUbQFXQENjAyAhtA2AC/V3tGG2hyeXdfH71LSzKO48KWc64KeYeuiQrWiiVmBLyoL+hDG2iGiO3J2zTAM5qZKbAB1UdX1d6IHolGIFpP6kKnm7EA9JFJpZ8PLdIwy4TnD+U6MQ9IM82tb+s5g/GlTpyazQzWrdOM1lL3Fi9jn3tktyZWsYvaTqzteu7A7YRxA2vU1RtJboAePZiZXG1L4iT2+9ba0E8xEPopdoTe3r/YGx/SQ0OZAIYmAAAAAElFTkSuQmCC",
|
||
"text/latex": [
|
||
"$\\displaystyle 0$"
|
||
],
|
||
"text/plain": [
|
||
"0"
|
||
]
|
||
},
|
||
"execution_count": 32,
|
||
"metadata": {},
|
||
"output_type": "execute_result"
|
||
}
|
||
],
|
||
"source": [
|
||
"floor(0)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 63,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"ename": "TypeError",
|
||
"evalue": "'Mul' object cannot be interpreted as an integer",
|
||
"output_type": "error",
|
||
"traceback": [
|
||
"\u001b[31m---------------------------------------------------------------------------\u001b[39m",
|
||
"\u001b[31mTypeError\u001b[39m Traceback (most recent call last)",
|
||
"\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[63]\u001b[39m\u001b[32m, line 2\u001b[39m\n\u001b[32m 1\u001b[39m n = symbols(\u001b[33m'\u001b[39m\u001b[33mn\u001b[39m\u001b[33m'\u001b[39m)\n\u001b[32m----> \u001b[39m\u001b[32m2\u001b[39m \u001b[43mcomb\u001b[49m\u001b[43m(\u001b[49m\u001b[32;43m3\u001b[39;49m\u001b[43m*\u001b[49m\u001b[43mn\u001b[49m\u001b[43m,\u001b[49m\u001b[43mn\u001b[49m\u001b[43m)\u001b[49m\n",
|
||
"\u001b[31mTypeError\u001b[39m: 'Mul' object cannot be interpreted as an integer"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"n = symbols('n')\n",
|
||
"comb(3*n,n)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": null,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"\n",
|
||
"38808\n",
|
||
"39203\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"count = 0\n",
|
||
"a = 199\n",
|
||
"b = 197\n",
|
||
"for i in range(1,a*b):\n",
|
||
" if gcd(a*b, i) == 1:\n",
|
||
" count += 1\n",
|
||
"print()\n",
|
||
"print(count)\n",
|
||
"38808\n",
|
||
"39203\n",
|
||
"print(a*b)\n",
|
||
"\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 80,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"38807\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"print(a*b-a-b)"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 82,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"2544765851052936426322609680343243245917029283699751882384\n",
|
||
"2544765851052936426322609680343243245917029283699751882384\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"print(comb(99,50)*comb(99,49))\n",
|
||
"\n",
|
||
"print(comb(99,49)*comb(99,49))\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "code",
|
||
"execution_count": 91,
|
||
"metadata": {},
|
||
"outputs": [
|
||
{
|
||
"name": "stdout",
|
||
"output_type": "stream",
|
||
"text": [
|
||
"1740\n",
|
||
"3654828866470766307523200\n",
|
||
"36548288664598635724800000\n",
|
||
"18274144332299317862400000\n",
|
||
"\n",
|
||
"1827414433235383153761600\n",
|
||
"331566074765238823295385600000\n"
|
||
]
|
||
}
|
||
],
|
||
"source": [
|
||
"print(4*comb(30,2))\n",
|
||
"print((factorial(30))/(10*factorial(20))+factorial(30)/(20*factorial(10)))\n",
|
||
"print(factorial(30)/(2*factorial(10)))\n",
|
||
"print(factorial(30)/(4*factorial(10)))\n",
|
||
"print()\n",
|
||
"print((factorial(30))/(20*factorial(20))+factorial(30)/(40*factorial(10)))\n",
|
||
"print(factorial(30)/(8*10**2))"
|
||
]
|
||
}
|
||
],
|
||
"metadata": {
|
||
"kernelspec": {
|
||
"display_name": "Python 3",
|
||
"language": "python",
|
||
"name": "python3"
|
||
},
|
||
"language_info": {
|
||
"codemirror_mode": {
|
||
"name": "ipython",
|
||
"version": 3
|
||
},
|
||
"file_extension": ".py",
|
||
"mimetype": "text/x-python",
|
||
"name": "python",
|
||
"nbconvert_exporter": "python",
|
||
"pygments_lexer": "ipython3",
|
||
"version": "3.13.7"
|
||
}
|
||
},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 2
|
||
}
|