Confounding Factors
September 24, 2010 at 6:07 pm 1 comment
My colleague Julia is preparing a talk about factoring for an elementary audience, and she created the following problem to use as a warm-up:
Take a two‑digit number ab, and find the least common multiple of a, b, and ab. For example, if you take the number 35, then LCM(3, 5, 35) = 105. For which two‑digit number ab is LCM(a, b, ab) the greatest? (The notation ab is used to indicate the two‑digit number with tens digit a and units digit b, which is equal to 10a + b. This notation is used to distinguish the two‑digit number ab from the product ab.)
Here are some math jokes about factors:
What do you call an amount that exactly divides a recipe for a sweet confection?
A fudge factor.What do algebra equations and British television have in common?
An X Factor.
Sadly, both of those are my original jokes. Sorry. To cleanse your palate, check out one of Randall Munroe’s original jokes about factoring:
Entry filed under: Uncategorized. Tags: factor, jokes, problem, x factor, xkcd.
1.
xander | September 25, 2010 at 12:29 am
The answer to the warm up is 89.
For simplicity, let c = MAX(10a+b,10b+a).
In general, LCM(a,b,c) = a*b*c/GCD(a,b,c). Intuitively, we want to maximize the numerator while minimizing the denominator.
The smallest possible denominator occurs when a, b, and c are relatively prime, so it would be great to find three numbers that are relatively prime.
To maximize the numerator, we can start by examining the maximum possible values for a and b. So take a=9 and b=8. 9 and 8 are relatively prime, so we are in business thus far. 98 and 8 share common factor (i.e. 2), but 89 is relatively prime to both 9 and 8, so 89 is a good candidate. LCM(9,8,89) = 8*9*89 = 6408.
a=9 and b=7 is another possible candidate. 97 is relatively prime to 9 and 7, thus LCM(9,7,97) = 9*7*97 = 6111. As 6111<6408, we can dismiss 97 as a candidate number.
All other candidates are inferior to those listed above. At best, we would have LCM(a,b,c) = a*b*c, where a ≤9, b<7 and c<97. Hence a*b*c<6111<6408.
Therefore 89 is the two digit number which maximizes LCM(a,b,c).
I don’t find this solution to be entirely satisfactory, as it ultimately relies upon some brute forcing or guess-and-checking (i.e. several candidate numbers need to be selected and tested), but I can’t come up with anything better/more generalizable.
As an added note, brute forcing in C gave the same result.
xander