Skip to main content

Combinatorics and LCMs

Working through the problems in Niven's book on combinatorics, I came across the following one that cleverly introduces least-common-multiples without saying any of those words.  The book asks the following question:

How many numbers that are evenly divisible by 11 exist between 1 and 2000?  How many that aren't also evenly divisible by 3?  How many numbers that are evenly divisible by 6, but not by 4 exist between 1 and 2000?

The hastily scribbled answer can be seen below, with each of the answers boxed in succession down the screen.

By simply dividing 2000 by 11, we find out how many integers between 1 and 2000 are evenly divisible by 11.  In other words, we ask how many multiples of 11 can fit between 1 and 2000.  When we want to eliminate the multiples of 3, that's when the least common multiple comes in.  We already have the answer for all numbers divisible by 11, but how to eliminate those also divisible by 3?  By first asking what number divisible by 11 are also divisible by three, we arrive at an answer.  The first number divisible by both is 33, or 3 X 11.  Then next is 66, and then 99, and so on, (if you're working it out by hand, it's easier to count by 11's than 3's).  As it turns out, only multiples of the least common multiple (LCM) of 3 and 11, (33), are divisible by both 3 and 11.  Now, we just need to figure out how many copies of numbers divisible by 33 are between 1 and 2000, and then subtract that number from the total number of integers divisible by 11 we calculated earlier to get the answer to the 'divisible by 11, but not 3' question.

The divisible by 6, but not 4 questions is similar.  In this case, the lowest common multiple of 6 and 4, in other words, the smallest number they'll both divide evenly, is 12.  By removing all the numbers divisible by 12 from 1 to 2000 from the count of integers between 1 and 2000 that are divisible by 6, we wind up with the answer to "How many integers between 1 and 2000 are divisible by 6, but not by 4?"


Comments

Popular posts from this blog

Cool Math Tricks: Deriving the Divergence, (Del or Nabla) into New (Cylindrical) Coordinate Systems

The following is a pretty lengthy procedure, but converting the divergence, (nabla, del) operator between coordinate systems comes up pretty often. While there are tables for converting between common coordinate systems, there seem to be fewer explanations of the procedure for deriving the conversion, so here goes!

What do we actually want?

To convert the Cartesian nabla



to the nabla for another coordinate system, say… cylindrical coordinates.



What we’ll need:

1. The Cartesian Nabla:



2. A set of equations relating the Cartesian coordinates to cylindrical coordinates:



3. A set of equations relating the Cartesian basis vectors to the basis vectors of the new coordinate system:



How to do it:

Use the chain rule for differentiation to convert the derivatives with respect to the Cartesian variables to derivatives with respect to the cylindrical variables.

The chain rule can be used to convert a differential operator in terms of one variable into a series of differential operators in terms of othe…

The Valentine's Day Magnetic Monopole

There's an assymetry to the form of the two Maxwell's equations shown in picture 1.  While the divergence of the electric field is proportional to the electric charge density at a given point, the divergence of the magnetic field is equal to zero.  This is typically explained in the following way.  While we know that electrons, the fundamental electric charge carriers exist, evidence seems to indicate that magnetic monopoles, the particles that would carry magnetic 'charge', either don't exist, or, the energies required to create them are so high that they are exceedingly rare.  That doesn't stop us from looking for them though!

Keeping with the theme of Fairbank[1] and his academic progeny over the semester break, today's post is about the discovery of a magnetic monopole candidate event by one of the Fairbank's graduate students, Blas Cabrera[2].  Cabrera was utilizing a loop type of magnetic monopole detector.  Its operation is in concept very simpl…

The Javascript Google URL Shortener Client API

I was working with the Google API Javascript Client this week to shorten the URLs of Google static maps generated by my ham radio QSL mapper. The client interface provided by Google is very useful. It took me a while to work through some of the less clear documentation, so I thought I'd add a few notes that would have helped me here. First, you only need to authenticate your application to the url shortener application if you want to track statistics on your shortened urls. If you just want the shortened URL, you don't need to worry about this. The worst part for me was that the smaple code only showed how to get a long url from an already shortened rul. If you follow the doucmentaiotn on the insert method, (the method for getting a shortened url from a long one), there is a reference to a rather nebulous Url resource required argument. It's not at all clear how to create one of these in Javascript. The following example code shows how:
var request = gapi.clie…