15 251 Great Theoretical Ideas in Computer Science Ancient Wisdom Unary and Binary 11 2007 Lecture 5 September Prehistoric Unary 1 2 3 4 Consider the problem of finding a formula for the sum of the first n numbers You already used induction to verify that the answer is n n 1 1 2 3 n 1 n S n n 1 n 2 2 1 S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S n n 1 S 2 1 2 3 n 1 n S n n 1 n 2 2 1 S n n 1 2S n n 1 S 2 There are n n 1 dots in the grid n 2 1 1 2 n nth Triangular Number n 1 2 3 n 1 n n n 1 2 nth Square Number n n2 n n 1 Breaking a square up in a new way 1 Breaking a square up in a new way 1 3 Breaking a square up in a new way 1 3 5 Breaking a square up in a new way 1 3 5 7 Breaking a square up in a new way 1 3 5 7 9 Breaking a square up in a new way 1 3 5 7 9 52 Breaking a square up in a new way The sum of the first n odd 2 numbers is n Pythagoras Here is an alternative dot proof of the same sum nth Square Number n n n 1 n2 nth Square Number n n n 1 n2 nth Square Number n n n 1 nth Square Number n n n 1 Sum of first n odd numbers Check the next one out Area of square n 2 n n Area of square n 2 n 1 n 1 n n Area of square n 2 n 1 n 1 n n Area of square n 2 n 1 n 1 n n n n Area of square n 2 n 1 n 1 n n n n Area of square n 2 n 1 2 n n 1 n n n 1 2 n n 1 n n 1 2 n n n 1 n 1 2 n n n 1 n n n n n 1 n 1 2 n3 n n 2 n3 n 1 2 n3 n 1 3 n2 2 n3 n 1 3 n 2 3 n 33 2 n n 1 3 n 2 3 13 n 2 n3 13 23 33 n n 1 2 2 Can you find a formula for the sum of the first n squares Babylonians needed this sum to compute the number of blocks in their pyramids Rhind Papyrus Scribe Ahmes was Martin Gardener of his day A man has 7 houses Each house contains 7 cats Each cat has killed 7 mice Each mouse had eaten 7 ears of spelt Each ear had 7 grains on it What is the total of all of these Sum of powers of 7 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 X 1 We ll use this fundamental sum again and again The Geometric Series A Frequently Arising Calculation X 1 1 X1 X2 X3 Xn 2 Xn 1 X1 X2 X3 Xn 1 Xn 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 1 X1 X2 X3 Xn 2 Xn 1 when x 1 Xn 1 X 1 Geometric Series for X 2 1 21 22 23 2n 1 1 X1 X2 X3 Xn 2 Xn 1 when x 1 2n 1 Xn 1 X 1 BASE X Representation S an 1 an 2 a1 a0 represents the number an 1 Xn 1 an 2 Xn 2 a0 X0 Base 2 Binary Notation 101 represents 1 2 2 0 21 1 20 Base 7 015 represents 0 7 2 1 71 5 70 Bases In Different Cultures Sumerian Babylonian 10 60 360 Egyptians 3 7 10 60 Maya 20 Africans 5 10 French 10 20 English 10 12 20 BASE X Representation S an 1 an 2 a1 a0 X represents the number an 1 Xn 1 an 2 Xn 2 a0 X0 Largest number representable in baseX with n digits X 1 X 1 X 1 X 1 X 1 X 1 X X 1 Xn 1 Xn 2 X0 Xn 1 Fundamental Theorem For Binary Each of the numbers from 0 to 2n 1 is uniquely represented by an n bit number in binary k uses log2k 1 digits in base 2 Fundamental Theorem For Base X Each of the numbers from 0 to Xn 1 is uniquely represented by an n digit number in base X k uses logXk 1 digits in base X n has length n in unary but has length log2n 1 in binary Unary is exponentially longer than binary Other Representations Egyptian Base 3 Conventional Base 3 Each digit can be 0 1 or 2 Here is a strange new one Egyptian Base 3 uses 1 0 1 Example 1 1 1 9 3 1 5 We can prove a unique representation theorem How could this be Egyptian Historically negative numbers first appear in the writings of the Hindu mathematician Brahmagupta 628 AD One weight for each power of 3 Left negative Right Unary and Binary Triangular Numbers Dot proofs 1 x x2 xn 1 xn 1 x 1 Base X representations k uses log2k 1 log2 k 1 digits in base 2 Here s What You Need to Know
View Full Document
Unlocking...