Built on Facts

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.

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

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:

i-88516ca505d84f969b7ab15a965c3fb3-2.png

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.

Comments

  1. #1 Paul
    February 8, 2009

    shouldn’t the formula be f(n)=Ln(n)+0.57721 instead of Log(n)?

  2. #2 Matt Springer
    February 8, 2009

    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.

  3. #3 Alex
    February 8, 2009

    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.

  4. #4 Joshua Zelinsky
    February 8, 2009

    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.

  5. #5 Kobra
    February 10, 2009

    How did they come up with the constant? The closest I got was e^(e-1)/10.

  6. #6 andyb
    February 13, 2009
    Sorry, now I feel better.