A362150 -id:A362150 - cp's OEIS frontend

A362149 Decimal expansion of K, a constant arising in the analysis of the binary Euclidean algorithm.

7, 0, 5, 9, 7, 1, 2, 4, 6, 1, 0, 1, 9, 1, 6, 3, 9, 1, 5, 2, 9, 3, 1, 4, 1, 3, 5, 8, 5, 2, 8, 8, 1, 7, 6, 6, 6, 6, 7, 7

Offset: 0

Paolo Xausa, Apr 09 2023

Corresponds to the 2/b constant reported in Knuth (1998), p. 352.

Vallée (1998) conjectured that this constant times A362150 equals 4*log(2)/Pi^2; Brent (1999) supported the conjecture with numerical computations and Morris (2016) proved the conjecture.

			0.7059712461019163915293141358528817666677...

Richard P. Brent, Further analysis of the binary Euclidean algorithm, Programming Research Group technical report TR-7-99, Oxford University (1999) (see also the arXiv link).
Steven R. Finch, Mathematical Constants, Cambridge University Press, New York, NY, 2003, p. 158.
Donald E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1998, Sect. 4.5.2, pp. 348-353.

Richard P. Brent, Further analysis of the binary Euclidean algorithm, arXiv:1303.2772 [cs.DS], 1999, p. 12.
Ian D. Morris, A rigorous version of R. P. Brent's model for the binary Euclidean algorithm, Advances in Mathematics, Vol. 290, 26 Feb. 2016, pp. 73-143.
Brigitte Vallée, Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators, Algorithmica 22 (1998), pp. 660-685.
Wikipedia, Binary GCD algorithm.

Cf. A118858, A345987, A362150.

Equals (4*log(2)/Pi^2)/A362150 = 4*A118858/A362150.

A375066 Decimal expansion of Hensley's constant, arising in the analysis of the Euclidean algorithm.

Original entry on oeis.org

5, 1, 6, 0, 6, 2, 4, 0, 8, 8, 9, 9, 9, 9, 1, 8, 0, 6, 8, 1

Offset: 0

Paolo Xausa, Jul 29 2024

Appears in the formula for the asymptotic variance of the Euclidean algorithm.

When applying the Euclidean algorithm on pairs (a, b), with 0 <= a <= b <= x, the asymptotic formula for the variance of the number of steps (divisions), as x -> infinity, is H*log(x), where H is this constant. See Lhote (2004), eq. 1.8.

			0.51606240889999180681...

Philippe Flajolet and Brigitte Vallée, Continued Fractions, Comparison Algorithms, and Fine Structure Constants, Research Report RR-4072, INRIA, 2000, p. 24.
Doug Hensley, The Number of Steps in the Euclidean Algorithm, Journal of Number Theory, Vol. 49, Issue 2, November 1994, pp. 142-182.
Doug Hensley, Continued Fractions, World Scientific, 2006, p. 210.
Loïck Lhote, Computation of a class of continued fraction constants, in Arge et al., Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004, pp. 199-210.
Wikipedia, Euclidean algorithm.

Cf. A089729, A174606, A345987, A362149, A362150.

Equals 2*(lambda''(1) - lambda'(1)^2) / (-lambda'(1)^3), where lambda'(1) = -Pi^2/(6*log(2)) = -A174606 and lambda''(1) is 9.08037... See Lhote (2004), eq. 1.8, and Flajolet and Vallée (2000), p. 24 (where lambda''(1) is called the Hensley's constant).

cp's OEIS Frontend

A362149 Decimal expansion of K, a constant arising in the analysis of the binary Euclidean algorithm.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula