0

I need to come up with a formula to calculate the coefficient from this formula

$$S = x + xn + xn^2 + \cdots + xn^{y-1} \tag{1}$$

Variables:

  • $S$ - total prize pool
  • $x$ - amount the last place receives
  • $y$ - number of players
  • $n$ - coefficient

How do I solve for $n$?

Thank you

Blue
  • 75,673
Yuri Vaskovski
  • 1
  • Read this: https://en.wikipedia.org/wiki/Geometric_series#Formula – Matti P. Jan 09 '19 at 13:45
  • The $n$ in your equation corresponds to $r$ in Wikipedia's notation. But I'm afraid there isn't an exact formula to calculate $r$. You'll have to resort to numerical methods for solving it. You can, for example, plot $S$ as a function of $n$ and then see what the approximate answer is. – Matti P. Jan 09 '19 at 13:46
  • I set the values for S, x, y. I just need to understand how to solve for n – Yuri Vaskovski Jan 09 '19 at 13:56
  • Could you precise if $n$ is supposed to be small (such as $n=1+\epsilon$ ? If this is the case, we can derive quite nice approximations. – Claude Leibovici Jan 13 '19 at 09:32

3 Answers3

3

The equation can be written

$$\frac{n^y-1}{n-1}=\frac Sx$$ or in the polynomial form

$$n^y-\frac Sxn+\frac Sx-1=0.$$

Such an equation doesn't have a closed-form solution, except for a few small values of the degree $y$.

A numerical solution by Newton's method works well.

2

The practical way to do it, assuming $ S > xy$. You take the following function $$ f(n) = \left(1+\frac Sx n-\frac Sx \right)^{1/y} $$

and then apply it to itself, until result no longer changes, starting with $n_0=1+1/y$: $n_1=f(n_0)$, $n_2=f(n_1)$ and so on.

For example, for $y=9$, $S/x=15$, we have the following $$n=1.111, 1.115, 1.118, 1.120, 1.121, 1.122, 1.122\dots$$

Vasily Mitch
  • 10,129
0

As Yves Daoust wrote, you are looking for the zero of function $$f(n)=n^y-\frac{ S}{x}(n-1)-1$$ Consider its derivatives $$f'(n)=y\, n^{y-1}-\frac{S}{x}$$ $$f''(n)=y\,(y-1) \, n^{y-2}$$ For $y>1$, the second derivative is always positive.

The first derivative cancels at $$n_*=\left(\frac{S}{x y}\right)^{\frac{1}{y-1}}$$ So, if $f(n_*)<0$ (remember that $n=1$ is a trivial solution to be discarded), to get a starting point for Newton method, expand $f(n)$ as a Taylor series to second order around $n=n_*$ to get $$f(n)=f(n_*)+\frac 12 f''(n_*) (n-n*)^2+O\left((n-n_*)^3\right)$$ and, ignoring the high order tems $$n_0=n_*+\sqrt{-2\frac{f(n_*) }{f''(n_*) }}$$

Now, iterate using $$n_{k+1}=n_k-\frac{ f(n_k)} { f'(n_k)}$$

For the values used by Vasily Mitch $(y=9,S=15x)$, $n_*=1.06594$ , $n_0=1.12738$ anf the iterates would be $$\left( \begin{array}{cc} k & n_k \\ 0 & 1.127375420 \\ 1 & 1.123698919 \\ 2 & 1.123557057 \\ 3 & 1.123556849 \end{array} \right)$$

Let us do the same with huge numbers : $y=123$, $S=123456789\,x$. This will give $n_*=1.11994$ and $n_0=1.16505$. Newton iterates would be $$\left( \begin{array}{cc} k & n_k \\ 0 & 1.165045878 \\ 1 & 1.156842265 \\ 2 & 1.150315554 \\ 3 & 1.146560370 \\ 4 & 1.145520226 \\ 5 & 1.145454006 \\ 6 & 1.145453756 \end{array} \right)$$

Claude Leibovici
  • 260,315