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.