cp's OEIS Frontend

A358110 Indices of the harmonic numbers in the Stern-Brocot sequence (A002487).

%I A358110 #23 Nov 08 2022 18:02:28
%S A358110 0,1,5,125,8195,32675,755,34763,520283,37773179,21743337467,
%T A358110 4647489635464983347207,1236947931143,272658152711,
%U A358110 604398345569737906323527,9595849053479089263878087,3693713292455,288389531265129191,11150032316898390632304469945009811031588839
%N A358110 Indices of the harmonic numbers in the Stern-Brocot sequence (A002487).
%C A358110 We assume the harmonic numbers to start with H(0) = 0.
%D A358110 Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence A002487 is called fusc).
%H A358110 Edsger W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF">More about the function "fusc"</a>.
%H A358110 Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/SternsDiatomic">Rational Trees and Binary Partitions</a>.
%H A358110 Rémy Sigrist, <a href="/A358110/a358110.png">Logarithmic binary plot of the sequence for n = 0..2048</a>
%F A358110 a(n) = A355090(A001008(n), A002805(n)) for any n > 0. - _Rémy Sigrist_, Nov 08 2022
%e A358110 Let Fusc(n) = fusc(n) / fusc(n + 1) where fusc = A002487.
%e A358110           0 = H(0) = Fusc(0)      => a(0) = 0.
%e A358110           1 = H(1) = Fusc(1)      => a(1) = 1.
%e A358110       (3/2) = H(2) = Fusc(5)      => a(2) = 5.
%e A358110      (11/6) = H(3) = Fusc(125)    => a(3) = 125.
%e A358110     (25/12) = H(4) = Fusc(8195)   => a(4) = 8195.
%e A358110    (137/60) = H(5) = Fusc(32675)  => a(5) = 32676.
%e A358110     (49/20) = H(6) = Fusc(755)    => a(6) = 755.
%e A358110   (363/140) = H(7) = Fusc(34763)  => a(7) = 34763.
%e A358110   (761/280) = H(8) = Fusc(520283) => a(8) = 520283.
%o A358110 (PARI) a(n) = { my (h=sum(i=1, n, 1/i), x=numerator(h), y=denominator(h)); if (x==0, 0, my (v=0, t=1, a=0, b=1, c=1, d=0); while (1, my (m=a+c, n=b+d); if (x*n==y*m, return (t+v), x*n<y*m, [c, d]=[m, n], [v, a, b]=[v+t, m, n]); t*=2)) } \\ _Rémy Sigrist_, Nov 08 2022
%o A358110 (Python) # using function harmonic from A001008
%o A358110 def A358110(n: int) -> int:
%o A358110     if n == 0: return 0
%o A358110     x, y = harmonic(1, n + 1)
%o A358110     a = d = v = 0
%o A358110     b = c = t = 1
%o A358110     while True:
%o A358110         m = a + c
%o A358110         n = b + d
%o A358110         if x * n == y * m:
%o A358110             return v + t
%o A358110         if x * n < y * m:
%o A358110             c, d = m, n
%o A358110         else:
%o A358110             v, a, b = v + t, m, n
%o A358110         t *= 2
%o A358110 print([A358110(n) for n in range(19)]) # (after _Rémy Sigrist_) _Peter Luschny_, Nov 08 2022
%Y A358110 Cf. A002487, A001008/A002805 (harmonic), A355090.
%K A358110 nonn
%O A358110 0,3
%A A358110 _Peter Luschny_, Nov 08 2022
%E A358110 More terms from _Rémy Sigrist_, Nov 08 2022