Problem of the Month (November 1998)

A divisor chain is a sequence of distinct positive integers with the following property: in every consecutive pair of numbers one divides the other. For example, 7 1 3 6 2 8 is a divisor chain since 7/1, 3/1, 6/3, 6/2, and 8/2 all divide evenly.

Notice that the largest number in the above chain is 8. Let S(n) be the smallest possible value of the largest number in a divisor chain of length n. It is easy to see that S(n)>n for some values of n. When n is large, there are at least 3 primes between n/2 and n, and these would all need to be next to 1 in any divisor sequence, an impossibility. What are the best results you can find for larger n? Can you prove your results?


ANSWERS

Many solvers mentioned that when n>3, only one prime between n/2 and n can be in the chain. This fact alone is enough to prove many of the small values of S(n).

John Hoffman found the values of S(n) for n≤30 and 38≤n≤41 using a computer. He also has conjectures for n=31 and n=32. His algorithm is complicated, and is difficult to implement for 31≤n≤37.

Hoffman asked why there are at least 3 primes between n/2 and n for large n. If we let π(n) be the number of primes less than n, then the Prime Number Theorem says π(n) / (n log n) converges to 1. This means that we can pick n large enough so that π(n) / (n log n) > .8 and π(n/2) / ( (n/2) log (n/2) ) < 1.2 . Then the number of primes between n/2 and n is:

π(n) - π(n/2) > .8 n log n - .6 n (log n - log 2) = .2 n (log n - 3 log 2) n > 3.

Hoffman (like most of the others) considered the dual problem of finding the longest chain containing only the numbers {1,2,3, . . .,n}. He managed to find several upper and lower bounds on L(n), the length of the longest such chain. Note that S(k)=n iff L(n-1)<k and L(n)≥k.

His lower bounds include:

His upper bounds include:

Brendan Owen found the values of S(n) for n≤30, with a computer program written in c++.

Mike Keith found the values of S(n) for n≤29 using a computer search. He notes that the values of S(n) - n have an interesting pattern, at least until n=29:

0 0 0 0 1
0 1 1 1 2
1 2 2 2 3
2 3 3 3 4
3 4 4 4 5
4 5 5 6  
Joseph DeVincentis gave the best values for n≤26, which he did by hand! He managed to prove the values of S(n) for n≤19 and n=21.

His argument that S(10)>11 is typical. If there were a divisor chain of length 10 with largest element 11, then it can not contain 7, so replace 11 with 7 to get a divisor chain of length 10 with largest element 10, which is impossible by the last paragraph. In fact, this argument can be generalized to show that S(n) is not a prime p if there is another prime between p/2 and p.

Robert Pratt gave the best values for n≤16. He proved the values of S(n) for n≤13 by exhaustive search. He formulated the problem as a graph theory problem, and looked for long paths in the "divisor graph" using some Mathematica programs he wrote for this purpose.

The sequence of values of S(n): 1, 2, 3, 4, 6, 6, 8, 9, 10, 12, 12, 14, 15, 16, 18, 18, 20, 21, 22, 24, 24, 26, 27, 28, 30, 30, 32, 33, 35, 36, . . . is now sequence A034298 of the Encyclopedia of Integer Sequences.

Sasha Ravsky showed that L(n) ≥ 2√(2n) - 4 for n ≥ 18. He does this by starting with a sequence of numbers {a, b+k, a+1, b+k-1, a+2, b+k-2, . . . , a+k, b} for carefully chosen a, b, and k, and inserts between every two numbers their product, obtaining a divisor chain of length 4k-1 with numbers no larger than 2(a+k)2.

The table below gives the values of S(n):

Smallest Divisor Chains of Length n

n S(n)Example
11 1
22 1 2
33 3 1 2
44 3 1 2 4
56 1 3 6 2 4
66 3 6 2 4 1 5
78 3 6 2 4 8 1 5
89 4 8 2 6 3 9 1 5
910 4 8 1 5 10 2 6 3 9
1012 1 5 10 2 8 4 12 6 3 9
1112 5 10 2 8 4 12 6 3 9 1 7
1214 5 10 1 7 14 2 8 4 12 6 3 9
1315 6 12 4 8 1 7 14 2 10 5 15 3 9
1416 6 12 4 8 16 1 7 14 2 10 5 15 3 9
1518 1 7 14 2 8 16 4 12 6 18 9 3 15 5 10
1618 7 14 2 8 16 4 12 6 18 9 3 15 5 10 1 11
1720 20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 1 11
1821 20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 21 1 11
1922 20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 21 1 11 22
2024 20 10 5 15 3 9 18 6 12 24 4 16 8 2 14 7 21 1 11 22
2124 15 5 10 20 4 16 8 24 12 6 18 9 3 21 7 14 2 22 11 1 13
2226 15 5 10 20 4 16 8 24 12 6 18 9 3 21 7 14 2 22 11 1 13 26
2327 15 5 10 20 4 16 8 24 12 6 18 9 27 3 21 7 14 2 22 11 1 13 26
2428 15 5 10 20 4 16 8 24 12 6 18 9 27 3 21 7 28 14 2 22 11 1 13 26
2530 30 15 5 10 20 4 16 8 24 12 6 18 9 27 3 21 7 28 14 2 22 11 1 13 26
2630 11 22 2 28 14 7 21 3 27 9 18 6 12 24 8 16 4 20 10 30 15 5 25 1 26 13
2732 11 22 2 32 16 8 24 12 6 18 9 27 3 21 7 14 28 4 20 10 30 15 5 25 1 26 13
2833 13 26 2 32 16 8 24 12 6 18 9 27 3 33 11 22 1 25 5 15 30 10 20 4 28 14 7 21
2935 13 26 2 34 17 1 28 14 7 35 5 15 30 10 20 4 32 16 8 24 12 6 18 9 27 3 33 11 22
3036 13 26 1 14 28 7 35 5 15 30 10 20 4 16 32 8 24 6 12 36 18 9 27 3 33 11 22 2 34 17
3139? 22 11 33 3 27 9 18 36 12 6 24 8 32 16 4 20 10 30 15 5 35 7 28 14 1 17 34 2 26 13 39
3240? 22 11 33 3 27 9 18 36 12 24 6 30 15 5 35 7 14 28 4 32 16 8 40 20 10 1 17 34 2 26 13 39
33  
34  
35  
36  
3745 26 13 39 3 33 11 22 44 4 28 14 42 21 7 35 5 40 20 10 30 15 45 9 18 36 12 6 24 8 32 16 1 17 34 2 38 19
3848 33 11 22 44 4 28 14 42 21 7 35 5 45 15 30 10 20 40 8 32 16 48 24 12 36 6 18 9 27 3 39 13 26 1 19 38 2 34
3948 33 11 22 44 4 28 14 42 21 7 35 5 45 15 30 10 20 40 8 32 16 48 24 12 36 6 18 9 27 3 39 13 26 1 19 38 2 34 17
4050 33 11 22 44 4 28 14 42 21 7 35 5 25 50 10 20 40 8 32 16 48 24 12 36 18 6 30 15 45 9 27 3 39 13 26 1 19 38 2 34
4150 33 11 22 44 4 28 14 42 21 7 35 5 25 50 10 20 40 8 32 16 48 24 12 36 18 6 30 15 45 9 27 3 39 13 26 1 19 38 2 34 17

Brendan Owen and Mike Keith also generalized divisor chains to divisor loops (same as chains except the first and last numbers also have to divide each other). The number 1 is always going to be used in such a loop, since we can replace any number with a 1 and still have a divisor loop. Therefore, finding divisor loops is the same as finding divisor chains starting with the number 1. Owen did n≤28 and Keith did n≤20. Let So(n) be the smallest number in a divisor loop of length n. Here are their results:

Smallest Divisor Loops of Length n

n So(n) Example
11 1
22 1 2
34 1 4 2
46 1 6 2 4
56 1 4 2 6 3
68 1 8 4 2 6 3
79 1 9 3 6 2 8 4
812 1 12 4 8 2 6 3 9
912 1 10 2 8 4 12 6 3 9
1012 1 9 3 6 12 4 8 2 10 5
1115 1 15 5 10 2 8 4 12 6 3 9
1215 1 10 5 15 3 6 12 4 8 2 14 7
1316 1 16 8 4 12 6 3 15 5 10 2 14 7
1418 1 16 8 4 12 6 18 9 3 15 5 10 2 14
1518 1 16 8 4 12 6 18 9 3 15 5 10 2 14 7
1620 1 20 10 5 15 3 9 18 6 12 4 16 8 2 14 7
1721 1 21 7 14 2 20 10 5 15 3 9 18 6 12 4 16 8
1824 1 24 12 6 18 9 3 21 7 14 2 16 8 4 20 10 5 15
1924 1 22 2 14 7 21 3 15 5 10 20 4 16 8 24 12 6 18 9
2024 1 15 5 10 20 4 16 8 24 12 6 18 9 3 21 7 14 2 22 11
2127 1 11 22 2 14 7 21 3 15 5 10 20 4 16 8 24 12 6 18 9 27
2228 1 11 22 2 10 20 5 15 3 21 7 14 28 4 16 8 24 12 6 18 9 27
2330 1 5 15 30 10 20 4 16 8 24 12 6 18 9 27 3 21 7 14 28 2 22 11
2430 1 11 22 2 14 28 7 21 3 27 9 18 6 12 24 8 16 4 20 10 30 15 5 25
2532 1 11 22 2 14 28 7 21 3 27 9 18 6 12 24 8 16 32 4 20 10 30 15 5 25
2633 1 21 7 14 28 2 22 11 33 3 27 9 18 6 12 24 8 16 32 4 20 10 30 15 5 25
2735 1 13 26 2 14 28 7 35 5 15 30 10 20 4 16 32 8 24 12 6 18 9 27 3 33 11 22
2836 1 13 26 2 14 28 7 35 5 15 30 10 20 4 16 32 8 24 6 12 36 18 9 27 3 33 11 22

The sequence of values of So(n): 1, 2, 4, 6, 6, 8, 9, 12, 12, 12, 15, 15, 16, 18, 18, 20, 21, 24, 24, 24, 27, 28, 30, 30, 32, 33, 35, 36 . . . is now sequence A035280 of the Encyclopedia of Integer Sequences.

Mike Keith also considered the same problem using rectangles. Here every two numbers adjacent horizontally or vertically need to divide one another. Here are his results:

Smallest m by n Divisor Rectangles

m \ n 1 2 3 4 5 6
1
1
12
312
3124
63124
42631 5
2
1
2
16
42
624
318
1628
93124
4123155
826110
41263155
162189110
3
3
1
2
36
12
84
2105
8115
4123
212420
186110
93155
1155204
27330216
9186248
 
4
3
1
2
4
91
36
122
48
9182
3612
1514
51020
432816
202241
1030618
51539
4205357
401030121
826183
241236927
 

Pascal Zimmer found a divisor chain of length 77 using numbers no larger than 100:

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


If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 5/26/03.