Let’s say that two positive integers m, n are compatible if the difference of their reciprocal is the reciprocal of an integer: that is, mn/(m-n) is an integer. For example, 2 is compatible with 1, 3, 4, and 6 but not with 5. Compatibility is a symmetric relation, which we’ll denote even though it’s not an equivalence. Here is a chart of this relation, with red dots indicating compatibility.
A few natural questions arise, for any given :
- What is the greatest number compatible with ?
- What is the smallest number compatible with ?
- How many numbers are compatible with ?
Before answering them, let’s observe that if and only if is a product of two divisors of . Indeed, for to be an integer, we must be able to write as the product of a divisor of and a divisor of . But a common divisor of and is also a divisor of .
Of course, “a product of two divisors of ” is the same as “a divisor of “. But it’s sometimes easier to think in terms of the former.
Question 1 is now easy to answer: the greatest number compatible with is .
But there is no such an easy answer to Questions 2 and 3, because of the possibility of overshooting into negative when subtracting a divisor of from . The answer to Question 2 is where is the greatest divisor of than is less than . This is the OEIS sequence A063428, pictured below.
The lines are numbers with few divisors: for a prime p, the smallest compatible number is p-1, while for 2p it is p, etc.
The answer to Question 3 is: the number of distinct divisors of , plus the number of such divisors that are less than . This is the OEIS sequence A146564.
Since consecutive integers are compatible, every number is a part of a compatible chain . How to build a short chain like this?
Strategy A: starting with , take the smallest integer compatible with the previous one. This is sure to reach 1. But in general, this greedy algorithm is not optimal. For n=22 it yields 22, 11, 10, 5, 4, 2, 1 but there is a shorter chain: 22, 18, 6, 2, 1.
Strategy B: starting with , write the greatest integer compatible with the previous one (which is by the above). This initially results in the OEIS sequence A007018: 1, 2, 6, 42, 1806, … which is notable, among other things, for giving a constructive proof of the infinitude of primes, even with a (very weak) lower density bound. Eventually we have to stop adding to every time; so instead add the greatest divisor of such that the sum does not exceed . For 22, this yields the optimal chain 1, 2, 6, 18, 22 stated above. But for 20 strategy B yields 1, 2, 6, 18, 20 while the shortest chain is 1, 2, 4, 20. Being greedy is not optimal, in either up or down direction.
Strategy C is not optimal either, but it is explicit and provides a simple upper bound on the length of a shortest chain. It uses the expansion of n in the factorial number system which is the sum of factorials k! with coefficients less than k. For example , so its factorial representation is 2301.
If n is written as abcd in the factorial system, then the following is a compatible chain leading to n (possibly with repetitions), as is easy to check:
1, 10, 100, 1000, 1000, a000, ab00, abc0, abcd
In the example with 67, this chain is
1, 10, 100, 1000, 2000, 2300, 2300, 2301
in factorial notation, which converts to decimals as
1, 2, 6, 24, 48, 66, 66, 67
The repeated 66 (due to 0 in 2301) should be removed.
Thus, for an even number s, there is a chain of length at most s leading to any integer that is less than (s/2+1)!.
As a consequence, the smallest possible length of chain leading to n is . Is this the best possible O-estimate?
All of the strategies described above produce monotone chains, but the shortest chain is generally not monotone. For example, 17 can be reached by the non-monotone chain 1, 2, 6, 18, 17 of length 5 but any monotone chain will have length at least 6.
The smallest-chain-length sequence is 1, 2, 3, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 5, 4, 5, 5, 4, 5, 4, 5, 5, 5, 4, 5, … which is not in OEIS. Here is its plot:
The sequence 1, 2, 3, 5, 11, 29, 67, 283, 2467,… lists the smallest numbers that require a chain of given length — for example, 11 is the first number that requires a chain of length 5, etc. Not in OEIS; the rate of growth is unclear.