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

0, 1, 5, 125, 8195, 32675, 755, 34763, 520283, 37773179, 21743337467, 4647489635464983347207, 1236947931143, 272658152711, 604398345569737906323527, 9595849053479089263878087, 3693713292455, 288389531265129191, 11150032316898390632304469945009811031588839

Offset: 0

Author

Peter Luschny, Nov 08 2022

Keywords

• nonn

Comments

We assume the harmonic numbers to start with H(0) = 0.

Examples

			Let Fusc(n) = fusc(n) / fusc(n + 1) where fusc = A002487.
          0 = H(0) = Fusc(0)      => a(0) = 0.
          1 = H(1) = Fusc(1)      => a(1) = 1.
      (3/2) = H(2) = Fusc(5)      => a(2) = 5.
     (11/6) = H(3) = Fusc(125)    => a(3) = 125.
    (25/12) = H(4) = Fusc(8195)   => a(4) = 8195.
   (137/60) = H(5) = Fusc(32675)  => a(5) = 32676.
    (49/20) = H(6) = Fusc(755)    => a(6) = 755.
  (363/140) = H(7) = Fusc(34763)  => a(7) = 34763.
  (761/280) = H(8) = Fusc(520283) => a(8) = 520283.
		

References

• Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence A002487 is called fusc).

Links

• Edsger W. Dijkstra, More about the function "fusc".
• Peter Luschny, Rational Trees and Binary Partitions.
• Rémy Sigrist, Logarithmic binary plot of the sequence for n = 0..2048

Crossrefs

Cf. A002487, A001008/A002805 (harmonic), A355090.

Programs

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*nRémy Sigrist, Nov 08 2022

Python

# using function harmonic from A001008
def A358110(n: int) -> int:
    if n == 0: return 0
    x, y = harmonic(1, n + 1)
    a = d = v = 0
    b = c = t = 1
    while True:
        m = a + c
        n = b + d
        if x * n == y * m:
            return v + t
        if x * n < y * m:
            c, d = m, n
        else:
            v, a, b = v + t, m, n
        t *= 2
print([A358110(n) for n in range(19)]) # (after Rémy Sigrist) Peter Luschny, Nov 08 2022

Formula

a(n) = A355090(A001008(n), A002805(n)) for any n > 0. - Rémy Sigrist, Nov 08 2022

Extensions

More terms from Rémy Sigrist, Nov 08 2022