Closest consecutive reciprocal sum to an integer

József Kürschák proved in 1908 that the perform

is rarely an integer for 0 < m < n. Specifically, the harmonic numbers

are by no means integers for n > 1.

The perform f(m, n) can get arbitrarily near any integer worth by taking m and n massive sufficient, however it may by no means precisely equal an integer.

For this put up, I’d like to take a look at how shut  f(m, n) involves an integer worth when 0 < m < n ≤ N for some massive N, say N = 100,000.

Computation technique

Essentially the most naive technique to strategy this is able to be to compute f(m, n) for all m and n and hold monitor of which values had been closest to integers. This is able to be wasteful since it could recompute the identical phrases time and again. As a substitute, we may reap the benefits of the truth that

As a substitute of working with f(m, n), will probably be handy to work with simply its fractional half

as a result of it received’t harm to throw away the integer elements as we go. The values of m and n minimizing g(m, n) would be the values for which f(m, n) comes closest to an integer from above. The values of m and n maximizing g(m, n) would be the values for which f(m, n) comes closest to an integer from under.

We may calculate a matrix with all values of g(m, n), however this is able to take O(N²) reminiscence. As a substitute, for every n we’ll calculate g(m, n), save the utmost and minimal values, then overwrite that reminiscence with g(m, n + 1). This strategy will solely take O(N) reminiscence.

Floating level error

After we compute f(m, n) for big values of n, can we depend on floating level arithmetic?

If N = 100,000, f(m, n) < 16 = 2⁴. A floating level fraction has 53 bits, so we’d anticipate every addition to be appropriate to inside an error of two⁻⁴⁹ and so we’d anticipate our complete error to be lower than 2⁻⁴⁹ N.

Python code

The next code computes the values of g(m, n) closest to 0 and 1.

import numpy as np

N = 100_000
f_m = np.zeros(N+1) # working reminiscence

# greatest values of m for every n
min_fm = np.zeros(N+1)
max_fm = np.zeros(N+1)

n = 2
f_m[1] = 1.5

for n in vary(3, N+1):
    f_m[n-1] = 1/(n-1)
    f_m[1:n] += 1/n
    f_m[1:n] -= np.ground(f_m[1:n])
    min_fm[n] = np.min(f_m[1:n])
    max_fm[n] = np.max(f_m[1:n])    

print(min(min_fm[3:]))
print(max(max_fm))

This studies a minimal worth of 5.2841953035454026e-11 and a most worth of 0.9999999996613634. The minimal worth is nearer to 0 than our (pessimistic) error estimate, although the utmost worth is farther from 1 than our error estimate.

Modifying the code a bit exhibits that the minimal happens at (27134, 73756), and this the enter to g that’s inside our error estimate. So we could be assured that it’s the minimal, although we will’t be assured of its worth. So subsequent we flip to Mathematica to seek out the precise worth of g(27133, 73756) as a rational quantity, a fraction with 32024 digits within the numerator and denominator, and convert it to a floating level quantity. The outcome agrees with our estimate in magnitude and to 4 vital figures.

So in abstract

with an error on the order of 10⁻¹¹, and that is the closest worth of f(m, n) to an integer, for 0 < m < n ≤ 100,000.

Associated posts