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. Alex Rower gave the results for n=33 and n=34.

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
3342 22 11 33 3 27 9 18 36 12 24 6 30 15 5 35 7 42 14 28 4 32 16 8 40 20 10 1 17 34 2 26 13 39
3444 44 22 11 33 3 27 9 18 36 12 24 6 30 15 5 35 7 42 14 28 4 32 16 8 40 20 10 1 17 34 2 26 13 39
3545? 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
3645? 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
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. In 2019, Alex Rower did 29≤n≤33. 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
2939 1 39 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
3040 1 39 13 26 2 14 28 7 35 5 15 30 10 40 20 4 16 32 8 24 6 12 36 18 9 27 3 33 11 22
3142 1 39 13 26 2 14 42 28 7 35 5 15 30 10 40 20 4 16 32 8 24 6 12 36 18 9 27 3 33 11 22
3244 1 39 13 26 2 14 42 28 7 35 5 15 30 10 40 20 4 16 32 8 24 6 12 36 18 9 27 3 33 11 22 44
3345 1 39 13 26 2 14 42 28 7 35 5 45 15 30 10 40 20 4 16 32 8 24 6 12 36 18 9 27 3 33 11 22 44

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. Below are his results. The 3×6, 4×6, 5×5, and 5×6 cases are due to Alex Rower.

Smallest m×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
515312248
1030636416
202189132
4
3
1
2
4
91
36
122
48
9182
3612
1514
51020
432816
202241
1030618
51539
4205357
401030121
826183
241236927
742618945
2811236315
448242305
32168401020
5
6
3
1
2
4
84
212
63
115
105
9271
18315
6305
24220
8164
248404
1221020
366305
918135
273217
51040832
153014816
45312244
91836228
27546427
71470103015
2142220545
633604401
9361224832
54186481664

Alex Rower also investigated Divisor Cylinders and Divisor Tori, and his results are below.

Smallest m×n Divisor Cylinders

m \ n 1 2 3 4
1
1
12
142
1642
2
1
2
16
42
124
3612
1263
482412
3
3
1
2
36
12
84
248
6121
1839
312424
61202
3015510
4
3
1
2
4
14
28
624
312
1927
6183
12224
4168
15459
630336
2424812
832164

Smallest m×n Divisor Tori

m \ n 1 2 3 4
1
1
12
142
1642
2
1
2
16
42
124
3612
1263
482412
3
1
4
2
13
26
412
124
3612
91836
13124
5156020
1030240
4
1
6
4
2
14
28
624
312
1510
31530
126020
42040
13248
560440
906482
9361272

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 4/23/19.