Dave's Free Press: Journal

violence, pornography, and rude words for the web generation


Recent posts


Recently commented posts


Journals what I read

geeky politics rant silly religion meta music perl weird drinking culture london language transport sport olympics hacking media maths web photography etiquette spam amazon film bastards books bryar holidays palm telecoms cars travel yapc bbc clothes rsnapshot phone whisky security home radio lolcats deafness environment curry art work privacy iphone linux unix go business engineering kindle gps economics latin anglo-saxon money bramble cars environment electronics
Wed, 30 Sep 2009

Optimising n! - revisited again

For the background, see this post and this post.

I have had An Branewave! When I said that

  100! = 250 * 333 * 520 * 714 * 119 * ...

was wrong (which it is) I stupidly didn't realise that there is a pattern to the missing terms. The 250 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 22), 12 multiples of 8 (aka 23), 6 multiples of 24, 3 multiples of 25, and 1 of 26. the 25 multiples of 4 contribute another 225. The 12 multiples of 8 (which of course are also multiples of 4) contribute another 212, and so on.

So we see that 100! is divisible by 250 + 25 + 12 + 6 + 3 + 1, or 297.

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

Posted at 01:44 by David Cantrell
keywords: geeky | maths
Permalink | 0 Comments

Sorry, this post is too old for you to comment on it.