LCM Optimal Sequences

The best way to learn math is to do math, which is one of the reasons I’m thrilled about the work of Antonella Catanzaro, Jaemin Feldman, Mika Higgins, Bradford Kimball, Henry Kirk, Ana Chrysa Maravelias, and Darius Sinha, who were all eighth graders at the Buckingham, Browne, and Nichols Middle School when they embarked on their own personal mathematical adventure and discovered some curious results which I’d like to draw more attention to, especially because they left behind a number of conjectures which hopefully someone might be interested in pursuing.

Their adventure began when Ms. Higgins wondered aloud whether algorithms and number theory could be combined. After some brainstorming, the group came up with the following question:

What is the least expensive path through n cities, labeled 1 through n, starting at city 1 and allowing multiple visits to a city, if the cost to travel between city a and b is the least common multiple of a and b?

Here’s a table of some examples of optimal paths.

n Cost Sample Optimal Path
1 0 1
2 2 1, 2
3 7 1, 2, 1, 3
4 12 1, 3, 1, 2, 4
5 21 1, 3, 1, 2, 4, 1, 5
6 28 1, 3, 6, 2, 4, 1, 5
7 40 1, 3, 6, 2, 4, 1, 5, 1, 7
8 51 1, 5, 1, 7, 1, 3, 6, 2, 4, 8
9 65 1, 5, 1, 7, 1, 4, 8, 2, 6, 3, 9
10 79 1, 4, 8, 2, 6, 3, 9, 1, 7, 1, 5, 10

In each optimal path, note that in every pair of adjacent numbers, one is always a multiple of the other. This is something that the seven students proved, and they proved it by showing that for positive integers x and y,

LCM(x, y) < x + y if and only if x divides y or y divides x.

In other words, if x is not a factor or multiple of y, then it is cheaper to travel from x to y via 1 than it is to travel directly from x to y, because the cost of traveling from x to 1 to y is xy, whereas the cost of traveling from x straight to y is LCM(xy). A corollary of this fact is that prime numbers greater than n/2 will always be sandwiched by ones in an optimal path, unless the prime occurs at the very end of the path.

They showed that there always exists an optimal path that visits numbers greater than 1 exactly once, as all of the optimal paths in the table do. And they showed that when n is prime, all optimal paths end in n, but this is not necessarily true when n is composite as the example for n = 6 in the table above shows. Through their math department chair, the seven submitted the sequence of optimal costs to the Online Encyclopedia of Integer Sequences, and it was recently approved as sequence A333354. For details, see pages 13-19 of Volume 13, Number 4 of the Girls’ Angle Bulletin which can be accessed for free at the Girls’ Angle website.

Here are some conjectures and avenues for further investigation:

  • For a given n, do all optimal paths have the same length?
  • What are good upper and lower bounds on the minimal cost sequence?
  • What can be said if you replace the cost of travel between a and b with the highest power of 2 that divides one of the two numbers?
  • What is an efficient way to generate optimal paths for n > 20?

They determined the minimal cost for n up to 20, and for prime n below 20, the costs are:

n 2 3 5 7 11 13 17 19
Cost 2 7 21 40 100 138 238 295

In every prime case listed above, the minimal cost is equal to

\displaystyle n + 2(\sum_{k=(n+1)/2}^{n-1} k) + (\sum_{k=\lceil n/3 \rceil}^{(n-1)/2} k).

Is that true for all prime numbers n?

If you find anything, please do let us know at girlsangle “at” gmail.com!

About girlsangle

We're a math club for girls.
This entry was posted in math and tagged , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s