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…

Lost Phone

We were incredibly lucky to have both been in university settings when our kids were born.  When No. 1 arrived, we were both still grad students.  Not long after No. 2 arrived, (about 10 days to be exact), mom-person defended her dissertation and gained the appellation prependage Dr. 

While there are lots of perks attendant to grad school, not the least of them phenomenal health insurance, that’s not the one that’s come to mind for me just now.  The one I’m most grateful for at the moment with respect to our kids was the opportunities for sheer independence.  Most days, we’d meet for lunch on the quad of whatever university we were hanging out at at the time, (physics research requires a bit of travel), to eat lunch.  During those lunches, the kids could crawl, toddle, or jog off into the distance.  There were no roads, and therefore no cars.  And, I realize now with a certain wistful bliss I had no knowledge of at the time, there were also very few people at hand that new what a baby…

Lab Book 2014_07_10 More NaI Characterization

Summary: Much more plunking around with the NaI detector and sources today.  A Pb shield was built to eliminate cosmic ray muons as well as potassium 40 radiation from the concreted building.  The spectra are much cleaner, but still don't have the count rates or distinctive peaks that are expected.
New to the experiment?  Scroll to the bottom to see background and get caught up.
Lab Book Threshold for the QVT is currently set at -1.49 volts.  Remember to divide this by 100 to get the actual threshold voltage. A new spectrum recording the lines of all three sources, Cs 137, Co 60, and Sr 90, was started at approximately 10:55. Took data for about an hour.
Started the Cs 137 only spectrum at about 11:55 AM

Here’s the no-source background from yesterday
In comparison, here’s the 3 source spectrum from this morning.

The three source spectrum shows peak structure not exhibited by the background alone. I forgot to take scope pictures of the Cs137 run. I do however, have the printout, and…