Dave's Free Press

Graphing tool

I made a shiny thing! It can plot arbitrary functions of the form x=f(y) or y=f(x). Under the skin, it just massages its arguments and passes them through to Gnuplot. Here's the source code.

Update: now 48.3% even shinier - see on the right

Optimising n! - revisited again

For the background, see this post and this post.

I have had An Branewave! When I said that

  100! = 2⁵⁰ * 3³³ * 5²⁰ * 7¹⁴ * 11⁹ * ...

was wrong (which it is) I stupidly didn't realise that there is a pattern to the missing terms. The 2⁵⁰ comes from observing that there a 50 multiples of 2 less than or equal to 100. There are also 25 multiples of 4 (also known as 2²), 12 multiples of 8 (aka 2³), 6 multiples of 2⁴, 3 multiples of 2⁵, and 1 of 2⁶. the 25 multiples of 4 contribute another 2²⁵. The 12 multiples of 8 (which of course are also multiples of 4) contribute another 2¹², and so on.

So we see that 100! is divisible by 2^{50 + 25 + 12 + 6 + 3 + 1}, or 2⁹⁷.

There is, of course, a similar pattern for all the other prime factors.

Combining functions

There was a great programme on Radio 4 yesterday about Newton and Leibnitz. I'm not sure why, but it inspired me to consider the curve that is constructed from y = x² when x <= 0, and y = x when x > 0 . I want to reduce that to a single function.

It can obviously be done.

Consider that to fit a curve to any^* three points, you can do it with a curve y = a + bx + cx². Figuring out the three constants a, b and c is trivial, you just solve three simultaneous equations. Similarly, for four points, you fit y = a + bx + cx² + dx³, and so on. To accurately fit the curve I described at the beginning, you need an infinite number of points, thus an infinite number of constants.

I'm sure that this can be done - obviously you can't actually calculate an infinite number of constants, but I'm sure that with a bit of integration it could be done. And it can be done for any such pair of functions which meet at a point. However, on further reflection I'm not entirely convinced that it can be done in the general case - you have that pesky discontinuous yes/no conditional in the middle: "is x <= n?".

* not strictly true - consider (0,0), (0,1), (1,0).

Factoring Factorials

Take a factorial. Any factorial. Factor it*. Notice a Pattern.

That pattern is that if you list all of the prime factors in order and the number of times they appear, at no point does any larger factor appear more often than any smaller factor. This would appear to be obvious, and it "obviously" applies to all factorials** (I've verified it by hand up to 28!, at which point I got bored). But I'm finding it hard to put a proof into words - or more concisely but equivalently - into symbols.

* this is easy. While factoring 1124000727777607680000 might be quite hard, if you know that it's 22! it becomes trivial because we know that it is divisible by 2, 3, 4, 5, ..., 21, 22, each of which is trivially factorable. Given that each number is the product of a unique set*** of factors, the factors of 22! can only be the set of all the factors of all the numbers we multipled to get 22!. Easy!

** it becomes obvious when you consider Eratosthenes' method for testing primality.

*** yes, I know, it's not really a set.

Umbrellas

What's the point of umbrellas? To be effective, their diameter needs to be slightly more than h * sin(ϑ) (where h is your height and ϑ is the angle of the rain from the vertical). So, if rain is falling vertically you need an umbrella with diameter slightly more than* the width of your shoulders. If rain is going horizontally, you need an umbrella slightly wider than you are tall. If rain is coming down at 20° from the vertical, you need an umbrella diameter just over 0.34 * your height, and so on.

Given that rain can subtend any angle from 0 to 90° from the vertical, then unless you wish to be your umbrella supplier's very best friend in the whole world, you need a Very Large umbrella. And yet, no-one carries such a thing. Indeed, I don't think anyone makes such a thing suitable for anyone other than midgets. So we see that every umbrella user has, from the point of view of keeping themselves dry, made the wrong decision. Their partial solutions are no better than what they would achieve by wearing a good coat and a hat.

Unfortunately, their partial solutions come at the cost to everyone else of getting poked in the face by the metal spikes at the edge of the umbrella.

* the value of "slightly more" is a function of ϑ and the shape of the human body. A good approximation would be to assume that a person's width is h/3 and their depth is h/4.

Optimising n! - revisited

For the background, see this post.

Late one night I thought that you might be able to simplify n-factorial thus:

Take the product of p(i)^int(n/p(i)) for i=1 to i=Φ(n). Damnit, I wish there was a good and easy way of writing mathemagics on t'interwebnet.

Where:

• n is the number whose factorial we wish to calculate;
• p(i) is the ith prime number;
• Φ(n) is the number of primes less than or equal to n

Now, without using a lookup table, p() and Φ() are hard to calculate, but at least you'd avoid a lot of the problems that come from using the stupendously big numbers that come as intermediate results in calculating factorials.

Unfortunately, that formula is wrong anyway. It's a restatement of this:

100! = 2⁵⁰ * 3³³ * 5²⁰ * 7¹⁴ * 11⁹ * ...

which came from noticing that 100! is the product of 50 numbers which have 2 as a prime factor, 33 numbers which have 3 as a prime factor, 20 numbers that have 5 as a prime factor, and so on. Unfortunately, it doesn't take account of numbers like 4 and 18 which have a repeated prime factor - 4, for example, is 2 * 2 and 18 is 2 * 3 * 3. Bother.

Wikipedia: WRONG AGAIN

Wikipedia has a reputation for being of rather low quality, particularly in the humanities. In the sciences and technology it is supposed to be pretty good. But today, I found an error in their article about ... the triangle. One of the most basic mathematical concepts. And they got it wrong. Joy.

OK, to be fair, it's only subtlely wrong, is correct for the majority of cases, and one could argue that the context in which the inaccurate information is presented makes it OK. But I disagree.

In a section called "Basic facts" they first mention that triangles were described thoroughly by Euclid. Good. In the next paragraph, they say that the internal angles add up to 180°. Not so good. They only do so in some spaces, the most commonly known of which is the Euclidean space. Anyway [click click click type click] I've fixed it now. I wonder how long it'll stay fixed, or whether some wanker will revert my pedantry.

Optimising n!

If you want to add up all the numbers from 1 to n, you can do it two ways. The slow, inefficient way is to calculate:

1 + 2 + 3 + ... + n

The quick way is to remember what you were taught in school, that:

1 + 2 + 3 + 4 + 5 + 6 = (6 + 1) + (2 + 5) + (3 + 4) = 7 + 7 + 7

and that in general:

1 + 2 + ... + n = n(n+1)/2

This optimisation might not matter for small values of n, but for n = 1000000 it really makes a big difference. This got me thinking whether there was a similar trick for calculating the product of all numbers from 1 to n - that is, n-factorial, or n!.

This matters even more for n! because it gets so large so quickly that computers are unable to accurately represent the intermediate values. In fact, 20! is the largest that can be respresented on a 64 bit machine. 21! can only be approximated, as you need to use a floating point number. This means that not only is calculating really big factorials time-consuming, it's not possible at all to do it accurately with native datatypes.

I don't even know if there is a simple re-statement of n! like there is for the sum above, but I'm gonna spend a few idle minutes working on it.