login
A358110
Indices of the harmonic numbers in the Stern-Brocot sequence (A002487).
1
0, 1, 5, 125, 8195, 32675, 755, 34763, 520283, 37773179, 21743337467, 4647489635464983347207, 1236947931143, 272658152711, 604398345569737906323527, 9595849053479089263878087, 3693713292455, 288389531265129191, 11150032316898390632304469945009811031588839
OFFSET
0,3
COMMENTS
We assume the harmonic numbers to start with H(0) = 0.
REFERENCES
Edsger W. Dijkstra, Selected Writings on Computing, Springer, 1982, p. 232 (sequence A002487 is called fusc).
FORMULA
a(n) = A355090(A001008(n), A002805(n)) for any n > 0. - Rémy Sigrist, Nov 08 2022
EXAMPLE
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.
PROG
(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
(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
CROSSREFS
Cf. A002487, A001008/A002805 (harmonic), A355090.
Sequence in context: A154022 A013710 A202628 * A109345 A194502 A229868
KEYWORD
nonn
AUTHOR
Peter Luschny, Nov 08 2022
EXTENSIONS
More terms from Rémy Sigrist, Nov 08 2022
STATUS
approved