### Nov

#### 27

# Project Euler: finding maximal sum of path in a graph

Filed Under hisabati, project euler by Mucheru | Comments Off on Project Euler: finding maximal sum of path in a graph

Problem 18 in Project Euler reminded me of shortest path algorithms in graph theory. The goal is to determine the maximal sum you can compute when traveling from the top to the bottom of a triangle.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3

7 5

2 4 6

8 5 9 3That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

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

If this were a shortest path problem, we would be computing the minimum sum when traveling down the triangle (and we would also have a fixed destination, rather than a set of them – details, details). As phrased, the problem does not actually require us to give the path that yields the maximal sum and that eases the requirements on our algorithm.

The first step of our solution is to read lists of integers from the input triangle string.

1: def get_triangle_lists(triangleString): 2: listOfRowsString = triangleString.split('n') 3: listOfRows = [] 4: for row in listOfRowsString: 5: currRow = [int(x) for x in row.split()] 6: listOfRows.append(currRow) 7: return listOfRows

Next, we compute the max sum.

1: def max_sum_in_triangle(triangleString): 2: listOfLists = get_triangle_lists(triangleString) 3: numRows = len(listOfLists) 4: for index in range(0, numRows): 5: if(index == 0): 6: continue 7: currRow = listOfLists[index] 8: previousRow = listOfLists[index - 1] 9: for column in range(0, index+1): 10: if (column == 0): 11: currRow[column] += previousRow[column] 12: elif(column == index): 13: currRow[column] += previousRow[column - 1] 14: else: 15: currRow[column] += max(previousRow[column - 1], previousRow[column]) 16: return max(listOfLists[numRows - 1])

The motivation is simple. We go through the triangle, from top to bottom one row at a time (breadth-first). For each node, we set its value to the maximal sum that can be achieved by a valid path ending in that node. For the top node, the maximal sum is trivially the value of the node. For subsequent rows, each node can be reached from exactly one or two nodes from the previous row. The outer nodes in a row are only reachable from the outer nodes from the previous row. This means that for these nodes, we always add the current node value to the previous outer node’s value ( Lines 10 to 13 of the code above). Nodes that are not outer nodes in the row are reachable from two nodes in the previous row (the node to the upper left and one to the upper right in the graphical representation).The maximal sum at the current node is therefore given by the value of the current node plus the higher value between those presented in the two nodes in the previous row (Line 15 of the code above).

When the algorithm finishes iterating through the rows, the maximal value can be read directly from the bottom row of the triangle (line 16 in the code above).

### Nov

#### 26

# Project Euler: Largest product of consecutive digits in grid

Filed Under hisabati, project euler by Mucheru | 1 Comment

Problem 11 from Project Euler is a fun one:

In the 20 by 20 grid below, four numbers along a diagonal line have been marked in red.

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 102638 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 956394 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 177878 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 351400 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 48The product of these numbers is

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 by 20 grid?

I came up with two solutions: a naive exhaustive search (which still runs remarkably fast in python) and a slightly more efficient one in the spirit of my solution to problem 8. The naive version proceeds as follows:

1: def max_prod_in_grid_basic(gridString, windowSize): 2: gridNums = [int(x) for x in gridString.split()] 3: gridLen = int(sqrt(len(gridNums))) 4: maxProduct = 0 5: # get horizontal products 6: lastColumn = gridLen - windowSize + 1 7: for rootRow in range(0, gridLen): 8: for rootColumn in range(0, lastColumn): 9: startIndex = (rootRow * gridLen) + rootColumn 10: endIndex = startIndex + windowSize 11: windowItems = gridNums[startIndex:endIndex] 12: currProduct = prod(windowItems) 13: if(currProduct > maxProduct): 14: maxProduct = currProduct 15: # get vertical products 16: lastRow = gridLen - windowSize + 1 17: for rootColumn in range(0, gridLen): 18: for rootRow in range(0, lastRow): 19: startIndex = (rootRow * gridLen) + rootColumn 20: endIndex = startIndex + (gridLen * windowSize) 21: windowItems = gridNums[startIndex: endIndex: gridLen] 22: currProduct = prod(windowItems) 23: if(currProduct > maxProduct): 24: maxProduct = currProduct 25: # get down-diagonal products 26: lastRow = gridLen - windowSize + 1 27: lastColumn = gridLen - windowSize + 1 28: for rootRow in range(0, lastRow): 29: for rootColumn in range(0, lastColumn): 30: startIndex = (rootRow * gridLen) + rootColumn 31: endIndex = startIndex + (gridLen * windowSize) + windowSize 32: windowItems = gridNums[startIndex: endIndex: gridLen+1] 33: currProduct = prod(windowItems) 34: if(currProduct > maxProduct): 35: maxProduct = currProduct 36: # get up-diagonal products 37: lastRow = gridLen - windowSize + 1 38: lastColumn = gridLen 39: firstColumn = windowSize - 1 40: for rootRow in range(0, lastRow): 41: for rootColumn in range(firstColumn, lastColumn): 42: startIndex = (rootRow * gridLen) + rootColumn 43: endIndex = startIndex + (gridLen * windowSize) - windowSize 44: windowItems = gridNums[startIndex: endIndex: gridLen-1] 45: currProduct = prod(windowItems) 46: if(currProduct > maxProduct): 47: maxProduct = currProduct 48: return maxProduct

The primary weakness with this approach is that it does not take advantage of the fact that there is a simple relationship between the products of two adjacent sets of consecutive numbers. From the solution to problem 8:

We achieve some performance gain by taking advantage of the overlap between adjacent windows. If the window has length 5, then adjacent windows have 3 elements in common. The overlap elements contribute the same value to the product computed for the two adjacent windows. Therefore, the difference between the product computed for a window starting at index i and one starting at i+1 is due to elements at the end of the windows. Specifically, the product of the window rooted at i+1 is given by the dividing the value of the product of the window rooted at i by the value of the ith element (undoing the effect of the element we’re removing) multiplied by the value of the element at position i+(windowSize – 1) (adding the effect of the new element)

The second algorithm takes advantage of this information. The solution is in two functions. First, we extract the list of valid sequences (all the rows, columns and up and down diagonals), taking the maximum length of each sequence.

1: def get_sequences_in_grid(gridString, minLength): 2: gridNums = [int(x) for x in gridString.split()] 3: gridLen = int(sqrt(len(gridNums))) 4: digitSequences = [] 5: # get horizontal sequences 6: rootColumn = 0 7: for rootRow in range(0, gridLen): 8: startIndex = (rootRow * gridLen) + rootColumn 9: endIndex = startIndex + gridLen 10: listItems = gridNums[startIndex:endIndex] 11: digitSequences.append(listItems) 12: # get vertical sequences 13: rootRow = 0 14: for rootColumn in range(0, gridLen): 15: startIndex = (rootRow * gridLen) + rootColumn 16: endIndex = int(len(gridNums)) 17: listItems = gridNums[startIndex: endIndex: gridLen] 18: digitSequences.append(listItems) 19: # get down-diagonal sequences 20: # upper triangle 21: lastRow = gridLen - minLength + 1 22: lastColumn = gridLen - minLength + 1 23: rootRow = 0 24: for rootColumn in range(0, lastColumn): 25: startIndex = (rootRow * gridLen) + rootColumn 26: endIndex = (rootRow + 1 +(gridLen - (rootColumn + 1))) * gridLen 27: listItems = gridNums[startIndex: endIndex: gridLen+1] 28: digitSequences.append(listItems) 29: # lower triangle 30: rootColumn = 0 31: for rootRow in range(1, lastRow): 32: startIndex = (rootRow * gridLen) + rootColumn 33: endIndex = (rootRow + 1 + (gridLen - (rootRow + 1))) * gridLen 34: listItems = gridNums[startIndex: endIndex: gridLen+1] 35: digitSequences.append(listItems) 36: # get up-diagonal sequences 37: # upper triangle 38: rootRow = 0 39: firstColumn = minLength - 1 40: for rootColumn in range(firstColumn, gridLen): 41: startIndex = (rootRow * gridLen) + rootColumn 42: endIndex = startIndex + (rootColumn * gridLen) 43: listItems = gridNums[startIndex: endIndex: gridLen - 1] 44: digitSequences.append(listItems) 45: # lower triangle 46: rootColumn = gridLen - 1 47: for rootRow in range(1, lastRow): 48: startIndex = (rootRow * gridLen) + rootColumn 49: endIndex = (rootRow + 1 + (gridLen - (rootRow + 1))) * gridLen 50: listItems = gridNums[startIndex: endIndex: gridLen - 1] 51: digitSequences.append(listItems) 52: return digitSequences 53:

The second step takes the list of sequences and iterates through them, computing the max product for each list using a modified version of the “slice product” function from problem 8.

1: def max_prod_in_grid(gridString, minLength): 2: sequences = get_sequences_in_grid(gridString, minLength) 3: max_product = 0 4: for currList in sequences: 5: listLength = len(currList) 6: if(listLength < minLength): 7: continue 8: curr_product = prod(currList[:minLength]) 9: if(curr_product > max_product): 10: max_product = curr_product 11: for i in range(1, listLength - minLength + 1): 12: stopPosition = i + (minLength - 1) 13: outItem = currList[i - 1] 14: inItem = currList[stopPosition] 15: if(outItem == 0): 16: curr_product = prod(currList[i:stopPosition + 1]) 17: else: 18: curr_product = (curr_product / outItem) * inItem 19: if(curr_product > max_product): 20: max_product = curr_product 21: return max_product

### Nov

#### 25

# Project Euler: Largest product of consecutive digits

Filed Under hisabati, project euler by Mucheru | 1 Comment

For Problem 8 in Project Euler, you are required to find the largest product of 5 consecutive digits in a 1000 digit integer.

7316717653133062491922511967442657474235534919493496983520

3127745063262395783180169848018694788518438586156078911294

9495459501737958331952853208805511125406987471585238630507

1569329096329522744304355766896648950445244523161731856403

0987111217223831136222989342338030813533627661428280644448

6645238749303589072962904915604407723907138105158593079608

6670172427121883998797908792274921901699720888093776657273

3300105336788122023542180975125454059475224352584907711670

5560136048395864467063244157221553975369781797784617406495

5149290862569321978468622482839722413756570560574902614079

7296865241453510047482166370484403199890008895243450658541

2275886668811642717147992444292823086346567481391912316282

4586178664583591245665294765456828489128831426076900422421

9022671055626321111109370544217506941658960408071984038509

6245544436298123098787992724428490918884580156166097919133

8754992005240636899125607176060588611646710940507754100225

6983155200055935729725716362695618826704282524836008232575

30420752963450

My implementation for this proceeds as follows:

1: def window_slice_product(num,windowSize): 2: digits = [int(x) for x in str(num)] 3: sequencewindowSize = len(digits) 4: if(sequencewindowSize <= windowSize): 5: return prod(digits) 6: 7: products =[] 8: curr_product = prod(digits[:windowSize]) 9: max_product = curr_product 10: for i in range(1, sequencewindowSize - windowSize + 1): 11: stopPosition = i + (windowSize - 1) 12: outItem = digits[i - 1] 13: inItem = digits[stopPosition] 14: if(outItem == 0): 15: curr_product = prod(digits[i:stopPosition + 1]) 16: else: 17: curr_product = (curr_product / outItem) * inItem 18: if(curr_product > max_product): 19: max_product = curr_product 20: return max_product

Given the digits in the input number, we create a list with all the integers in sequence. To calculate the required product, we create a sliding window of length 5, which serves as a snapshot of the list. In each iteration of the loop starting on line 10, we ‘slide’ the window down the list (we start with the window’s first element at index 0 and consider 5 consecutive items; move the window to have first item at index 1 and consider 5 items etc until we get to the point where the window’s starting element is at index 995). We take the product of each window and check if it’s higher than the maximal product seen so far. At the end, we report the max product.

We achieve some performance gain by taking advantage of the overlap between adjacent windows. If the window has length 5, then adjacent windows have 3 elements in common. The overlap elements contribute the same value to the product computed for the two adjacent windows. Therefore, the difference between the product computed for a window starting at index i and one starting at i+1 is due to elements at the end of the windows. Specifically, the product of the window rooted at i+1 is given by the dividing the value of the product of the window rooted at i by the value of the ith element (undoing the effect of the element we’re removing) multiplied by the value of the element at position i+(windowSize – 1) (adding the effect of the new element). This is achieved in lines 11 to 17 of the algorithm posted.

In the cases where we remove a zero, its necessary to compute the product for the new window by multiplying all items in the window – otherwise we would end up dividing by zero.

### Nov

#### 24

# Project Euler: Summing digits in a factorial

Filed Under hisabati, project euler by Mucheru | Leave a Comment

For problem 20, the goal is to sum all the digits in a large number:

Find the sum of the digits in the number 100!

The algorithm proceeds as follows:

1: def factorial(n): 2: if(n == 0): 3: return 1 4: else: 5: return (n * factorial(n-1)) 6: 7: def sum_factorial(n): 8: fact = factorial(n) 9: digits = [int(x) for x in str(fact)] 10: return sum(digits)

The *factorial()* function is defined in a pretty straightforward recursive algorithm. The interesting line stuff happens in the *sum_factorial()* function (specifically on line 9). We use a list comprehension to unpack the digits in the factorial number into a list object. When the comprehension is evaluated, the call to *str()* converts the factorial number to a string (which is iterable). We take each character in the string and call *int()* on it to convert it to an integer. The collection of integers is then collected into a list. the call to *sum()* on line 10 takes a list of integers and returns a single number which is the sum.

### Nov

#### 21

# Project Euler: Least Common Multiple

Filed Under hisabati, project euler by Mucheru | Leave a Comment

This is the second of a series of problems form Project Euler that I’ve worked on as part of my “Learn Python” project. In Problem 5, the question is:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

In mathematical terms, this is asking for the Least Common Multiple of the numbers in the range from 1 to 20. The algorithm here is an implementation of the “LCM by table” method described in the linked Wikipedia article.

1: def find_lcm_of_range(n): 2: assert (0 < n) 3: residues = range(1, n+1) 4: divisor = 2 5: lcm_factors = [] 6: found_factor = False 7: while True: 8: #print residues 9: found_factor = False 10: highest_power = 0 11: for index, item in enumerate(residues): 12: if(item < 2): 13: continue 14: elif((item % divisor) == 0): 15: found_factor = True 16: # extract all powers of the divisor 17: curr_power = 0 18: while ((residues[index] % divisor) == 0): 19: residues[index] = residues[index] / divisor 20: curr_power += 1 21: if(curr_power > highest_power): 22: highest_power = curr_power 23: if(found_factor): 24: highest_value = pow(divisor, highest_power) 25: lcm_factors.append(highest_value) 26: # remove 1s from the list 27: residues[:] = [x for x in residues if (x != 1)] 28: if(divisor < n): 29: if(divisor == 2): 30: divisor += 1 31: else: 32: divisor += 2 33: else: 34: break 35: print "LCM factors: ", lcm_factors 36: # multiply out all factors 37: lcm = 1 38: for f in lcm_factors: 39: lcm *= f 40: 41: return lcm

The algorithm finds the lcm of the numbers in range (1,n) by accumulating factors in a list. This is similar to the Prime Factors code from a previous post – we try all numbers starting at 2 and check if we have a factor for any number in the list. Once we find a factor, we figure out the highest exponent of the divisor that divides a number on the list (lines 18 – 21). The value of the divisor to its maximal power is taken as a factor and added to our list. We also reduce the values of numbers in the range as we find factors, keeping computation costs low. At the end of an iteration involving a particular divisor, we remove all numbers in the residues list whose values are now 1 (i.e. we’ve found all their factors so they no longer need to be considered in future iterations) [line 27]. At the end, when we have the list of factors, we multiply them out to give the lcm.

To get a better idea of how this works, you can uncomment line 8 and observe the list of residues at each iteration. The algorithm is exponential but runs surprisingly fast – the lcm for numbers between 1 and 20 is determined in 1 millisecond whereas the lcm for the range 1-10,000 is found in 2.749 seconds. The latter number is pretty big:

5793339670287642968692270879166240098634860297998518825393

1383511489793001457731823088325981761829221665744176794023

4070565594914024678915773283267630212994668431184746378526

5683193852154947234797107306816167930170547268523692646338

7338495220571064420250677315000599457941340849496227227628

9264937710182648218422303703496401025734928814243173061895

6946710149583460199127003991878092450649540579792376220536

0790652073159333382795670426041033566699342449050309786673

6816704833691556895675542398988790397441473339719882580610

4209097047672929348451307244361479576687872632579585485539

4491290821167148355514749149683707585283381546153703014210

4424703181805119066911083251464942193434988993829180182465

8660982766747032916601211087498110480041574152758628002673

7848182673635645872230905234515169611121042867043956727839

3141987286262740666554678461833435991947615903686084725783

9816974011148592404698687071488389428584139496462740809416

1019230662749101230783008668676907211199488107523306410531

7720454528539577068732384668299886498221575571035032835633

9828177546491190478915951590098740157467888594249390760474

0891878907698622679570965569483682456042918236444719794534

4111719076063360905340293493513002761418925297954487518263

9439915321618327038573779574877050861209637476533357823797

3395907265484337502903901947799663388329849198045756207969

5900556866076781952063672736006329094170242247547504287112

3691791366341921592583094403553984874916317848961422754665

6090790164108195741048033614368495827231281392190063051315

2480701922634008013150956085121395107314697323113138989957

4604056343312142777607148265590434653828101066847673113241

5829844984600414136781404774213539507859790229205890271721

6003091699268061218717500081637387739116100095086091496653

3257963276739707887799692658133741935183475437041100868613

6818501030862345505385357198060894463821342298717851567836

5629843448064696137680247649673729796551790660743981982468

0510457613447482301648884281807704166167609839937880971389

4284994865370648616800689225595431967181072865363430005250

8407678909121645307057049368379155848566069606873473723913

3925443211908593217554139295434368471669516262927122978928

9404752104218596977036941910521266321726821940533986384237

9944037806183013790993479752601227241944542750888255870444

8820896569037370690405692650932469630881097433179011945643

8147168585552011926921912167450509941646104076818762060881

9039696164316463849858959442312185056205470938742411697592

0545014547874611279689862671196632096505721221995856733885

1356631739947125096250452942497473309299907612330435197454

3927886373592531163086850070142496054926595244291345133441

3751710187227942820228595165285635482723076593150280534169

6470148698002737700823078904634554776750169178259216255903

9688655887498277898889501724524554482488337123098356575613

6923315797740557936529367194313141203410990194489281924500

1657496671822581274180596255340507054499934060282320458240

7224542099335697359400328591099346868782741108643949244635

7385201533842888196184329208356603466981461961260663828361

5766521897504566616272305253931938372830446073384019299355

3208643427340195176336623467904229159519548226451370914941

2610039010451098737336632861536305604213744080822597360080

9566845718073791616927784260557845021823094999326904373592

3194075166608967643880922625103691821535592854460749909418

6351624722653265314219855184006363198942877679953328621546

4660644129411503287306838551341184739976807097763115368031

7486460437805490551434282972306780537384530102349490082537

6935520720816799920335315752466601702980367961213182474079

4652592875662818479980117505768541194835524231818203552256

4267527304551157522808370997632376063481928679364579939708

6644626401581281917999413864229510887238170918193709229039

2544335464025324661284746003660247161196698209062164637264

1149307664444734710834082003296620590642018967211650156874

8772830085450178081015584483748979814430994299909177446640

6270065305461848242329380636274754660519867343112275861821

2935011121014348682253780418138368087454176062891599042941

6594140869292225060112780497196234280792774339003039504826

3275616935165347620718001157478088456439083590834464409622

7816937908832895970240439825842200692241702358634587453443

6568408211443036286744619360107556980365077301802670000381

2298460527976219100308016537538008597751565631582745643139

434508332515569645426771932483266712323523039014220800000L

### Nov

#### 17

# Project Euler: prime factors

Filed Under hisabati, project euler by Mucheru | 1 Comment

The best way to learn a programming language is to use it in a project. Having a book is nice as a starting point (and as a reference guide) but I find that you have to step out of the world of tutorials and samples to see new sides of a language and encounter its frustrations. I’ve been meaning to try out python for a while now but I didn’t have a project that I would use it on. Recently, I came across a perfect candidate: Project Euler.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

This is the perfect tool for learning a language that has a functional bent to it.

For my first bit of Python, I tried out problem 3.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

def unique_prime_factors(n): assert (0 < n) if (n == 1): return [n] factors = [] residue = n divisor = 2 while True: if residue == 1: break while ((residue % divisor) != 0): divisor += 1 factors.append(divisor) while ((residue % divisor) == 0): residue /= divisor return factors

The idea behind the algorithm is pretty straight-forward. Given a number n, check for divisors from 2 to a max number (initially n). Each time we find a divisor, we reduce the max number and use the residue as our new max number. This implicitly caps the size of divisor considered at \sqrt{n} .Also, when we find a factor, we divide the residue for a long as the factor is a divisor thus extracting all the powers of the factor in the residue.

Reducing the residue to the smallest number we need speeds up our algorithm and proves to be a great boost in performance if we the number we’re factoring has small factors (i.e. is B-smooth for a small B).

### Nov

#### 17

# American tribalism

Filed Under siasa by Mucheru | Leave a Comment

The American Presidential campaign was filled with mudslinging and hate. The republican propaganda machine painted the picture of Obama as an un-American outsider, a terrorist, a socialist; they stopped short of calling him the anti-Christ. It reminded me of the Kenyan election. Thankfully, in the American case, the losing candidate conceded defeat graciously and the winner accepted the concession magnanimously.

The propaganda machine did not go away on polling day. Talk radio is still active spreading fear and hate. Last week, a Republican Congressman, Paul Broun, made the allegation that Obama would establish a Gestapo force in America (on talk radio, no less). A news report from AP has the details.

Broun was specifically referring to a July speech by Obama, where the then-Democratic presidential nominee said he supports a civilian force helping the military when it comes to national security.

Responding to those comments, Broun told the AP Monday: “That’s exactly what Hitler did in Nazi Germany and it’s exactly what the Soviet Union did. When he’s proposing to have a national security force that’s answering to him, that is as strong as the U.S. military, he’s showing me signs of being Marxist.”

“We can’t be lulled into complacency,” Broun added. “You have to remember that Adolf Hitler was elected in a democratic Germany.”

The statement is absolutely untenable and irrational. It is amazing to see this happen in America. Politics has moved from the realm of reasoned debate and policy discussions to appealing to people’s fears and latent prejudices. The target audience is divided into groups totally unrelated to the policies – in America, Palin preached about a “real” America and an “elitist” or “unpatriotic” fake America. If this were in Kenya, the proxy for policy discourse would would be tribal affiliation. Accusations would be “my opponent is a Muslim; he will only help his tribesmen” et cetera. Those are not quite as bad as “my opponent is Hitler” (though the republican machinery did use these earlier on). The experience makes me rethink my perceptions of tribalism. The line of division doesn’t matter – the tendency to fiery irrational hate and even violence is the same.

### Nov

#### 5

# The New Man

Filed Under siasa by Mucheru | Leave a Comment

Obama’s victory has been hailed as a victory for America. It is an affirmation that the country lives by the ideals that it was founded on. The vibrant movement that Obama mobilized shows that the government really is of the people. His unlikely ascendancy shows that it is still a land of opportunity – where a middle-class multi-racial kid from a single parent upbringing can rise to the highest office in the land.

For a nation that started out treating black people as sub-human and just 30 years ago criminalized interracial marriages, the transformation is amazing. As an African living in America, I share the euphoria of the black community. Obama is Joshua to Martin Luther King’s Moses. Dr. King led his people through the great struggle. He inspired many and spoke of a future in which the value of a man would be determined by the quality of his character – regardless of race. This is that time and this is the land of his dreams.

In the last speech he gave on the day before he was assassinated, King talked about the promised land:

Well, I don’t know what will happen now. We’ve got some difficult days ahead. But it really doesn’t matter with me now, because I’ve been to the mountaintop. And I don’t mind. Like anybody, I would like to live a long life. Longevity has its place. But I’m not concerned about that now. I just want to do God’s will. And He’s allowed me to go up to the mountain. And I’ve looked over. And I’ve seen the Promised Land. I may not get there with you. But I want you to know tonight, that we, as a people, will get to the promised land! And so I’m happy, tonight. I’m not worried about anything. I’m not fearing any man! Mine eyes have seen the glory of the coming of the Lord!!

It is noteworthy that Obama is not the traditional black revolutionary. He is the “new black man”. Reading his life story, you get the impression that he looks beyond race. Being black is only part of who he is. Franz Fanon spoke of this new man in his advice to the 3rd world revolutionaries:

For Europe, for ourselves and for humanity, comrades, we must make a new start, develop a new way of thinking, and endeavor to create a new man.

As an African, I see a different promise in Obama. I don’t think his administration will especially prioritize Africa or give us extra development aid. He already has quite a job cut out for him fixing America. What I do hope is that he will show the next generation of African leaders the value of the New Man. There are many parallels between the black struggle in America and the African struggle. The Americans have overcome by evolving a new man. We need to borrow a leaf from them and move past the fixation with colonialism and neocolonialism, blaming our present on the crimes of past generations. We need to formulate a plan of the future of our continent that does not involve retribution or righting past wrongs. We need our own messenger of Hope.

### Oct

#### 25

# Math’s use of language

Filed Under hisabati, sayansi, tarakirishi by Mucheru | Leave a Comment

Here’s a gem from the Ars mathamatica blog.I don’t think I could put it better if I tried.

You know, mathematical terminology cannot be parodied. Mathematicians have invented groups, semigroups, quasigroups, pseudogroups, and two mostly-unrelated concepts both known as groupoids. They have invented both formal groups and quantum groups, neither of which are kinds of groups. And while the study of groups is a branch of algebra, most groups are not, in fact, algebraic.

Check out the comments for the post

### Aug

#### 20

# The power of yams

Filed Under teknolojia by Mucheru | Comments Off on The power of yams

The Olympics may be gone but the sense of wonder at some of the feats of athletic ability still remain. For me, the two that stand out especially are the doings of Usain Bolt, Jamaica’s 21 year old star sprinter.

The first was his seemingly effortless win of the 100 m final. He did not look to strain as he led the pack in world record time. He let off before crossing the finish line (taking time to thump on his chest and look around to his adoring/amazed fans) – yet he still broke the world record and won gold! It was a sight to behold! Later on, when the NBC interviewer caught up with him, the conversation could not have been scripted better (paraphrased liberally).

Commentator: Congratulations on your victory. Winning Jamaica’s first men’s gold in this event. How does it feel?

Usain: It feels good. I came out here to win and have fun and I did.

Commentator: You let off a few meters there before crossing the finish line yet you still broke the world record. How much more time do you think you would have shaved off the record if you hadn’t let off?

Usain: hey, I’m not worried about that. I came here to win and have a good time and I did.

Commenator: [look of disbelief] but, the world record. Don’t you think you would have taken off some more time off it?

Usain: [even more amusing look of disbelief] yeah, but I won.

In my words, the last statement would have been “Dude, didn’t you notice I won?” He did win and he did have fun. In fact, it looked like every other contestant treated the race as the run of his life – huffing, puffing , strain showing on their faces – but Usain couldn’t wait for the race to be done. He wanted to show off his golden shoes (of which he had two pairs: a 100m version for the 100m race and a 200m version for the 200m race). He also needed to perform a jig and pose by he clock showing his world-record-setting time.

I can’t say I was totally shocked by Bolt’s performance in the 100m final. I had watched his semi-final heat for the same race the day before. In that, he had let off at about the 50m mark and taken the rest of the time to look into the stands, wave his hands around and generally trivialize the race. By his standards, winning against the fastest sprinters in the world was like taking candy from a bunch of babies.

As expected , the look of effortless ease did not go unquestioned. The press was first to hear voices “there are suspicions that doping might be involved”, “he might be taking performance enhancing substances”. Bolt’s dad faced those suspicions face on. “I know what my son takes to be strong and fast. ” He took a suspenseful pause then added, “It is a healthy amount of yams from Jamaica’s Trelawny region.” [Reuters]

I hope bolt’s dad has a Yam farm somewhere – this thing could become huge. In today’s hyper-engineered sports industry, yams could well become the next protein shake. We’ll see supermarket aisles with yam-extract products right next to the soy stuff.

Mr. bolt sr. I want to get in on the action too. That’s why I’m announcing today the secret behind Simon Wanjiru’s gold medal winning (and Olympic Record setting) performance at the Marathon. Its all about arrowroots. A healthy dose of Nyahururu arrowroots and you can run 40kms non-stop. You can place orders here.