Sunday Function

Continuing my series of basic concepts with middle school math will be tricky when we're doing a Sunday Function. But let's give it a shot, and see if we can keep it to that beginning level.


This function is pretty simple. You add reciprocals until you get reach whatever number n you've picked, then you stop. Formally the function has a name - the harmonic series. As you pick bigger and bigger n, the sum will be bigger and bigger. There's no limit to how big it will get, but clearly its growth will be pretty slow. If you want f(n) = 100, n is going to have to be pretty stinking huge.

How huge? Well, let me digress for a moment to explain logarithms. Let's say you have a statement like this one 2 * 2 * 2 * 2 = 16. You have to multiply 2 by itself 4 times to get 16. A logarithm is just how many times you have to multiply your chosen number (called a base) by itself to get the result. The base 2 logarithm of 16 is 4. The base 3 logarithm of 243 is 5, because 3 * 3 * 3 * 3 * 3 = 243. Don't worry about calculating these by hand, any decent handheld calculator can do them for you.

Now imagine that instead of 2 or 3 as your base, you use a number called e. That number happens to be about 2.71828, though like pi the digits go on forever in an irregular pattern. Why that number? It's a long story, which you'll start catching pieces of in high school. But the story won't really make all that much sense until calculus. The base e logarithm of a n is often denoted ln(n).

So accepting that little bit of weirdness, here's an unusual truth:


The approximately equals sign means that the larger n is, the better the approximation will be. So if you want to add all the reciprocals of the numbers between 1 and 1000, you don't have to actually perform every addition. You can find the logarithm of 1000 (how many times you have to multiply e by itself to get 1000) and add that correction factor. The result will be approximately f(100). The correction factor, by the way, is the Euler-Mascheroni constant. Proving this handy approximation is not difficult, but it too requires calculus so I'll save it for a future installment.

What do the numbers turn out to be for adding all the reciprocals up to 1/1000 , by the way? Here's what I get.

The actual answer: 7.48547
Our approximation: 7.48497

Not bad.

It's a little beyond our scope here to do the algebra to invert and find n given f(n). But it can be done using elementary high school algebra, and for instance if you want to add enough numbers to get f(n) = 100, n will have to be about 1.5 x 1043. Which I think you'd find to be an intractable problem of addition if you didn't know the shortcut we've done today.

More like this

Math-averse readers! Do not be scared off! You can enjoy this entry even if as far as you're concerned the equations are pretty pictures of Cypriot syllabary. Not long ago we looked at adding up lots of consecutive integers. Multiplying consecutive integers is also interesting, and not only that…
Again, apologies for the hideously scanty posting. Been in the lab doing some really interesting research which will with some luck get me in a really nice journal, as well as doing the various rounds of revision on the paper for some previous research. Also putting two talks together for a…
We begin with a joke. What's a logarithm? It's a birth control method for lumberjacks. Hahahahaha! Believe it or not, one of my high school math teachers taught me that. Actually, logarithms are a computational tool for turning products into sums. They are defined as follows. \[ \log_a b=x \…
Time for the big finale! We now have all the pieces in place to establish the divergence of the sum of the reciprocals of the primes. Recall that we have the Euler product expansion of the harmonic series: \[ \sum_{n=1}^\infty \frac{1}{n}= \prod_p \left( \frac{1}{1-\frac{1}{p}} \right) \]   We…

It's a pretty common practice to use log and ln more or less interchangeably in pure mathematics. The base 10 log is essentially extinct, since its use as a calculational device has been killed by the calculator and unlike the base e log it's not mathematically very interesting.

That said if I'm writing this at the pre-college level it does contradict the usual notation, so I think your notation is better.

Does that correction factor have anything to do with the one in Gauss's prediction of the number of primes? I remember something like that from a book I just read.

Alex, a in a nutshell yes. Leg g(x) be the product of 1-1/p where p ranges over the positive primes less than or equal to x. So g(4)=(1 -1/2)(1/-1/3) for example. Then it turns out that lim g(x)/log x = e^-gamma as x goes to infinity where gamma is the Euler-Mascheroni constant mentioned above. If one tries to make a naive heuristic based on this formula and the assumption that primes are in some sense independent of each other (this can be made more precise) for the density of the primes you expect to see that Pi(x) is asymptotic to x/(K log x) where K = e^gamma and Pi(x) is the prime counting function. However, one in fact has Pi(x) ~ x/log x. Roughly speaking this correction occurs because there are divisibility relations between the different primes.