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 (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.
In 2021, he improved this lower bound considerably. If p1 through pk are the primes less than √n, then 1, p1, p1p2, p2, p2p3, p3,... pk is a divisor chain of n of length 2k. Thus L(n)≥2π(√n)≈2√(n/log n).
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. Michael Yee improved n=34, n=35, and n=36.
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 |
1 | 1 |
1 |
2 | 2 |
1 2 |
3 | 3 |
3 1 2 |
4 | 4 |
3 1 2 4 |
5 | 6 |
1 3 6 2 4 |
6 | 6 |
3 6 2 4 1 5 |
7 | 8 |
3 6 2 4 8 1 5 |
8 | 9 |
4 8 2 6 3 9 1 5 |
9 | 10 |
4 8 1 5 10 2 6 3 9 |
10 | 12 |
1 5 10 2 8 4 12 6 3 9 |
11 | 12 |
5 10 2 8 4 12 6 3 9 1 7 |
12 | 14 |
5 10 1 7 14 2 8 4 12 6 3 9 |
13 | 15 |
6 12 4 8 1 7 14 2 10 5 15 3 9 |
14 | 16 |
6 12 4 8 16 1 7 14 2 10 5 15 3 9 |
15 | 18 |
1 7 14 2 8 16 4 12 6 18 9 3 15 5 10 |
16 | 18 |
7 14 2 8 16 4 12 6 18 9 3 15 5 10 1 11 |
17 | 20 |
20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 1 11 |
18 | 21 |
20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 21 1 11 |
19 | 22 |
20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 21 1 11 22 |
20 | 24 |
20 10 5 15 3 9 18 6 12 24 4 16 8 2 14 7 21 1 11 22 |
21 | 24 |
15 5 10 20 4 16 8 24 12 6 18 9 3 21 7 14 2 22 11 1 13 |
22 | 26 |
15 5 10 20 4 16 8 24 12 6 18 9 3 21 7 14 2 22 11 1 13 26 |
23 | 27 |
15 5 10 20 4 16 8 24 12 6 18 9 27 3 21 7 14 2 22 11 1 13 26 |
24 | 28 |
15 5 10 20 4 16 8 24 12 6 18 9 27 3 21 7 28 14 2 22 11 1 13 26 |
25 | 30 |
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 |
26 | 30 |
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 |
27 | 32 |
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 |
28 | 33 |
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 |
29 | 35 |
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 |
30 | 36 |
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 |
31 | 39 |
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 |
32 | 40? |
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 | 42 |
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 |
34 | 42 |
19 38 1 16 32 8 40 20 10 30 15 5 35 7 21 42 14 28 4 36 12 24 6 18 9 27 3 39 13 26 2 22 11 33 |
35 | 44 |
19 38 1 33 11 44 22 2 40 20 10 30 15 5 35 7 21 42 14 28 4 32 16 8 24 12 36 6 18 9 27 3 39 13 26 |
36 | 44 |
19 38 1 17 34 2 26 13 39 3 33 11 22 44 4 32 16 8 40 20 10 30 15 5 35 7 28 14 42 6 24 12 36 18 9 27 |
37 | 45 |
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 |
38 | 48 |
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 |
39 | 48 |
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 |
40 | 50 |
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 |
41 | 50 |
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. Michael Yee improved n=32 and n=33 and sent 34≤n≤36. 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 |
1 | 1 |
1 |
2 | 2 |
1 2 |
3 | 4 |
1 4 2 |
4 | 6 |
1 6 2 4 |
5 | 6 |
1 4 2 6 3 |
6 | 8 |
1 8 4 2 6 3 |
7 | 9 |
1 9 3 6 2 8 4 |
8 | 12 |
1 12 4 8 2 6 3 9 |
9 | 12 |
1 10 2 8 4 12 6 3 9 |
10 | 12 |
1 9 3 6 12 4 8 2 10 5 |
11 | 15 |
1 15 5 10 2 8 4 12 6 3 9 |
12 | 15 |
1 10 5 15 3 6 12 4 8 2 14 7 |
13 | 16 |
1 16 8 4 12 6 3 15 5 10 2 14 7 |
14 | 18 |
1 16 8 4 12 6 18 9 3 15 5 10 2 14 |
15 | 18 |
1 16 8 4 12 6 18 9 3 15 5 10 2 14 7 |
16 | 20 |
1 20 10 5 15 3 9 18 6 12 4 16 8 2 14 7 |
17 | 21 |
1 21 7 14 2 20 10 5 15 3 9 18 6 12 4 16 8 |
18 | 24 |
1 24 12 6 18 9 3 21 7 14 2 16 8 4 20 10 5 15 |
19 | 24 |
1 22 2 14 7 21 3 15 5 10 20 4 16 8 24 12 6 18 9 |
20 | 24 |
1 15 5 10 20 4 16 8 24 12 6 18 9 3 21 7 14 2 22 11
|
21 | 27 |
1 11 22 2 14 7 21 3 15 5 10 20 4 16 8 24 12 6 18 9 27 |
22 | 28 |
1 11 22 2 10 20 5 15 3 21 7 14 28 4 16 8 24 12 6 18 9 27 |
23 | 30 |
1 5 15 30 10 20 4 16 8 24 12 6 18 9 27 3 21 7 14 28 2 22 11 |
24 | 30 |
1 11 22 2 14 28 7 21 3 27 9 18 6 12 24 8 16 4 20 10 30 15 5 25 |
25 | 32 |
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 |
26 | 33 |
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 |
27 | 35 |
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 |
28 | 36 |
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 |
29 | 39 |
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 |
30 | 40 |
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 |
31 | 42 |
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 |
32 | 42 |
1 16 32 8 40 20 10 30 15 5 35 7 21 42 14 28 4 36 12 24 6 18 9 27 3 39 13 26 2 22 11 33 |
33 | 44 |
1 33 11 44 22 2 40 20 10 30 15 5 35 7 21 42 14 28 4 32 16 8 24 12 36 6 18 9 27 3 39 13 26 |
34 | 44 |
1 17 34 2 26 13 39 3 33 11 22 44 4 32 16 8 40 20 10 30 15 5 35 7 28 14 42 6 24 12 36 18 9 27 |
35 | 45 |
1 28 14 42 21 7 35 5 40 20 10 30 15 45 9 36 18 6 12 24 8 32 16 4 44 22 11 33 3 39 13 26 2 38 19 |
36 | 48 |
1 24 48 16 32 8 40 20 10 30 6 12 36 18 9 45 15 5 35 7 21 42 14 28 4 44 22 11 33 3 39 13 26 2 46 23 |
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
| |
|
|
|
|
|
2
| |
|
|
|
|
|
3
| |
|
|
|
|
5 | 15 | 3 | 12 | 24 | 8 |
10 | 30 | 6 | 36 | 4 | 16 |
20 | 2 | 18 | 9 | 1 | 32 | |
---|
4
| |
|
|
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
| |
|
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
| |
|
|
|
---|
2
| |
|
|
|
---|
3
| |
|
|
|
---|
4
| |
|
|
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
| |
|
|
|
---|
2
| |
|
|
|
---|
3
| |
|
|
|
---|
4
| |
|
|
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.