Amicable Numbers (Part II)

In the first part we discussed how to compute the sum of proper divisors function from the sum of divisors function, . We saw that if we factorize the number then compute the list divisors from prime factor, it was much faster (on average) than testing each possible numbers from to (or , since we get one large divisor for every small divisors).

So now, let’s all put that together to get an efficient program that enumerates amicable pairs. First, we obtain a list of primes (not missing any) where the largest prime is , the largest number we will be testing—we need it to compute (up to) . If we were to search for all amicable numbers, the list would need to be unbounded, maybe we would need to produce it as we go along; but if we look for amicable pairs up to, say, about , we only need primes up to (and there’sn’t that many of them). For the sake of efficiency, we also need a way of not testing a number twice.

The Sieve of Eratosthenes

The Ancient Greeks never fail to amaze me. Sometimes their ideas border the merely superstitious, sometimes you find a guy like Eratosthenes (c. 275 BC – c. 195 BC) that comes up with a truly modern idea. I’m not talking about his invention of geography (in the modern sense of the word) nor about his suspiciously accurate estimate of Earth’s size. No, I’m talking about an algorithm that has a very modern feel to it: the sieve of Eratosthenes

So what is it that I find so modern about this algorithm? Well, it has a computational feel to it, replacing smarts with a simple procedure, regular and repetitive. So, how hard is Eratosthenes’ sieve to implement? Not every: about 10 lines of code is needed in C++ (and possibly quite fewer if we use some other language).

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.