login
Least k such that H(k) > n, where H(k) is the harmonic number Sum_{i=1..k} 1/i.
(Formerly M1249 N1385)
82

%I M1249 N1385 #126 Apr 10 2024 22:01:01

%S 1,2,4,11,31,83,227,616,1674,4550,12367,33617,91380,248397,675214,

%T 1835421,4989191,13562027,36865412,100210581,272400600,740461601,

%U 2012783315,5471312310,14872568831,40427833596,109894245429,298723530401,812014744422

%N Least k such that H(k) > n, where H(k) is the harmonic number Sum_{i=1..k} 1/i.

%C From _Dean Hickerson_, Apr 19 2003: (Start)

%C For k >= 1, log(k + 1/2) + gamma < H(k) < log(k + 1/2) + gamma + 1/(24k^2), where gamma is Euler's constant (A001620). It is likely that the upper and lower bounds have the same floor for all k >= 2, in which case a(n) = floor(exp(n-gamma) + 1/2) for all n >= 0.

%C This remark is based on a simple heuristic argument. The lower and upper bounds differ by 1/(24k^2), so the probability that there's an integer between the two bounds is 1/(24k^2). Summing that over all k >= 2 gives the expected number of values of k for which there's an integer between the bounds. That sum equals Pi^2/144 - 1/24 ~ 0.02687. That's much less than 1, so it is unlikely that there are any such values of k.

%C (End)

%C Referring to A118050 and A118051, using a few terms of the asymptotic series for the inverse of H(x), we can get an expression which, with greater likelihood than mentioned above, should give a(n) for all n >= 0. For example, using the same type of heuristic argument given by _Dean Hickerson_, it can be shown that, with probability > 99.995%, we should have, for all n >= 0, a(n) = floor(u + 1/2 - 1/(24u) + 3/(640u^3)) where u = e^(n - gamma). - David W. Cantrell (DWCantrell(AT)sigmaxi.net)

%C For k > 1, H(k) is never an integer. Hence apart from the first two terms this sequence coincides with A004080. - _Nick Hobson_, Nov 25 2006

%D John H. Conway and R. K. Guy, "The Book of Numbers," Copernicus, an imprint of Springer-Verlag, NY, 1996, pages 258-259.

%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 83, p. 28, Ellipses, Paris 2008.

%D Ronald Lewis Graham, Donald Ervin Knuth and Oren Patashnik, "Concrete Mathematics, a Foundation for Computer Science," Addison-Wesley Publishing Co., Reading, MA, 1989, Page 258-264, 438.

%D H. P. Robinson, Letter to N. J. A. Sloane, Oct 23 1973.

%D W. Sierpiński, Sur les decompositions de nombres rationnels, Oeuvres Choisies, Académie Polonaise des Sciences, Warsaw, Poland, 1974, p. 181.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane, Illustration for sequence M4299 (=A007340) in The Encyclopedia of Integer Sequences (with Simon Plouffe), Academic Press, 1995.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D I. Stewart, L'univers des nombres, pp. 54, Belin-Pour La Science, Paris 2000.

%H Robert G. Wilson v, <a href="/A002387/b002387.txt">Table of n, a(n) for n = 0..2303</a> (first 101 terms from T. D. Noe)

%H John V. Baxley, <a href="http://www.jstor.org/stable/2691241">Euler's constant, Taylor's formula, and slowly converging series</a>, Math. Mag. 65 (1992), 302-313. (Gives terms up to n = 24.)

%H R. P. Boas, <a href="/A002387/a002387_1.pdf">Partial sums of the harmonic series, II</a>, Mimeographed manuscript, no date.

%H R. P. Boas, Jr. and J. W. Wrench, Jr., <a href="http://www.jstor.org/stable/2316476">Partial sums of the harmonic series</a>, Amer. Math. Monthly, 78 (1971), 864-870. (Gives terms up to n = 20.)

%H Nick Hobson, <a href="https://web.archive.org/web/20160802195036/http://www.qbyte.org/puzzles/p034s.html">Solution to puzzle 34: Harmonic sum 2</a>.

%H H. P. Robinson, <a href="/A003115/a003115.pdf">Letter to N. J. A. Sloane, Oct 28 1973</a>.

%H H. P. Robinson, <a href="/A006530/a006530.pdf">Letter to N. J. A. Sloane, Oct 1981</a>

%H H. P. Robinson, <a href="/A002387/a002387_2.pdf">Letter to N. J. A. Sloane, Dec 20 1983</a>

%H John A. Rochowicz, Jr., <a href="http://epublications.bond.edu.au/ejsie/vol8/iss2/4">Harmonic Numbers: Insights, Approximations and Applications</a>, Spreadsheets in Education (eJSiE) (2015), Vol. 8: Iss. 2, Article 4.

%H R. G. Wilson, <a href="/A006509/a006509.pdf">Letter to N. J. A. Sloane with attachment, Jan 1989</a> (A006509 is mentioned in the attachment)

%H R. G. Wilson v, <a href="/A002387/a002387.pdf">Letter to N. J. A. Sloane, Oct 12 1993</a>

%H J. W. Wrench, Jr., <a href="/A002387/a002387_3.pdf">Selected Partial Sums of the Harmonic Series</a>, Manuscript, no date [Annotated scanned copy]

%F Note that the conditionally convergent series Sum_{k>=1} (-1)^(k+1)/k = log 2 (A002162).

%F Limit_{n->oo} a(n+1)/a(n) = e. - _Robert G. Wilson v_, Dec 07 2001

%F It is conjectured that, for n > 1, a(n) = floor(exp(n-gamma) + 1/2). - _Benoit Cloitre_, Oct 23 2002

%t fh[0]=0; fh[1]=1; fh[k_] := Module[{tmp}, If[Floor[tmp=Log[k+1/2]+EulerGamma]==Floor[tmp+1/(24k^2)], Floor[tmp], UNKNOWN]]; a[0]=1; a[1]=2; a[n_] := Module[{val}, val=Round[Exp[n-EulerGamma]]; If[fh[val]==n&&fh[val-1]==n-1, val, UNKNOWN]]; (* fh[k] is either floor(H(k)) or UNKNOWN *)

%t f[n_] := k /. FindRoot[HarmonicNumber[k] == n, {k, Exp[n]}, WorkingPrecision -> 100] // Ceiling; f[0] = 1; Array[f, 28, 0] (* _Robert G. Wilson v_, Jan 24 2017 after _Jean-François Alcover_ in A014537 *)

%o (PARI) a(n)=if(n,my(k=exp(n-Euler));ceil(solve(x=k-1.5,k+.5,intnum(y=0,1,(1-y^x)/(1-y))-n)),1) \\ _Charles R Greathouse IV_, Jun 13 2012

%o (Haskell)

%o a002387 n = a002387_list !! n

%o a002387_list = f 0 1 where

%o f x k = if hs !! k > fromIntegral x

%o then k : f (x + 1) (k + 1) else f x (k + 1)

%o where hs = scanl (+) 0 $ map recip [1..]

%o -- _Reinhard Zumkeller_, Aug 04 2014

%Y Apart from initial terms, same as A004080.

%Y Cf. A006509, A055980, A115515, A242654.

%K nonn,nice

%O 0,2

%A _N. J. A. Sloane_

%E Terms for n >= 13 computed by _Eric W. Weisstein_; corrected by _James R. Buddenhagen_ and _Eric W. Weisstein_, Feb 18 2001

%E Edited by _Dean Hickerson_, Apr 19 2003