# 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?

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:

• L(p) = L(p-1) for primes p>3.
• If there are at least 2 primes between n/2 and n, then L(n) ≤ n - π(n) + π(n/2) + 1.
• If there are at least 2 primes between n/3 and n/2, then L(n) ≤ n - π(n) - π(n/2) + 2 π(n/3) + 3
• If there are at least 3 primes between n/4 and n/3, then L(n) ≤ n - π(n) - π(n/2) - π(n/3) + 3 π(n/4) + 8.
His upper bounds include:

• L(n) ≥ log2 n + log3 n + 1, since there is always the chain . . ., 8, 4, 2, 1, 3, 9, 27, . . . .
• L(n) ≥ max{ L(k) + L(j) + 1 } over all (k,j) with (k,j) = 1 & kj = n, since if A = a11, a2, . . ., aL(k), and B = b1, b2, ..., bL(j) are two optimal chains for k and j, then j*A, 1, k*B is a chain for n.
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
 1 2
 3 1 2
 3 1 2 4
 6 3 1 2 4
 4 2 6 3 1 5
2
 1 2
 1 6 4 2
 6 2 4 3 1 8
 1 6 2 8 9 3 12 4
 4 12 3 15 5 8 2 6 1 10
 4 12 6 3 15 5 16 2 18 9 1 10
3
 3 1 2
 3 6 1 2 8 4
 2 10 5 8 1 15 4 12 3
 2 12 4 20 18 6 1 10 9 3 15 5
 1 15 5 20 4 27 3 30 2 16 9 18 6 24 8
 5 15 3 12 24 8 10 30 6 36 4 16 20 2 18 9 1 32
4
 3 1 2 4
 9 1 3 6 12 2 4 8
 9 18 2 3 6 12 15 1 4 5 10 20
 4 32 8 16 20 2 24 1 10 30 6 18 5 15 3 9
 4 20 5 35 7 40 10 30 1 21 8 2 6 18 3 24 12 36 9 27
 7 42 6 18 9 45 28 1 12 36 3 15 4 48 24 2 30 5 32 16 8 40 10 20
5
 6 3 1 2 4
 8 4 2 12 6 3 1 15 10 5
 9 27 1 18 3 15 6 30 5 24 2 20 8 16 4
 24 8 40 4 12 2 10 20 36 6 30 5 9 18 1 35 27 3 21 7
 5 10 40 8 32 15 30 1 48 16 45 3 12 24 4 9 18 36 2 28 27 54 6 42 7
 7 14 70 10 30 15 21 42 2 20 5 45 63 3 60 4 40 1 9 36 12 24 8 32 54 18 6 48 16 64

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
 1 2
 1 4 2
 1 6 4 2
2
 1 2
 1 6 4 2
 1 2 4 3 6 12
 1 2 6 3 4 8 24 12
3
 3 1 2
 3 6 1 2 8 4
 2 4 8 6 12 1 18 3 9
 3 12 4 24 6 1 20 2 30 15 5 10
4
 3 1 2 4
 1 4 2 8 6 24 3 12
 1 9 27 6 18 3 12 2 24 4 16 8
 1 5 45 9 6 30 3 36 24 2 48 12 8 32 16 4

## Smallest m×n Divisor Tori

m \ n 1 2 3 4
1
 1
 1 2
 1 4 2
 1 6 4 2
2
 1 2
 1 6 4 2
 1 2 4 3 6 12
 1 2 6 3 4 8 24 12
3
 1 4 2
 1 3 2 6 4 12
 1 2 4 3 6 12 9 18 36
 1 3 12 4 5 15 60 20 10 30 2 40
4
 1 6 4 2
 1 4 2 8 6 24 3 12
 1 5 10 3 15 30 12 60 20 4 20 40
 1 3 24 8 5 60 4 40 90 6 48 2 9 36 12 72

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.