Let's say you sit in a pub, minding your own business, when all of a sudden a stranger walks up to you and offers you a bet:
We'll choose two positive integers at random. If they have any divisor in common (other than ) I'll pay you a dollar, else you'll pay me a dollar. Are you in?
Apart from the question what kind of establishments you frequent, you should be wondering: is this a good bet for you?
When two integers have no divisors in common except the trivial divisor we say they are coprime or relatively prime. and have the common divisor , so they are not coprime, whilst and only have the trivial common divisor , so they are coprime.
This makes you start thinking: "As numbers grow bigger, aren't there a lot of divisors out there? After all, half the numbers are even, so if we hit two even numbers, they'll have the factor in common and I'll win. And then there's , , , ... Seems like a good deal!" Continue reading The Prime Bet→
In the past months, I spent as much time as I had on taking online courses at Coursera. One particularly interesting course, both from a mathematical and computational point of view, is Analytic Combinatorics which applies combinatorics (i.e., the art of counting) to the analysis of algorithms by finding formulae, exact or asymptotic, for their running time.
It is notoriously difficult to find exact formulae for general combinatorial constructs. Typically, we want to know how many objects, e.g., trees, permutations, sequences, with certain properties there are of a given size. Famously, the number of binary trees (and about a million other constructions) is governed by the Catalan numbers
I recently spent some time on the formidable website Numberphile which explains mathematical ideas, some important, some recreational, in short and accessible videos. Definitely worth checking out. One of the videos that is most relevant to us explains the Riemann Hypothesis: