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?

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:

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.

• L(n) ≥ log₂ n + log₃ 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 = a₁1, a₂, . . ., a_L(k), and B = b₁, b₂, ..., b_L(j) are two optimal chains for k and j, then j*A, 1, k*B is a chain for n.

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  

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)².

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

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 S_o(n) be the smallest number in a divisor loop of length n. Here are their results:

The sequence of values of S_o(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:

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

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.