## 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 ofa,b, andab.For example, if you take the number 35, then LCM(3, 5, 35) = 105. For which two‑digit numberabis LCM(a,b,ab) the greatest? (The notationabis used to indicate the two‑digit number with tens digitaand units digitb, which is equal to 10a+b. This notation is used to distinguish the two‑digit numberabfrom the productab.)

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