Formula for progression with increasing ratios

Question

Looking for a single formula solution to the following problem, to replace an algorithmic for loop approach for a similar problem in a software.

Imagine a really long metal bar. We are making a finite max number of M train cars using this bar.

1 unit length of the bar is needed to make the 1^st car. Each successive car requires an increasing amount of the metal bar, compared to previous one. The n^th car requires following unit lengths of the bar $$ \frac {M} {M - (n - 1)} $$

So for the first n (<= M) number of cars, the sum total of metal bar units required is $$ b = 1 + \frac {M} {M - 1} + \frac {M} {M - 2} + \ldots + \frac {M} {M - (n - 1)} $$

The question is, for given positive values of M and (real) b how can we find the possible number of n including the fraction.

Hope I have explained the question well. Please feel free to edit the question and title if required.

Answer 1

Suprisingly (at least to me), this problem looks simple and it is not.

Using harmonic numbers, just as @SenZen commented, the equation is $$b=M \left(H_{M+1}-H_{M+1-n}\right)$$ (corrected after @Yves Daoust' comment).

To have an estimate of $n$, what I should try is to compare with the integral and write $$b\sim\int_0^{n-1} \frac M {M-k} dk=M\log \left(\frac{M}{M-n+1}\right)$$ which would give $$n \sim 1+M \left(1-e^{-\frac{b}{M}}\right)$$

Trying for $M=1000$ and $b=150$, this would give $n=140.292$ while the summation up to $n=140$ would give $b=150.742$ and the summation up to $n=139$ would give $b=149.580$.

Changing $b=350$, $n=296.312$ while the solution is $n=296$ for which $b=350.767$.

This has to be tried. If it works, the region do explore for integer values of $n$ could be significantly reduced.

Edit

Beside the integral, we could make other estimates : the second one is based on $$H_m - H_n \sim \log \left(\frac{m}{n}\right)$$ and the third one on $$H_m - H_n \sim \log \left(\frac{2m+1}{2n+1}\right)$$ derived from the inequality $$\frac{1}{24 (n+1)^2} < H_n -\log \left(n+\frac{1}{2}\right)-\gamma <\frac{1}{24 (n+1)^2}$$ derived by De Temple in $1991$.

So, we have three starting estimates $$n_1=M \left(1-e^{-\frac{b}{M}}\right)+1 \quad n_2=(M+1) \left(1-e^{-\frac{b}{M}}\right) \quad n_3= \left(M+\frac{3}{2}\right) \left(1-e^{-\frac{b}{M}}\right)$$

Checking for $M=50$ and a few $b$ as in your table, $$\left( \begin{array}{ccccc} b & n_1 & n_2 & n_3 & \text{exact}\\ 1 & 1.99007 & 1.00987 & 1.01977 & 1.01980 \\ 2 & 2.96053 & 1.99974 & 2.01934 & 2.01941 \\ 3 & 3.91177 & 2.97001 & 2.99913 & 2.99922 \\ 4 & 4.84418 & 3.92107 & 3.95951 & 3.95964 \\ 5 & 5.75813 & 4.85329 & 4.90087 & 4.90104 \\ 6 & 6.65398 & 5.76706 & 5.82360 & 5.82379 \\ 7 & 7.53209 & 6.66273 & 6.72805 & 6.72828 \\ 8 & 8.39281 & 7.54067 & 7.61459 & 7.61485 \\ 9 & 9.23649 & 8.40122 & 8.48358 & 8.48388 \\ 10 & 10.0635 & 9.24473 & 9.33537 & 9.33569 \\ 11 & 10.8741 & 10.0715 & 10.1703 & 10.1706 \\ 12 & 11.6686 & 10.8820 & 10.9887 & 10.9891 \\ 13 & 12.4474 & 11.6764 & 11.7908 & 11.7913 \\ 14 & 13.2108 & 12.4550 & 12.5771 & 12.5776 \\ 15 & 13.9591 & 13.2183 & 13.3479 & 13.3484 \\ 16 & 14.6925 & 13.9664 & 14.1033 & 14.1039 \\ 17 & 15.4115 & 14.6997 & 14.8438 & 14.8444 \\ 18 & 16.1162 & 15.4185 & 15.5697 & 15.5703 \\ 19 & 16.8069 & 16.1231 & 16.2811 & 16.2818 \\ 20 & 17.4840 & 16.8137 & 16.9785 & 16.9792 \end{array} \right)$$

I think that is is clear that the best is, from very far away, $$\color{red}{n= \left(M+\frac{3}{2}\right) \left(1-e^{-\frac{b}{M}}\right)}$$

Update

More mathematical would be to write $$n=1+M-H^{(-1)}(x) \qquad \text{with} \qquad x=H_{M+1}-\frac{b}{M}$$

David W. Cantrell proposed by series reversion an extremely accurate solution for $H^{(-1)}(x)$ (have alook at sequences $A118050$ and $A118051$ in $OEIS$). Applied to the present case, it will write

$$n=1+M -\left(u-\frac 12 - \frac 1 {24\,u}+ \frac 3 {640\,u^3}- \frac {1525} {580608\,u^5}\right)+O\left(\frac{1}{u^7}\right)$$ where $u= e^{x-\gamma }$

$$1+M -\left(u-\frac 12 - \frac 1 {24\,u}+ \frac 3 {640\,u^3}- \frac {1525} {580608\,u^5}\right)$$

For $M=50$, the results (with, on purpose, a ridiculous number of figures).

$$\left( \begin{array}{ccc} b & \text{approximation} & \text{exact solution} \\ 1 & 1.0198006860101889035 & 1.0198006860101852029 \\ 2 & 2.0194086190999160598 & 2.0194086190999118032 \\ 3 & 2.9992236557634994756 & 2.9992236557634945796 \\ 4 & 3.9596377350723295228 & 3.9596377350723238912 \\ 5 & 4.9010350354556991454 & 4.9010350354556926677 \\ 6 & 5.8237921283772688384 & 5.8237921283772613876 \\ 7 & 6.7282781289686421452 & 6.7282781289686335751 \\ 8 & 7.6148548436803070019 & 7.6148548436802971443 \\ 9 & 8.4838769150090051558 & 8.4838769150089938173 \\ 10 & 9.3356919633594224112 & 9.3356919633594093694 \\ 11 & 10.170640726096946137 & 10.170640726096931136 \\ 12 & 10.989057193847112850 & 10.989057193847095596 \\ 13 & 11.791268744096267332 & 11.791268744096247486 \\ 14 & 12.577596272146875145 & 12.577596272146852317 \\ 15 & 13.348354319479872273 & 13.348354319479846016 \\ 16 & 14.103851199575398348 & 14.103851199575368148 \\ 17 & 14.844389121242243242 & 14.844389121242208505 \\ 18 & 15.570264309505340250 & 15.570264309505300296 \\ 19 & 16.281767124099662268 & 16.281767124099616312 \\ 20 & 16.979182175617919857 & 16.979182175617866999 \end{array} \right)$$

Notice that, truncating to the first term, this would give another estimate $$n_4=\left(M+\frac 32\right)-(M+1) \exp\left(\frac{1}{2(M+1)}-\frac{b}{M} \right)$$

Answer 2

Below is the code (in Swift language) to compare the results of the formula given in the accepted answer and the one computed using program.

import Darwin

let M: Double = 50
let e: Double =  Darwin.M_E

for math_b in stride(from: 0.0, through: 200.0, by: 1.0) {
    // Math
    let math_n = M * (1 - pow(e, -math_b / M))

    // Algorithm
    var algo_b = math_b
    var algo_n = 0.0

    while algo_b > 0 {
        let chunk_size = M / (M - algo_n)

        algo_n += (algo_b >= chunk_size) ? 1 : (algo_b / chunk_size)

        algo_b -= chunk_size
    }

    print("b =", math_b, "math n =", round(math_n * 100) / 100, "algo n =", round(algo_n * 100) / 100)
}

Results for the first few values of b, for M = 50 are,

    b = 0.0    math n = 0.0     algo n = 0.0
    b = 1.0    math n = 0.99    algo n = 1.0
    b = 2.0    math n = 1.96    algo n = 1.98
    b = 3.0    math n = 2.91    algo n = 2.94
    b = 4.0    math n = 3.84    algo n = 3.88
    b = 5.0    math n = 4.76    algo n = 4.8
    b = 6.0    math n = 5.65    algo n = 5.71
    b = 7.0    math n = 6.53    algo n = 6.59
    b = 8.0    math n = 7.39    algo n = 7.46
    b = 9.0    math n = 8.24    algo n = 8.32
    b = 10.0   math n = 9.06    algo n = 9.15
    b = 11.0   math n = 9.87    algo n = 9.97
    b = 12.0   math n = 10.67   algo n = 10.77
    b = 13.0   math n = 11.45   algo n = 11.56
    b = 14.0   math n = 12.21   algo n = 12.33
    b = 15.0   math n = 12.96   algo n = 13.09
    b = 16.0   math n = 13.69   algo n = 13.83
    b = 17.0   math n = 14.41   algo n = 14.55
    b = 18.0   math n = 15.12   algo n = 15.27
    b = 19.0   math n = 15.81   algo n = 15.97
    b = 20.0   math n = 16.48   algo n = 16.65

Also as M increases, the difference between both the results decreases.