3
$\begingroup$

I'd like to look at behavior of $f(n)$ for the following $f$

$$\begin{array}{lll} g(s,n)&=&\frac{1}{n}\sum_i^n \left(1-\frac{1}{i}\right)^s\\ f(n)&=&\text{smallest } s \text{ such that } g(s,n)<10^{-6} \end{array}$$

My naive implementation is below, but it's too slow to make a good plot in reasonable time. Any tips how to speed this up?

g[s_, n_] := Total@Table[(1. - 1/i)^s, {i, 1, n}]/n;
f[n_] := (For[i = 1, i < 20 n, i++,
   If[g[i, n] < 10^(-6), Break[]]]; i)
f[1000] // Timing (* {1.74248, 11243} *)
$\endgroup$
7
  • $\begingroup$ the hypothesis is that $f(n)$ is linear in $n$ $\endgroup$ Jun 17 at 19:41
  • $\begingroup$ Maybe something along the lines of FindRoot[g[s, 1000] == 10^-6, {s, 100}]? $\endgroup$
    – Carl Woll
    Jun 17 at 19:45
  • $\begingroup$ Was just in the process of trying Carl Woll's suggestion: $\endgroup$ Jun 17 at 19:56
  • $\begingroup$ zero[n_, s_] := n 10^(-6) - NSum[(1 - 1/i)^s, {i, 1, n}] $\endgroup$ Jun 17 at 19:56
  • $\begingroup$ lastSolution = s /. FindRoot[zero[10, s], {s, 2}];Table[{2^n, lastSolution = s /. FindRoot[zero[2^n, s], {s, lastSolution}]}, {n, 1, 12}];ListPlot[%] but slows down for larger n... $\endgroup$ Jun 17 at 19:57
5
$\begingroup$

Could do it recursively, using FindRoot with starting point determined by previous value (per comment by @CraigCarter).

ff[3] = 1;
ff[n_Integer] := 
 ff[n] = Floor[
   s /. FindRoot[
     Sum[((i - 1)/i)^s, {i, 2, n}] == n*10^(-6), {s, ff[n - 1]},
WorkingPrecision -> Log[2, n] + $MachinePrecision]]

Check result:

ListPlot[Table[ff[n], {n, 3, 100}]]

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ thanks! Fixed a typo, now the result seems perfectly linear. There's probably an analytic way to derive this $\endgroup$ Jun 22 at 0:35
  • $\begingroup$ Thanks @YaroslavBulatov. Does look like it is approximately linear. $\endgroup$ Jun 22 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.