Associated Topics || Dr. Math Home || Search Dr. Math

### Factors and Multiples - Hamiltonian Path

```
Date: 11/02/98 at 22:29:02
From: Joey Dawson
Subject: Factors and Multiples

We have to make a sequence of numbers, all different, each of which is
a factor or a multiple of the one preceding it. The numbers in this
sequence have to be from 1-100, 1 being the last number in the
sequence. An example of this is: 3-15-30-10-5-35-7-21-3. We have to
use as many numbers as possible. Everyone in my class has figured out
the most number of numbers there has to be in the sequence. Can you
help me figure out how many numbers is the most numbers there can be
in the sequence? I would appreciate it very much if you could help me.
Thank you very much.

Joey Dawson
```

```
Date: 11/04/98 at 12:01:56
From: Doctor Peterson
Subject: Re: Factors and Multiples

Hi, Joey. This is a pretty big problem. I haven't found any easy
solution. I'll just tell you how I've been looking at it and maybe you
will be able to finish it up.

I see this in terms of what we call graph theory, which has to do with
things like maps that show relations between objects. To keep things
simple, let's just work with numbers up to 12, rather than all the way
to 100. I have drawn a diagram that shows which numbers could be
adjacent in your sequence, by drawing a line between any pair of
numbers one of which is a divisor of the other:

3---12---4
/ \ /  \ / \
9   6----2---8
|
7       10
|
11       5

This says that 2 divides 4, 6, 8, 10, and 12; 3 divides 6, 9, and 12;
4 divides 8 and 12 and is a multiple of 2; 5 divides 10; 6 divides 12
and is a multiple of 2 and 3; 8, 9, 10, and 12 don't divide anything
but are multiples of other numbers. 7 and 11 divide nothing in this
range, so they are disconnected from the rest of this "graph." Of
course 1 could be connected to every number, but since it has to be
the
last number in the sequence (the answer would be a little different if
that weren't required), we don't need to show it.

You can see that 7 and 11 won't be included in any sequence you can
make, because there is no number other than 1 that they could be next
to. In general, any prime bigger than half the limit (100 in your
problem) will be neither a multiple nor a factor of any number in the
range.

The problem now is just to draw the longest path that goes through
each
number only once. That's not hard. There's one path that will go
through the whole "connected" part of the graph:

3   12---4
/ \ /      \
9   6    2---8
|
7       10
|
11       5

The longest sequence, then, is:

5, 10, 2, 8, 4, 12, 6, 3, 9, 1

(or the reverse), and includes all the numbers that could possibly
have
been in such a sequence. (This is called a "Hamiltonian path.")

I expanded this to include the numbers 1-25, and found no Hamiltonian
path through all the numbers. I had to leave out three numbers in
addition to 13, 17, 19, and 23 that are not connected to the rest. But
I'm not sure I could prove I found the longest path, without trying
all
possible paths.

With 100 numbers, it would be even harder. But at least we know a
maximum size for the path (that is, which numbers _have_ to be left
out), although we don't know whether we can actually make a path that
size until we try.

Keep playing with this, and let me know if anyone finds a way other
than brute force to find the longest sequence or to prove that you can
find a Hamiltonian path in the graph for 1-100. You may find some
feature of these particular graphs that makes it easy to find a path.

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search