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

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...

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

Now available as a Kindle ebook for 99 cents ! Get a spiffy ebook, and fund more physics 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 ...

More Cowbell! Record Production using Google Forms and Charts

First, the what : This article shows how to embed a new Google Form into any web page. To demonstrate ths, a chart and form that allow blog readers to control the recording levels of each instrument in Blue Oyster Cult's "(Don't Fear) The Reaper" is used. HTML code from the Google version of the form included on this page is shown and the parts that need to be modified are highlighted. Next, the why : Google recently released an e-mail form feature that allows users of Google Documents to create an e-mail a form that automatically places each user's input into an associated spreadsheet. As it turns out, with a little bit of work, the forms that are created by Google Docs can be embedded into any web page. Now, The Goods: Click on the instrument you want turned up, click the submit button and then refresh the page. Through the magic of Google Forms as soon as you click on submit and refresh this web page, the data chart will update immediately. Turn up the:...

Copasetic Flow

Search This Blog