This week’s “Riddler Classic” puzzle, from FiveThirtyEight:

From Itay Bavly, a chain-link number problem:

You start with the integers from one to 100, inclusive, and you want to organize them into a chain. The only rules for building this chain are that you can only use each number once and that each number must be adjacent in the chain to one of its factors or multiples. For example, you might build the chain:

4, 12, 24, 6, 60, 30, 10, 100, 25, 5, 1, 97

You have no numbers left to place after 97, leaving you with a finished chain of length 12.

What is the longest chain you can build?

It turns out this question is literally as old as I am. Carl Pomerance wrote a paper On the longest simple path in the divisor graph, C. Pomerance, Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983, Cong. Num. 40 (1983), 291–304. The result of this paper is that if is the length of the longest chain in , then . That is, as gets large, we can’t “use up” a constant fraction of the integers. This paper was dedicated to Erdos on his seventieth birthday.

But the paper is not constructive. The natural thing to do is to think of this as a graph-theory problem. Construct a graph with vertices latex a$ to if . But finding the longest path in a graph is NP-hard.

For example, with this graph appears as follows:

and you can see that 7 is going to cause something of a problem. If we just avoid it we can find the path

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

so . You can also see something of the structure of this problem – numbers which share prime factors cluster together in the graph, and we end up putting numbers with the same prime factors together in the sequence. Here all the multiples of three are at the beginning, all the multiples of two in the middle, and all the multiples of five at the end.

In fact , which we can figure out by arguing around 7. We can’t have a path that has 7 in the middle because 7 has degree 1 in this graph, so if 7 occurs at all it must occur at the start or the end. Without loss of generality let’s say we have a path that starts with 7, of length 10 We must have 7, 1, and then a path in this graph that goes through all eight vertices:

but such a path clearly doesn’t exist – if it existed it would have to go between the two vertices of degree 1, which are 9 and 5, but one can’t navigate properly around 2.

So what to do? I know nothing better than trial and error. We can quickly build the following path of length 30:

64, 32, 96, 48, 16, 8, 24, 72, 36, 12, 4, 2, 6, 18, 54, 27, 9, 81, 3, 1, 5, 15, 45, 90, 30, 10, 60, 20, 40, 80

which basically zig-zags through the 3-smooth numbers (that is, numbers with all factors 2 and 3) and then the numbers you get if you multiply those by 5. Then we want to insert little excursions out along different primes. For example between 3 and 1 we can insert

3, 51, 17, 68, 34, 1

which is essentially the path 3, 1, 4, 2 multiplied by 17. Doing a few of these insertions gives a length-49 sequence

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 84, 28, 7, 14,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 9, 81,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 15, 45, 90, 30, 10, 60, 20, 40, 80

where I’ve bolded the newly inserted bits, which go “out along” the primes 7, 11, 17, and 19 respectively. (Don’t ask me what happened to 13.) We can keep hacking away at this, for example sticking some multiples of 25 in between 5 and 15 to get

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 84, 28, 7, 14,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 9, 81,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 100, 50, 25, 75, 15, 45, 90, 30, 10, 60, 20, 40, 80

Since there are no 13s in here, let’s put them in. One way to do this is in the second line, which we can replace with the second and third lines here:

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 56, 14, 42, 21, 84, 28,
7, 91, 13, 39, 78, 26, 52,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 9, 81,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 100, 50, 25, 75, 15, 45, 90, 30, 10, 60, 20, 40, 80

and this has length 62. Things get trickier now – the idea becomes to look for numbers that aren’t in the sequence but have all their factors small. 63 isn’t in the sequence and it feels insertable, and if we replace 27, 9, 81, 3 with 27, 81, 9, 63, 3 we can do it. A few more little moves like this get us up to length 67:

64, 32, 96, 48, 16, 8, 24, 72, 36, 12,
4, 84, 28, 56, 14, 98, 49,
7, 91, 13, 39, 78, 26, 52,
2, 88, 44, 22, 11, 99, 33, 66,
6, 18, 54, 27, 81,
9, 63, 21, 42,
3, 51, 17, 68, 34,
1, 38, 76, 19, 95,
5, 80, 40, 20, 100, 50, 25, 75,
15, 45, 90, 30, 60, 10, 70, 35

which is the solution I submitted.

The “missing” numbers now are

23 29 31 37 41 43 46 47 53 55 57 58 59 61 62 65 67 69 71 73 74 77 79 82 83 85 86 87 89 92 93 94 97

and you can see what the basic problem ends up being.  All of these have at least one prime factor that’s greater than or equal to 11. Can we squeeze any of these in? In particular 55 and 77 seem like they could be inserted along this basic route, although I can’t figure out how.