Scanning for π

In a previous episode, we looked at how we could use random sampling to get a good estimate of , and found that we couldn’t, really, unless using zillions of samples. The imprecision of the estimated had nothing to do with the “machine precision”, the precision at which the machine represents numbers. The method essentially counted (using size_t, a 64-bits unsigned integer—at least on my box) the number of (random) points inside the circle versus the total number of points drawn.

Can we increase the precision of the estimate by using a better method? Maybe something like numerical integration?

Amicable Numbers (part I)

I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let be a natural number (a positive integer), and let

with and , be the sum of the divisors of . We’re in fact interested in the sum of the proper divisors of , that is,

Now we’re ready to define amicable numbers!

Amicable numbers: Two numbers, are amicable, if, and only if, and .

Given , we can find and test if . But to do that efficiently, we need to compute (or ) very rapidly. The first expression above requires , but we can do much better. Let’s see how.

Computing Binomials (Part I)

We often start thinking about something, make some progress, and eventually realize it’s not going anywhere, or, anyway, the results aren’t very phrasmotic—certainly not what you hoped for. Well, this week’s post is one of those experiments.

So I was wondering, how can I compute the binomial coefficient, , and minimize the size of the integers involved?

Of Drunkards

In a city with orthogonal streets and regular city block, a party-goer leaves a bar and walks back home. His home is North East from the bar, blocks up, and blocks east. At each intersection, he decide to go either north or east randomly—but whatever’s left of his sobriety keeps from backtracking: he always moves closer to home. How many ways can the drunkard get get back home?

Best. Number Base. Ever.

One of the first things we learn when we begin programming is that there are different number bases: base 10, the usual one, but also binary, octal, and hexadecimal. Their expressive power is strictly equivalent, but we also notice that hexadecimal numbers are written much more compactly than binary, and so, hexadecimal is “more efficient.”

But “efficiency” begs the question: how do we define it, and, once efficiency defined, which base is the best? Let’s find out!

The conjecture of 8

The other day I found an amusing short from numberphile about “happy numbers”. Not unlike the Collatz problem, a number is happy if, through successive transformations, it reaches one. The transformation is rather numerological in nature (i.e., it’s arbitrary and so why not): To get the next number in the series to happiness, you take the current number and sum the squares of its digits.

The example in the video is that is a happy number:

Therefore is a happy number. That’s cool, but are all numbers happy, and, if not, what happens when a number is unhappy?

π by rejection

In the 18th century, Georges-Louis Leclerc, Count of Buffon, proposed an experiment to estimate . The experiment (now somewhat famous as it appears in almost all probability textbooks) consists in dropping randomly matches on a floor made of parallel floorboards and using the number of time the matches land across a junction to estimate .

To perform the Count’s experiment, you do not need a lot of math. You only need to test if

with and are both uniform random variables, and is the width of the floorboards. You may remark that we use and that it looks like a circular definition until you think that radians is 45°, and you can estimate it using other means. Then you start throwing zillions of virtual matches and count the number of intersections, then use a laboriously obtained probability distribution to estimate .

Lucky for us, there’s a variant that does not require the call to sines, not complicated integrals. Just squaring, counting, and a division. Let’s have a look.

Strange Change

A classical example of a greedy algorithm is the algorithm to return change given a set of face values. In Canada (and the US) the usual coins are 25¢, 10¢, 5¢ and 1¢ coins—there’s also a 50¢ coin, but they’re rare nowadays. The algorithm proceeds as follows. You are given a number of cents to return, and you start with the highest face value, . You subtract from the numbers of cents while the number of cents still to return is greater or equal to . If the number of cents still to return is smaller than but not zero, you repeat using the next denomination, , then if there’s still some, with , etc. Eventually, you return all the change, using a minimal number of coins.

So the next interesting question is whether our current coinage is optimal, as measured by the (average) quantity of returned change? No. It’s not. Let’s see why.

Euclid and Primality Testing (III)

So in previous installments, we looked at how to use the euclidean algorithm to devise a Las Vegas-type algorithm for primality testing. We also found that, in general, simply testing factors one after the other is much more efficient (but that doesn’t mean that there are not better algorithms to test for primality!).

We also considered only relatively small primorials (the products of the first prime numbers) since they rapidly exceeded . But just how fast do primorials grow?

Euclid, Primes numbers, and a Bit of Algorithm Analysis

Last time we had a look at using the greatest common divisor and Euclid’s algorithm to devise a Las Vegas algorithm for primality testing. We also had a look at how the inclusion exclusion principle helps us determine the proportion of the numbers correctly tested.

However, we finished by asking ourselves if the method is actually efficient compared to, say, simply testing small divisors, one by one. Let us now find out.