diff options
Diffstat (limited to 'Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter4.ipynb')
| -rwxr-xr-x | Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter4.ipynb | 743 |
1 files changed, 743 insertions, 0 deletions
diff --git a/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter4.ipynb b/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter4.ipynb new file mode 100755 index 00000000..91c1e06d --- /dev/null +++ b/Discrete_Mathematics_and_its_Applications_by_Kenneth_H.Rosen/chapter4.ipynb @@ -0,0 +1,743 @@ +{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 03: Page 239"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "The quotient when 101 is divided by 11 is 9 = 101 div 11 and the remainder is 2 = 101 mod 11\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To find the quotient and remainder \n",
+ "dividend=101\n",
+ "divisor=11\n",
+ "quotient=dividend/divisor #To find quotient\n",
+ "remainder=dividend%divisor #To find remainder\n",
+ "dividend=(divisor*quotient)+remainder\n",
+ "print \"The quotient when\",dividend,\"is divided by\",divisor,\"is\",quotient,\"=\",dividend,\"div\",divisor,\"and the remainder is\",remainder,\"=\",dividend,\"mod\",divisor\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 04: Page 240"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "The quotient when -11 is divided by 3 is -4 = -11 div 3 and the remainder is 1 = -11 mod 3\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To find the quotient and remainder\n",
+ "dividend=-11\n",
+ "divisor=3\n",
+ "quotient=dividend/divisor\n",
+ "remainder=dividend%divisor\n",
+ "dividend=(divisor*quotient)+remainder\n",
+ "print \"The quotient when\",dividend,\"is divided by\",divisor,\"is\",quotient,\"=\",dividend,\"div\",divisor,\"and the remainder is\",remainder,\"=\",dividend,\"mod\",divisor\n",
+ "\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 01: Page 246"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "enter a number: 101011111\n",
+ "351\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To convert binary to decimal equivalent\n",
+ "binary_num= raw_input('enter a number: ')\n",
+ "decimal = 0\n",
+ "for digit in binary_num:\n",
+ " decimal = decimal*2 + int(digit)\n",
+ "\n",
+ "print decimal\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 03: Page 247"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {
+ "collapsed": false,
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "enter a number: 2AE0B\n",
+ "The conversion of 2AE0B to hexadeimal is 175627\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To convert decimal to hexadecimal\n",
+ "dec= raw_input('enter a number: ')\n",
+ "\n",
+ "print \"The conversion of\",dec,\"to hexadeimal is\",int(dec,16)\n",
+ "\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 04: Page 247"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter a number12345\n",
+ "The decimal number 12345 is converted to its octal equivalent : 3 0 0 7 1\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute decimal to octal\n",
+ "numbers= []\n",
+ "dec=input(\"Enter a number\");\n",
+ "num=dec\n",
+ "while dec!=0:\n",
+ " \n",
+ " rem=dec%8\n",
+ " dec=dec/8\n",
+ " numbers.append(rem)\n",
+ "print \"The decimal number\",num,\"is converted to its octal equivalent : \",\n",
+ "for i in reversed(numbers):\n",
+ " print i,\n",
+ " \n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 05: Page 248"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the decimal number which is to be converted to hexadecimal177130\n",
+ "The hexadecimal equivalent of decimal 177130 is 0 2 B 3 E A\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To convert Decimal to hexadecimal\n",
+ "num=[]\n",
+ "def ChangeHex(n): #function to convert\n",
+ " if (n < 0):\n",
+ " num.append(\"\")\n",
+ " elif (n<=1):\n",
+ " num.append(n)\n",
+ " else: #for numbers greater than 9\n",
+ " x =(n%16)\n",
+ " if (x < 10):\n",
+ " num.append(x) \n",
+ " if (x == 10):\n",
+ " num.append(\"A\")\n",
+ " if (x == 11):\n",
+ " num.append(\"B\")\n",
+ " if (x == 12):\n",
+ " num.append(\"C\")\n",
+ " if (x == 13):\n",
+ " num.append(\"D\")\n",
+ " if (x == 14):\n",
+ " num.append(\"E\")\n",
+ " if (x == 15):\n",
+ " num.append(\"F\")\n",
+ " ChangeHex( n / 16 )\n",
+ "dec_num=input(\"Enter the decimal number which is to be converted to hexadecimal\");\n",
+ "ChangeHex(dec_num)\n",
+ "print \"The hexadecimal equivalent of decimal\",dec_num,\"is\",\n",
+ "for i in reversed(num):\n",
+ " print i,\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 06: Page 249"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter a decimal number241\n",
+ "\n",
+ "The binary equivalent of decimal 241 is 1 1 1 1 0 0 0 1\n"
+ ]
+ }
+ ],
+ "source": [
+ "#Compute Decimal to Binary\n",
+ "array=[]\n",
+ "def conv(n):\n",
+ " if n==0:\n",
+ " print ''\n",
+ " else:\n",
+ " array.append(str(n%2)) #to compute remainder and append it to the result\n",
+ " return conv(n/2) \n",
+ "dec_num=input(\"Enter a decimal number\")\n",
+ "conv(dec_num)\n",
+ "print \"The binary equivalent of decimal\",dec_num,\"is\",\n",
+ "for i in reversed(array):\n",
+ " print i,\n",
+ "\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 06: Page 249"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "enter the first number: 1110\n",
+ "enter the second number: 1011\n",
+ "The sum of binary numbers 1110 and 1011 is 11001\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute the binary addition\n",
+ "def binAdd(bin1, bin2): #function to add two binary numbers\n",
+ " if not bin1 or not bin2:#checks if both the numbers are binary\n",
+ " return '' \n",
+ "\n",
+ " maxlen = max(len(bin1), len(bin2))\n",
+ "\n",
+ " bin1 = bin1.zfill(maxlen) #zfill fills with zero to fill the entire width\n",
+ " bin2 = bin2.zfill(maxlen)\n",
+ "\n",
+ " result = ''\n",
+ " carry = 0\n",
+ "\n",
+ " i = maxlen - 1\n",
+ " while(i >= 0):\n",
+ " s = int(bin1[i]) + int(bin2[i])#adding bit by bit\n",
+ " if s == 2: #1+1\n",
+ " if carry == 0:\n",
+ " carry = 1\n",
+ " result = \"%s%s\" % (result, '0')\n",
+ " else:\n",
+ " result = \"%s%s\" % (result, '1')\n",
+ " elif s == 1: # 1+0\n",
+ " if carry == 1:\n",
+ " result = \"%s%s\" % (result, '0')\n",
+ " else:\n",
+ " result = \"%s%s\" % (result, '1')\n",
+ " else: # 0+0\n",
+ " if carry == 1:\n",
+ " result = \"%s%s\" % (result, '1')\n",
+ " carry = 0 \n",
+ " else:\n",
+ " result = \"%s%s\" % (result, '0') \n",
+ "\n",
+ " i = i - 1;\n",
+ "\n",
+ " if carry>0:\n",
+ " result = \"%s%s\" % (result, '1')\n",
+ " return result[::-1]\n",
+ "bin1 = raw_input('enter the first number: ')\n",
+ "bin2 = raw_input('enter the second number: ')\n",
+ "print \"The sum of binary numbers\",bin1,\"and\",bin2,\"is\",binAdd(bin1,bin2)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 02: Page 258"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the number for which the prime factors have to be found100\n",
+ "[2, 2, 5, 5]\n"
+ ]
+ }
+ ],
+ "source": [
+ "#to find the prime factors\n",
+ "\n",
+ "def prime_factors(n):\n",
+ " i = 2\n",
+ " factors = []\n",
+ " while i * i <= n:\n",
+ " if n % i: #modulp division to check of the number is prime or not\n",
+ " i += 1\n",
+ " else:\n",
+ " n //= i\n",
+ " factors.append(i) #append those numbers which readily divides the given number\n",
+ " if n > 1:\n",
+ " factors.append(n)\n",
+ " return factors\n",
+ "number=input(\"Enter the number for which the prime factors have to be found\");\n",
+ "a=prime_factors(number)\n",
+ "print a\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 03: Page 258"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the number101\n",
+ "101 is prime\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To say if a number is prime or not\n",
+ "globals() ['count']=0\n",
+ "n=input(\"Enter the number\");\n",
+ "for i in range(2,n):#number thats not divisible by other than one and itself. so from 2 to n (n-1 in python for loop)\n",
+ " if n%i==0:\n",
+ " count=count+1\n",
+ " num=i\n",
+ "if count==0:\n",
+ " print n,\"is prime\" \n",
+ "else:\n",
+ " print n,\"is not prime because its divisible by\",num\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 04: Page 259"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the number for which the prime factors have to be found7007\n",
+ "[7, 7, 11, 13]\n"
+ ]
+ }
+ ],
+ "source": [
+ "#to find the prime factors\n",
+ "\n",
+ "def prime_factors(n):\n",
+ " i = 2\n",
+ " factors = []\n",
+ " while i * i <= n:\n",
+ " if n % i: #modulp division to check of the number is prime or not\n",
+ " i += 1\n",
+ " else:\n",
+ " n //= i\n",
+ " factors.append(i) #append those numbers which readily divides the given number\n",
+ " if n > 1:\n",
+ " factors.append(n)\n",
+ " return factors\n",
+ "number=input(\"Enter the number for which the prime factors have to be found\");\n",
+ "a=prime_factors(number)\n",
+ "print a\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 10: Page 263"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the first number24\n",
+ "Enter the second number36\n",
+ "GCD( 24 , 36 ) is 12\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute GCD\n",
+ "def gcd(a,b):#fuction computes gcd\n",
+ " if b > a:\n",
+ " return gcd(b,a)\n",
+ " r = a%b\n",
+ " if r == 0:\n",
+ " return b\n",
+ " return gcd(r,b)\n",
+ "n1=input(\"Enter the first number\");\n",
+ "n2=input(\"Enter the second number\");\n",
+ "print \"GCD(\",n1,\",\",n2,\") is\",gcd(n1,n2)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 11: Page 263"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the first number17\n",
+ "Enter the second number22\n",
+ "GCD( 17 , 22 ) is 1\n"
+ ]
+ }
+ ],
+ "source": [
+ "#To compute GCD\n",
+ "def gcd(a,b):#fuction computes gcd\n",
+ " if b > a:\n",
+ " return gcd(b,a)\n",
+ " r = a%b\n",
+ " if r == 0:\n",
+ " return b\n",
+ " return gcd(r,b)\n",
+ "n1=input(\"Enter the first number\");\n",
+ "n2=input(\"Enter the second number\");\n",
+ "print \"GCD(\",n1,\",\",n2,\") is\",gcd(n1,n2)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 16: Page 268"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the first number414\n",
+ "Enter the second number662\n",
+ "gcd( 414 , 662 )is 2\n"
+ ]
+ }
+ ],
+ "source": [
+ "#to find gcd using euclidean algorithm\n",
+ "def gcd(a,b):#euclidean algithm definition\n",
+ " x=a\n",
+ " y=b\n",
+ " while y!=0:\n",
+ " r=x%y\n",
+ " x=y\n",
+ " y=r\n",
+ " print \"gcd(\",a,\",\",b,\")is\",x\n",
+ "num1=input(\"Enter the first number\");\n",
+ "num2=input(\"Enter the second number\");\n",
+ "gcd(num1,num2)\n"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "collapsed": true
+ },
+ "source": [
+ "# 04:NUMBER THEORY AND CRYPTOGRAPHY"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example 17: Page 270"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 1,
+ "metadata": {
+ "collapsed": false
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Enter the first number252\n",
+ "Enter the second number198\n",
+ "gcd( 252 , 198 )is 18\n"
+ ]
+ }
+ ],
+ "source": [
+ "#to find gcd using euclidean algorithm\n",
+ "def gcd(a,b):#euclidean algithm definition\n",
+ " x=a\n",
+ " y=b\n",
+ " while y!=0:\n",
+ " r=x%y\n",
+ " x=y\n",
+ " y=r\n",
+ " print \"gcd(\",a,\",\",b,\")is\",x\n",
+ "num1=input(\"Enter the first number\");\n",
+ "num2=input(\"Enter the second number\");\n",
+ "gcd(num1,num2)\n"
+ ]
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 2",
+ "language": "python",
+ "name": "python2"
+ },
+ "language_info": {
+ "codemirror_mode": {
+ "name": "ipython",
+ "version": 2
+ },
+ "file_extension": ".py",
+ "mimetype": "text/x-python",
+ "name": "python",
+ "nbconvert_exporter": "python",
+ "pygments_lexer": "ipython2",
+ "version": "2.7.9"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 0
+}
|