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

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 rule can be used to convert a differe…

Division: Distributing the Work

Our unschooling math comes in bits and pieces.  The oldest kid here, seven year-old No. 1 loves math problems, so math moves along pretty fast for her.  Here’s how she arrived at the distributive property recently.  Tldr; it came about only because she needed it.
“Give me a math problem!” No. 1 asked Mom-person.

“OK, what’s 18 divided by 2?  But, you’re going to have to do it as you walk.  You and Dad need to head out.”

And so, No. 1 and I found ourselves headed out on our mini-adventure with a new math problem to discuss.

One looked at the ceiling of the library lost in thought as we walked.  She glanced down at her fingers for a moment.  “Is it six?”

“I don’t know, let’s see,” I hedged.  “What’s two times six?  Is it eighteen?”

One looked at me hopefully heading back into her mental math.

I needed to visit the restroom before we left, so I hurried her calculation along.  “What’s two times five?”

I got a grin, and another look indicating she was thinking about that one.

I flashed eac…

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…