Let $a_n=|nx-1|$, $n\in\mathbb{Z}^+$ and $x\in\mathbb{R}$. Find the least possible value of $\sum_{n=1}^{696}a_n$

Question

Let $a_n=|nx-1|$, $n\in\mathbb{Z}^+$ and $x\in\mathbb{R}$. Find the least possible value of $\displaystyle\sum_{n=1}^{696}a_n$

My attempt: \begin{align*} S_{696}&=\sum_{n=1}^{696}|nx-1|\\ &=|x|\sum_{n=1}^{696}|n-\frac{1}{x}|\\ \end{align*}

Answer 1

Denote $a_n(x) = \vert nx -1 \vert$ and $$f_m(x)= \sum_{n=1}^m a_n(x)$$

You're looking for the minimum of $f_{696}$.

The minimum of $f_m$ is attained for one of the values:

$$1, 1/2, 1/3, \dots, 1/m.$$

And for $1 \le k \le m$ you have

$$f_m\left(\frac{1}{k}\right) = \frac{2k^2 - 2(m+1)k + m(m+1)}{2k}.$$

Looking at the minimum of the map

$$g : x \mapsto \frac{2x^2 - 2(m+1)x + m(m+1)}{2x},$$ you find (by differentiation) that the minimum is achieved at

$$x_m = \sqrt{\frac{m(m+1)}{2}}.$$

Therefore the minimum of $f_m$ is attained at $$\lfloor 1/x_m \rfloor \text{ or } \lceil 1/x_m \rceil.$$ You just have to compute $f_m$ at those two values to get the minimum. For example the minimum of $f_{696}$ is attained at $1/492$ and its value is 288.

A python program to illustrate the question.

from math import sqrt
def abs_nx(n, x):
    return abs(n * x - 1.0)
def f(m, x):
    y = 0.0
    for n in range(1, m + 1):
        y += abs_nx(n, x)
    return y
def g(m, k):
    return (k * (k - 1) + (m - k) * (m - k + 1)) / (2.0 * k)
def min_f(m):
    xm = sqrt(m * (m + 1) / 2.0)
    k, kp1 = round(xm), round(xm) + 1
    fm_k, fm_kp1 = f(m, 1.0 / k), f(m, 1.0 / kp1)
    km = k if fm_k < fm_kp1 else kp1
    return km
def main():
    m = 10
    for k in range(1, m + 1):
        print(f"f(10, {1.0 / k: .2f}): {f(m, 1.0 / k): .2f}, g(10, {k: 2d}): {g(m, k): .2f}")
    km = min_f(m)
    print(f"minimum: {f(m, 1.0 / km): .2f} attained at: 1/{km: 2d}")
k696 = min_f(696)
print(f&quot;minimum 696: {f(696, 1.0 / k696): .2f} attained at: 1/{k696: 2d}&quot;)



main()