{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Zahlentheorie\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Python kann von Haus aus mit großen Ganzzahlen (die mehr als 64-Bit haben) umgehen." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "89986999899989998999900079990979854553444233312220111999874222099977775555333411098866665554444333322221111" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = 900000000000000000000000000010000000000000000000000001\n", "y = 99985555444433332222111199988866665554444333322221111\n", "x*y" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "130001000100010000999200110200010010001000100010002" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x % y" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zahlentheorie mit SymPy\n", "\n", "Das Submodul [sympy.ntheory](http://docs.sympy.org/latest/modules/ntheory.html) (engl. \"number theory\") beinhaltet zahlentheoretiche Funktionen." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Primzahltest" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sympy.ntheory import isprime, nextprime\n", "isprime(20150407)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "20150411" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nextprime(20150407)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Struktur der Primzahlen bis 2000:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " oo o o o o o o o o o o o o o o o o o o o o \n", " o o o o o o o o o o o o o o o \n", " o o o o o o o o o o o o o o o \n", "o o o o o o o o o o o o o o \n", " o o o o o o o o o o o o \n", "o o o o o o o o o o o o o o \n", " o o o o o o o o o o \n", " o o o o o o o o o o o o o \n", "o o o o o o o o o o o o o \n", " o o o o o o o o o o o \n", " o o o o o o o o o o o o \n", "o o o o o o o o o o o \n", " o o o o o o o o o o o o o \n", " o o o o o o o o o o o o \n", " o o o o o o o o o \n", "o o o o o o o o o o o \n", " o o o o o o o o o o \n", "o o o o o o o o o o o \n", " o o o o o o o o o o o o \n", " o o o o o o o o o o o \n", "o o o o o o o o o o o o \n", " o o o o o o o o o o o \n", " o o o o o o o o \n", " o o o o o o o o o o o \n", " o o o o o o o o o o \n" ] } ], "source": [ "from __future__ import print_function\n", "zeilen, spalten = 25, 80\n", "for z in range(zeilen):\n", " for s in range(spalten):\n", " n = (s + 1) + spalten * (z)\n", " print(\"o\" if isprime(n) else \" \", end=\"\")\n", " print()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Faktorisierung in $\\mathbb{Z}$\n", "\n", "Das Ergebnis ist ein `dict`, wobei die Schlüssel die Primzahlen und die Werte die Vielfachheit sind." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "{13: 1, 1051: 1, 4339: 3}" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sympy.ntheory import factorint\n", "factorint(1116130609622197)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "{13: 1, 1051: 1, 4339: 3}" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fc2 = factorint(1116130609622197)\n", "fc2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Check" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1116130609622197" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z = 1\n", "for primzahl, vielfachheit in fc2.items():\n", " z *= primzahl**vielfachheit\n", "z" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Chinesischer Restsatz" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(59, 78)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sympy.ntheory.modular import crt\n", "crt([2, 3, 13], [1, 2, 7])" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[1, 2, 7]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[59 % m for m in [2, 3, 13]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Partitionen von n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "P( 0) = 1\n", "P( 100) = 190569292\n", "P( 200) = 3972999029388\n", "P( 300) = 9253082936723602\n", "P( 400) = 6727090051741041926\n", "P( 500) = 2300165032574323995027\n", "P( 600) = 458004788008144308553622\n", "P( 700) = 60378285202834474611028659\n", "P( 800) = 5733052172321422504456911979\n", "P( 900) = 415873681190459054784114365430\n", "P( 1000) = 24061467864032622473692149727991\n", "P( 1100) = 1147240591519695580043346988281283\n", "P( 1200) = 46240102378152881298913555099661657\n", "P( 1300) = 1607818855017534550841511230454411672\n", "P( 1400) = 49032194652550394774839040691532998261\n", "P( 1500) = 1329461690763193888825263136701886891117\n", "P( 1600) = 32417690376154241824102577250721959572183\n", "P( 1700) = 717802041964941442478681516751205185010007\n", "P( 1800) = 14552716211005418005132948684850541312590849\n", "P( 1900) = 272089289788583262011466359201428623427767364\n", "P( 2000) = 4720819175619413888601432406799959512200344166\n" ] } ], "source": [ "from sympy.ntheory import npartitions\n", "for i in range(0, 2001, 100):\n", " np = npartitions(i)\n", " print(\"P(%5d) = %d\" % (i, np))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lengendre-Symbol" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sympy.ntheory.residue_ntheory import legendre_symbol\n", "legendre_symbol(49, 997)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "-1" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "legendre_symbol(7, 997)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Möbiusfunktion" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sympy.ntheory import mobius\n", "mobius(11111222227777)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "{7: 1, 19: 1, 23: 1, 103: 1, 1753: 1, 20117: 1}" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factorint(11111222227777)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mobius(11111222227779)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "{3: 6, 167: 1, 91267853: 1}" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factorint(11111222227779)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Endliche Körper\n", "\n", "Welche Punkte in $\\mathbb{F}_7 \\times \\mathbb{F}_7$ liegen am Einheitskreis, also erfüllen $x^2 + y^2 = 1$?" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0:1\n", "0:6\n", "1:0\n", "2:2\n", "2:5\n", "5:2\n", "5:5\n", "6:0\n" ] } ], "source": [ "from itertools import product\n", "\n", "F7 = range(7)\n", "\n", "for x, y in product(F7, F7):\n", " if (x**2 + y**2) % 7 == 1:\n", " print(\"%d:%d\" % (x, y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Bemerkung:* Das ist natürlich nicht wirklich $\\mathbb{F}_7$, denn wir brauchen die Modulo-Operation.\n", "Eine gute Aufgabe wäre, eine Klasse für $\\mathbb{F}_p$ zu implementieren,\n", "dessen Elemente (also, man braucht auch eine Klasse für die Elemente) die Basisoperationen beherrschen." ] } ], "metadata": { "kernelspec": { "display_name": "Anaconda (Python 3)", "language": "python", "name": "anaconda3" }, "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.5.1" } }, "nbformat": 4, "nbformat_minor": 0 }