Relating integers by differences of reciprocals

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 {m\sim n} even though it’s not an equivalence. Here is a chart of this relation, with red dots indicating compatibility.

Capture
Compatibility of integers up to 200

Extremes

A few natural questions arise, for any given {n}:

  1. What is the greatest number compatible with {n}?
  2. What is the smallest number compatible with {n}?
  3. How many numbers are compatible with {n}?

Before answering them, let’s observe that {m\sim n} if and only if {|m-n|} is a product of two divisors of {n}. Indeed, for {mn/(m-n)} to be an integer, we must be able to write {|n-m|} as the product of a divisor of {m} and a divisor of {n}. But a common divisor of {m} and {m-n} is also a divisor of {n}.

Of course, “a product of two divisors of {n}” is the same as “a divisor of {n^2}“. But it’s sometimes easier to think in terms of the former.

Question 1 is now easy to answer: the greatest number compatible with {n} is {n+n^2 = n(n+1)}.

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 {n^2} from {n}. The answer to Question 2 is {n-d} where {d} is the greatest divisor of {n^2} than is less than {n}. This is the OEIS sequence A063428, pictured below.

min_jump10000
The smallest compatible number for n

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 {n^2}, plus the number of such divisors that are less than {n}. This is the OEIS sequence A146564.

Chains

Since consecutive integers are compatible, every number {n} is a part of a compatible chain {1\sim \cdots\sim n}. How to build a short chain like this?

Strategy A: starting with {n}, 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 {1}, write the greatest integer compatible with the previous one (which is {k(k+1)} 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 {k^2} to {k} every time; so instead add the greatest divisor of {k^2} such that the sum does not exceed {n}. 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 {67 = 2\cdot 4! + 3\cdot 3! + 0\cdot 2! + 1\cdot 1!}, 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 {O(\log n/\log \log n)}. 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:

stepde
Smallest chain length for integers from 1 to 1000

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.

Together in hyperharmony

Harmonic numbers are the partial sums of the harmonic series:

\displaystyle  H_n=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{n}

As every freshman knows (?), they grow without bound: {H_n\rightarrow\infty} as {n\rightarrow\infty}. It is also well known that the sequence {H_n-\log n} has a finite limit, called the Euler-Mascheroni constant {\gamma\approx 0.577\dots}. On top of that, Bernoulli numbers show up in the asymptotic expansion for {H_n},

\displaystyle  H_n=\log n+\gamma -\sum_{k=1}^\infty \frac{B_k}{k n^{k}} =\log n+\gamma +\frac{1}{2n}-\frac{1}{12n^2}-\dots

where I take the position that {B_1=-1/2}. The larger {n} gets, the fewer terms are needed for given precision.

And apparently, {\log H_n \, e^{H_n}} have something to do with the Riemann hypothesis.

In their Book of Numbers, J. H. Conway and R. K. Guy briefly entertained the idea of defining “hyperharmonic numbers” by repeating the process of partial summation.

\displaystyle   H_n^{(2)}  = H_1+H_2+\dots + H_n \\ \\ H_n^{(3)}   = H_1^{(2)}+H_2^{(2)}+\dots + H_n^{(2)}

and so on. It is natural to guess that this will produce sequences of increasing complexity. But Conway and Guy immediately destroy this illusion with the formula

\displaystyle H_n^{(r)} = \binom{n+r-1}{r-1}(H_{n+r-1}-H_{r-1})

The base case {r=2} is a neat arithmetical trick:

\displaystyle   H_1+\dots+H_n  = \frac{n}{1}+\frac{n-1}{2}+\frac{n-2}{3}+\dots +\frac{1}{n} \\ \\   = \frac{n+1}{1}-1 +\frac{n+1}{2}-1 + \frac{n+1}{3} -1 + \dots +\frac{n+1}{n} -1 \\ \\  = (n+1)H_n-n = (n+1)H_{n+1} -(n+1) = \binom{n+1}{1} (H_{n+1} -1)

For {n\ge 2}, the harmonic numbers {H_n} are never integers, although {H_{30}=3.994987\dots} makes a solid effort. The reason is simple: the highest power of {2} not exceeding {n} appears in some {1/2^k} and in no other term. Nothing to cancel it with.

The hyperharmonic numbers are conjectured to be non-integer as well, and this has been verified for many values of {r} but not in full generality.

Playing with numbers: 1/998001 and others

A post in response to Colin’s “Patterns in numbers”:

1/998001 = 0.000 001 002 003 004 005 006 007…

goes through all integers 000 through 999, skipping only 998. Maple confirms this:

1/998001

This fraction made rounds on the internet a while ago.

I begin with two general claims:

  • Integer numbers are more complicated than polynomials
  • Decimal fractions are more complicated than power series

To illustrate the first one: multiplying 748 by 367 takes more effort than multiplying the corresponding polynomials,

(7x^2+4x+8)(3x^2+6x+7) = 21x^4+54x^3+97x^2+76x+56

The reason is that there’s no way for the product of 4 x and 3x^2 to “roll over” into x^4. It’s going to stay in the x^3 group. Mathematically speaking, polynomials form a graded ring and integers don’t. At the same time, one can recover the integers from polynomials by setting x=10 in 21x^4+54x^3+97x^2+76x+56. The result is 274516.

Moving on to the second claim, consider the power series

\displaystyle (*) \qquad \frac{1}{1-t}=1+t+t^2+t^3+\dots = \sum_{n=0}^{\infty} t^n

I prefer to use t instead of x here, because we often want to replace t with an expression in x. For example, setting t=2x gives us

\displaystyle \frac{1}{1-2x}=1+2x+4x^2+8x^3+\dots = \sum_{n=0}^{\infty} 2^n x^n

which is nothing surprising. But if we now set x=0.001 (and, for neatness, divide both sides by 1000), the result is

\displaystyle \frac{1}{998}=0.001\ 002\ 004\ 008\ 016\ 032 \dots

which looks like a magical fraction producing powers of 2. But in reality, setting x=0.001 did nothing but mess things up. Now we have a complicated decimal number, in which powers of 2 break down starting with “513” because of the extra digits rolled over from 1024. In contrast, the neat power series keeps generating powers of 2 forever.

By the way, \displaystyle \frac{1}{1-2x} is the generating function for the numbers 1,2,4,8,16…, i.e., the powers of 2.

So, if you want to cook up a ‘magical’ fraction, all you need to do is find the generating function for the numbers you want, and set the variable to be some negative power of 10. E.g., the choice x=0.001 avoids digits rolling over until the desired numbers reach 1000. But we could take x=10^{-6} and get many more numbers at the cost of a more complicated fraction.

For example, how would one come up with 1/998001? We need a generating function for 1,2,3,4,…, that is, we need a formula for the power series \sum nt^n. No big deal: just take the derivative of (*):

\displaystyle \frac{1}{(1-t)^2}=\sum_{n=0}^{\infty} nt^{n-1}

and multiply both sides by t to restore the exponent:

\displaystyle (**) \qquad \frac{t}{(1-t)^2}=\sum_{n=0}^{\infty} nt^{n}

Now set t=0.001, which is easiest if you expand the denominator as 1-2t+t^2 and multiply both the numerator and denominator by 1000000. The result is

\displaystyle \frac{1000}{998001} = \sum_{n=0}^{\infty} n\,0.001^{n} = 0.001002003\dots

Dropping 1000 in the numerator is a matter of taste (cf. xkcd 163).

Let’s cook up something else. For example, again take the derivative in (**) and multiply by t:

\displaystyle \frac{t(1+t)}{(1-t)^3}=\sum_{n=0}^{\infty} n^2t^{n}

Now set t=0.001 to get

\displaystyle \frac{1001}{997002999} = 0.000\ 001\ 004\ 009\ 016\ 025\ 036\ 049\dots

Admittedly, this fraction is less likely to propagate around the web than 1/998001.

For the last example, take the Fibonacci numbers 1,1,2,3,5,8,13,… The recurrence relation F_{n+2}=F_n+F_{n+1} can be used to find the generating function, \displaystyle \frac{1}{1-t-t^2} = \sum F_n t^n. Setting t=0.001 yields

\displaystyle \frac{1}{998999} = 0.000\ 001\ 002\ 003\ 005\ 008\ 013\ 021\ 034\ 055\dots