Entries Tagged 'Mathematics' ↓
April 9th, 2008 — Mathematics, python
I was looking at a few interesting algorithms to figure out whether a given number was a prime, all because I wanted the fastest solutions possible while solving project euler sums involving prime numbers. And after that session, the sum is still not over and might never be as I have gotten around to post on this blog, the stuff I’ve gathered.The AKS algorithm is of extreme academic importance but has horrible speeds and hence is of no use to me whose main aim to get prime number with utter ease.
I then looked at the Miller-Rabin algorithm and then moved to try out an implementation on my own. I cheated by trying to look at implementations on the cookbook and understood nothing. So it was back to me to figure out something. The algorithm goes like this:
To check if “n” is prime, “n” should obviously be 2 or odd. Forget 2, because if you don’t, I will call you names ( and who needs miller-rabin to prove if 2 is prime ? ).
Since n is odd, n-1 is even. Try expressing n - 1 as 
. It seems relatively simple. Here is the code to do that:
#!/usr/bin/python
#Miller-Rabin Primality Test.
#Author: Shriphani Palakodety a.k.a PSP#Now comes one of the world’s fastest primality tests:
def twoPower(n):
factors = []
s = 0
while n > 0:
if n % 2 == 0:
factors.append(0)
n = n / 2
s += 1
else:
factors.append(n)
d = n
break
return s, d
Once that is done, we need to generate a random number which lies in the range ![\left[1, n - 1\right]](http://www.codecogs.com/eq.latex?\left[1,&space;&space;n&space;-&space;1\right])
. Here is the code to do that:
#!/usr/bin/pythonfrom random import randint
def randGen(n):
return randint(1, n)
Ok, I agree there was no need for that snippet. Let us move on anyway. The crux of this algorithm lies in the following statement:
if 
and 
for all r in the range 
] then return composite.
Well, this is quite easy to implement in Python:
#!/usr/bin/env python
#Modulo Check
def moduloCheck(rand_int, odd_no, n):
if rand_int ** odd_no == 1 % n:
for i in range(0, n):
if rand_int ** ( ( 2**i) * odd_no ) == -1 % n:
continue
else:
break
return "Prime"
else:
return "Prime"
return "Composite"
Now comes the trouble:
number = 73n = twoPower
(number-
1)[0]
odd_no = twoPower(number - 1)[1]
rand_int = randGen(n - 1)
print moduloCheck(rand_int, odd_no, n)
Have a look at what I get:
shriphani@psp-laptop:~/project_euler$ python miller_rabin.py
Prime
shriphani@psp-laptop:~/project_euler$ python miller_rabin.py
Prime
shriphani@psp-laptop:~/project_euler$ python miller_rabin.py
Prime
shriphani@psp-laptop:~/project_euler$ python miller_rabin.py
Composite
BOOM !
The trick to avoiding such problems is to just run the moduloCheck function as many times as possible and if we get more Primes than Composites, then the number is Prime, else Composite 
I then decided to create a parameter “k” which would determine the number of times the moduloCheck function should run. Then I implemented a counter to check the frequency of the strings - “Prime” and “Composite” thrown out by the script. Here is the code:
k = randint
(1, n
)
def freqCheck(k, odd_no, n):
freq_list = []
for i in range(0, k):
freq_list.append(moduloCheck(randGen(n - 1), odd_no, n))
if freq_list.count("Prime") > freq_list.count("Composite"):
return "Prime"
else:
return "Composite"
So, the entire script looks like this: http://shriphani.com/scripts/miller-rabin.html
March 31st, 2008 — Mathematics, python
I am very sorry Stanford - you won’t have the honor to call yourself the breeding place of the next biggest character in the history of Computer Science. I feel extremely sorry to being you this bad news.
Anyway, in a bout of stupidity (induced by an intense feeling to optimize a stupid script of no apparent worth) I ended up rewriting problem 16 on projecteuler.net using memoization. Well, I guess I am going to be a computer scientist right ?
Well, have a look at it:
#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP
cache = {}
cache[ 2 ** 0] = 1
def cachePopulator():
for i in range(1, 1001):
if cache.has_key(2 ** (i - 1)):
cache[2 ** i]= 2 * cache[2 ** (i-1)]
cachePopulator()
cachestring = str(cache[2 ** 1000])
cache_string_list = [ int(x) for x in cachestring ]
print sum(cache_string_list)
Next comes a dose of creativity. This is my algorithm to generate the powerset of a given set. A powerset of a set is basically the set whose elements are subsets of a given set. Now, if the cardinal number of a set is “n”, then it should have 
subsets. How? Simple combinatrics.
Subsets can be considered as selections. From a set of n elements, we end up selecting 0, 1, 2 ….. n elements. Hence we have something of the form:
Now, how do we obtain the powerset of a given set ? I came up with an idea to use binary numbers to get to the answer. Consider that we have a set composed of elements a, b and c.
Let i be allowed to increment from 0 to . Now observe the magic of the binary system:
| i |
binary |
Element(s) |
| 0 |
000 |
- |
| 1 |
001 |
c |
| 2 |
010 |
b |
and so on. So, depending on the location of 1 in the binary number, we accordingly pick an element from the set and get to the solution. Well, here is the code needed to generate a list containing the digits of the corresponding binary number as over here we need to obtain the indices of 1.
#!/usr/bin/env python
#Convert a number in the decimal system to the binary system
#file: decimaltobinary.py
def converter(i, num_length):
b = ”
while i > 0:
j = i & 1
b = str(j) + b
i >>= 1
bin_string = [ int(x) for x in str(b)]
reqd_bin_string = [0] * ( num_length - len(bin_string) ) + bin_string
return reqd_bin_string
Then comes the code to generate the powerset:
#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP
#file: powerset.py
import decimaltobinary
def powerSetMaker(set_name):
powerset = []
for i in range(2 ** (len(set_name))):
bin_list = decimaltobinary.converter(i, len(set_name))
subset = []
for n in range(len(bin_list)):
if bin_list[n] == 1:
subset.append(set_name[n])
else:
continue
powerset.append(subset)
return powerset
You can download the Decimal to Binary converter here. The powerset constructor can be downloaded here.
That should do it
Ah right, owing to the mess my life has become ( getting shafted by colleges everywhere ) I have been incapable of responding to comments. I apologize and promise that I will get to making this blog the best in the world soon
HAPPY CODING !
March 24th, 2008 — Mathematics, python
Its time for an overdose of Math!
I encountered this problem in the Project Euler archives which involved a small triangle of numbers in which I had to find the maximum sum from top to bottom. The solution - brute force.
Wrong,
The main rule I follow and I believe most aspiring computer scientists follow involves the easiest way to solve a sum. Brute force doesn’t cut it as the best method to solve this sum when you are confronted with a grid as large as the one presented in question 67 (click here to see the mammoth of a triangle ).
I was trying to figure out the answer to that question and I came up with this idea, to move up from the base of the triangle. Here is how it works:
1. Consider the following triangle:
2. Replace each number in the second line with the number which happens to be the maximum of the numbers obtained
by adding that number to the two numbers adjacent to it in the line below. In this case, the pair giving the maximum
is represented in red.
Proceed in the same fashion and you will end up with 23 as the final number. 23 is the maximum sum obtained when going from top to bottom and this method is a quick way of getting to the answer.
Here is the code for the triangle provided in question 18:
#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a P.S.P
triangle = """\
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"""
def triangleMaker(triangle):
triangle_list = [ line.split() for line in triangle.splitlines() ]
return triangle_list
#start from the lowermost line and work your way up.
def getMax(triangle):
#pick the second last line of the triangle
our_line = triangle[-2]
for i in range(len(our_line)):
new_num_list = []
new_num_list.append(int(triangle[-2][i]) + int(triangle[-1][i]))
new_num_list.append(int(triangle[-2][i]) + int(triangle[-1][i + 1]))
triangle[-2][i] = str(max(new_num_list))
triangle.pop()
return triangle
tri_grid = triangleMaker(triangle)
for i in range(len(tri_grid) - 1):
tri_grid = getMax(tri_grid)
print tri_grid
For an idea on how effective this solution is, question 67 took 0.18 seconds to solve.
Happy coding
March 24th, 2008 — Mathematics, python
Well, a new sum on ProjectEuler enabled me to test my meager math and Python skills. This one however wasn’t as much of a Python challenge as it was a math challenge. Let me introduce you to problem 15 of the Project Euler problem set. The problem describes the number of ways you can move across a 2 x 2 grid.
The solution turned out to be dead simple if you regard the possible movements as follows:
- A horizontal move is represented by x
- A vertical move is represented by y
Consider the first block in the above picture. The bold line can be represented as;
x x y y
using our notation.
The bold line in the second block can be represented as;
x y x y
This is but a permuation of the letters we get in the first series.
So we get that the length of any path from the starting point to the last point in a grid of order “n” is 2n units and compulsorily contains “n” horizontal moves and “n” vertical moves. Our problem is limited to dividing 2n possible moves into n horizontal and n vertical moves. The answer as known to any mathematician with brains is:
2nCn
In case of a 20 x 20 grid that becomes: “Out of 40, choose 20″. Therefore: 40C20. The required code ( I am sure there isn’t any need, but I am too lazy to find my calc and punch in the numbers):
#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
def no_of_paths(order):
return (factorial(order * 2)) / (factorial(order)) ** 2
print no_of_paths(20)
Happy Coding
March 22nd, 2008 — Mathematics, python
As I sit admiring the rain (which I believe has come a bit too early in the year thanks to global warming), I am churning out code. I just love seeing functions. Each function performing an individual action and all of these interacting to achieve the objective of the program - I LOVE IT !!!
I wrote this script the day before MIT’s results were announced and due to a mistake committed by the admissions office ( 
) which had me in a bad mood for sometime, this script stayed underground.
The objective of this script was to solve question 22 of the Project Euler problem set ( the greatest set of problems ever ).
Here is the solution:
#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP
import string
f = open("names.txt", "r")
names_list = f.read().split(‘","’)
names_list[0] = names_list[0][1:]
names_list[-1] = names_list[-1][0:6]
names_list.sort() #Arrange in alphabetical order.
def alphaDict():
alphadict = {}
alphastring = string.uppercase
for char in alphastring:
alphadict[char] = alphastring.find(char) + 1
return alphadict
def scorer(word):
”‘Make a score for each word’”
alphadict = alphaDict()
scores_list = []
for letter in word:
scores_list.append(alphadict[letter])
return sum(scores_list)
scores_list = []
for name in names_list:
scores_list.append((names_list.index(name) + 1) * scorer(name))
print sum(scores_list)
That particular solution took 0.83 seconds which I guess is ok considering what one of my brute force attempts on the collatz theorem took, 52 seconds. Well, I am happy with 0.83 seconds and I request and welcome everyone else to provide better solutions.
Well, here is the solution to question number 11 .
import numpy
from operator import mulnumbers = ”‘\
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48′”
def gridMaker(numbers):
grid = {}
index = 0
for numstring in numbers.splitlines():
bummer = [ int(char) for char in numstring.split() ]
grid[index] = bummer
index += 1
return grid
grid = gridMaker(numbers)
def horizontalProd(index, grid):
”‘The structural unit of this function is a list’”
prods_list = []
num_list = grid[index]
for num_index in range(0, len(num_list) - 3):
prods = reduce(mul, num_list[num_index:num_index+4])
prods_list.append(prods)
return max(prods_list)
def verticalProd(vertical_index, grid):
”‘The structural unit of this function is a vertical column i.e. dict[index][0]
for index between 0 and 20′”
prods_list = []
num_list = []
for index in range(0, 20):
num_list.append(grid[index][vertical_index])
for num_index in range(0, len(num_list) -3):
prods = reduce(mul, num_list[num_index:num_index+4])
prods_list.append(prods)
return max(prods_list)
def prepareMatrix(grid):
num_matrix = []
for i in range(0, 20):
num_matrix.append(grid[i])
return num_matrix
def diagonalProd(grid_key, grid_value, grid):
base_matrix = numpy.mat(prepareMatrix(grid))
sub_matrix = base_matrix[grid_key:grid_key+4, grid_value:grid_value+4]
return reduce(mul, numpy.diagonal(sub_matrix))
def prepareInvertMatrix(grid):
num_matrix = []
for i in range(0, 20):
num_list = grid[i]
num_list.reverse()
num_matrix.append(num_list)
return numpy.mat(num_matrix)
def inverseDiagonalProd(grid_key, grid_value, grid):
base_matrix = prepareInvertMatrix(grid)
sub_matrix = base_matrix[grid_key:grid_key+4, grid_value:grid_value+4]
return reduce(mul, numpy.diagonal(sub_matrix))
def maxHorProdList(grid):
prods_list = []
for i in range(0, 17):
prods_list.append(horizontalProd(i, grid))
return prods_list
def maxVerProdList(grid):
prods_list = []
for i in range(0, 17):
prods_list.append(verticalProd(i, grid))
return prods_list
def maxDiagProdList(grid):
prods_list = []
for i1 in range(0, 17):
for i2 in range(0, 17):
prods_list.append(diagonalProd(i1, i2, grid))
return prods_list
def maxInvertDiagProdList(grid):
prods_list = []
for i1 in range(0, 17):
for i2 in range(0, 17):
prods_list.append(inverseDiagonalProd(i1, i2, grid))
return prods_list
print max[maxHorProdList(grid) + maxVerProdList(grid) + maxDiagProdList(grid) + maxInvertDiagProdList(grid)]
This solution is “big” and I know it. But I wanted to get a basic hang of numpy and found that this sum would be an excellent opportunity to do so. Well, happy coding
February 22nd, 2008 — Daily life, Mathematics, python
Lots of stuff happening in the past week. Let me begin with that news which should come as a blow to storage enthusiasts. The HD-DVD format is going forever. Toshiba says it will no longer create HD-DVD players/records. Now, I liked the HD-DVD format for its ECMAScript support. Well thats over. Then the US blew up a satellite, China’s pissed and wants to know more about the mission, my board exams are getting closer ( bleagh! ). Anyway, here is an update on my “work” in the past week.
Oh BTW, while solving a question related to the Fibonacci sequence, I found a supercool formula - the Binet’s formula. Let the greatest integer function be represented by “[]”
f(x) = [x]
let F represent the Fibonacci sequence. The Binet’s formula states that
F(n) = [{(1 + sqrt(5))^n}-{(1-sqrt(5))^n} / (2^n * sqrt(5))]
There ! Now you can solve that Fibonacci problem in the project euler archives.
I solved another sum. Here is the question:
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ? b, then a and b are an amicable pair and each of a and b are called amicable numbers.For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.
Here is the solution:
#!/usr/bin/env python
#Amicable numbers
def makeFactors(number):
factor_list = []
if number % 2 == 0:
for i in range(1, number / 2 + 1):
if number % i == 0:
factor_list.append(i)
else:
continue
else:
for i in range(1, (number + 1)/2):
if number % i == 0:
factor_list.append(i)
else:
continue
return factor_list
def checkAmicable(number):
factor_list = makeFactors(number)
factor_sum = sum(factor_list)
new_factor_list = makeFactors(factor_sum)
new_factor_sum = sum(new_factor_list)
if new_factor_sum == number and factor_sum != number:
return True
else:
return False
amicable_list = []
for number in range(0, 10001):
if checkAmicable(number):
amicable_list.append(number)
else:
continue
print sum(amicable_list)
Thats it for now, goodbye !
February 9th, 2008 — Mathematics, python
Shaun ( of #computers on irc.icq.net ) once mentioned that children are quite clever till people teach them things. I am currently in such a state. I’ve got ignorant people, ignorant about their ignorance, all around me and what’s more, this super-brain society feels that it is up to them to set me on the path to success. When you set their skills to test, they confuse between Perl and vim and feel that programming includes just taking things into consideration and typing instructions in English. I am just cheesed off by this lot. What do I do when I am in am in this towering temper ? I code. Well, let us begin this technical dose guaranteed to bring calm and quiet to the oppressed mind.
During my search for good number theory questions ( not already included in the Project Euler problem archive ). I discovered Kaprekar’s brilliant work.
Observe the following numbers:
(a). 197:
Arrange the digits of 197 in increasing order and you get 179. Reverse this and you get 971. 971-179 = 792. Do the same with 792.
972-279 = 693
963-369 = 594
954-459 = 495
STOP ! 495 is the kaprekar constant for 3 digit numbers. Pick any 3 digit number and carry out the aforementioned process. You will end up at 495. This is called the Kaprekar method. I hacked up a Python script to measure the depth of the Kaprekar process. It supports 3 digit numbers only atm. I will hack it up a bit more to figure out the kaprekar constant and then calculate the depth. So fellow code enthusiasts, enjoy !;
#!/usr/bin/python
#Kaprekar process length
from copy import copy
kaprekar_constant = 495
def kapLength(number):
difference = numAppend(number)[2]
i = 0
while difference != kaprekar_constant:
i = i + 1
difference = numAppend(difference)[2]
else:
return i
def numAppend(number):
numlist = []
for char in str(number):
numlist.append(char)
numlist.sort()
new_numlist = copy(numlist)
new_numlist.reverse()
smallest_number = int("".join(numlist))
greatest_number = int("".join(new_numlist))
difference = greatest_number - smallest_number
return (smallest_number, greatest_number, difference)
print kapLength(197)
Change the number in the last argument to try out new numbers. I will write about something I have stumbled upon in the world of semantic filesystems tomorrow.
February 5th, 2008 — Mathematics, python
Its over - the practical exams are finished. So here is the update:
4th of Feb:
I entered the examination hall trying to figure out possible worst case scenarios ( my experience with the highly inaccurate fractional weights during the physical balance experiment hasn’t been pleasant. ). I was shivering and I got experiment 10 - simple pendulum. I zoomed away and after 7 readings, submitted my paper. I am not going to write about that, doesn’t deserve space on this blog.
5th of Feb (i.e. today):
I entered the hall with an air of confidence around me. Well, it is the last time I do practicals in school so the nostalgia did bug me. I finished my salt analysis experiment in a jiffy. My salt was barium chloride and the yellow precipitate that is obtained when the salt solution is allowed to react with potassium chromate was striking. Anyway, I did my volumetric analysis experiment after that and I was asked to estimate the amount of oxalic acid in 1000 ml solution using a 0.02 M solution of KMnO4 (potassium permanganate). I got the result to be 6.3636 gram. Brilliant, its over !
Now, I solved a few sums in math over the past few days. Here are the hopefully ok solutions. The star highlight is the last problem. I found it on a newsgroup and considering someone mentioned Donald Knuth there, I was eager to see if I could solve “any” sum of this legend of a computer scientist. I need laminated pics of Knuth, Shannon and Dijkstra. Can someone point me to a source where I can find a framed pic of these pioneers ? Right, lets move to the math.
Question1:
Find the sum of the digits in 100! (100 factorial).
#!/usr/bin/python
#Author: Shriphani Palakodety
# ProjectEuler.net problem 20
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
def sumOfDigits(n):
num = factorial(n)
num_list = [ int(x) for x in str(num) ]
return sum(num_list)
print sumOfDigits(100)
Divide the numbers 1 ** 2, 2**2 …… 50 ** 2 into 2 groups so that the difference between the sums of the elements of each group is either 0 or the minimum value possible.
#!/usr/bin/python
#Author: Shriphani Palakodety
#Donald Knuth's problem (i think)
def genNumList(n):
num_list = []
for i in range(0, n+1):
num_list.append( i ** 2)
return num_list
def pairMaker(num_list):
list1 = num_list
list2 = []
for i in range(0, len(list1)-1):
list2.append(list1[i])
difference = abs(sum(list2) - sum(list1[i:]))
yield (list1[i:], list2[:i], difference)
def commode(n):
bullshit = [ x for x in pairMaker(genNumList(n)) ]
diff_list = []
for element in bullshit:
diff_list.append(element[2])
return (diff_list, bullshit)
def solution(n):
i = commode(n)[0].index(min(commode(n)[0]))
return commode(n)[1][i]
print solution(50)
I found some more semantic filesystems material that I will read tomorrow. I’ve got 2 more euler problems which I am about to finish. Lots of work to do but there are only 24 hours in a day.
January 19th, 2008 — Mathematics, python
I am busy writing dad’s pdf script. The real troubles begin when you parse 1000 pages using trash like pyparsing (yes, I am back to it). Anyway, let me see how it goes. I did another projecteuler.net sum today ( question 8 ). The question is:
Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
Here is what I wrote to solve this problem:
There. It took 0.03 seconds to work. Not bad for a budding computer scientist I suppose
Right, I’ll write again later.
December 7th, 2007 — Daily life, Mathematics
Today I returned a bit too late from FIITJEE considering that I had to give the evaluation forms to my teachers. After returning home, I picked up a book titled “An Unusual Algebra” by I.M. Yaglom. It is an excellent work that introduces Boolean algebra. I have finished half the book. Here is what I learned:
2 + 3 = 5
3 + 4 = 7
If we have sets like A, B and C and if we define addition to be union, and multiplication to be intersection, then we have the following properties associated with the operations addition and multiplication:
1. Commutative property:
A + B = B + A or A + C = C + A or B + C = C + B
AB = BA or AC = CA or BC = CB
2. Associative propery:
(A + B) + C = A + (B + C)
(AB)C = A(BC)
3. Distributive property:
(A + B)C = AC + BC
(A + C)(B + C) = AB + C
4. Idempotent property:
AA = A, BB = B and CC = C
A + A = A, B + B = B and C + C = C
So we go on to state that the operation “addition” and “multiplication” are to have the above properties and if we go on to apply this operation “addition” to a set of numbers {0, 1}, then we have the following:
0 + 1 = 1
0 + 0 = 0
1 + 1 = 1
1 + 0 = 1
Now these satisfy the properties stated above. There’s Boolean algebra in a nutshell.
I was then musing that those properties that we stated for sets form the peoperties for operations in Boolean algebra. However I did find a catch in that. We have what is known as the Identity element for addition and multiplication, 0 and 1 respectively. But there is no such set X such that X + A = A or XA = A. If there were such a set, it would be the superset of every set. There you go.
I need to learn a bit more. I will be posting more about this book here. Till then, goodbye
