A383441 a(n) is the total of iterations needed in the binary GCD algorithm to compute gcd(n, k) for k = 0..n. The corresponding row of gcds is row n of A109004.

0, 0, 0, 2, 1, 5, 5, 12, 5, 11, 12, 23, 13, 29, 27, 31, 17, 38, 26, 47, 31, 42, 51, 70, 35, 63, 64, 72, 62, 96, 69, 104, 49, 80, 84, 86, 64, 123, 103, 118, 77, 130, 94, 152, 115, 128, 151, 174, 90, 163, 138, 164, 144, 197, 157, 188, 144, 187, 206, 229, 157, 251

Offset: 0

Author

Peter Luschny, May 16 2025

Keywords

• nonn

Comments

The reference Python implementation is provided in the links. It is a variant of Algorithm B described by Knuth in TAOCP Vol. 2, potentially offering some speedup in Python.

References

• Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, section 4.7, p. 83.
• D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 2, Seminumerical Algorithms. Chapter 4.5.2 The greatest Common Divisor, Page 321, Algorithm B.

Links

• Peter Luschny, Table of n, a(n) for n = 0..10000
• Richard P. Brent, Further analysis of the binary Euclidean algorithm, Technical Report PRG TR-7-99, Oxford University Computing Laboratory, November 1999, arXiv:1303.2772 [cs.DS].
• Peter Luschny, Binary Gcd, May 2025.
• Peter Luschny, Illustration of the distribution of the values.
• Damien Stehlé and Paul Zimmermann, A Binary Recursive Gcd Algorithm, 6th International Symposium on Algorithmic Number Theory - ANTS VI, 2004, Burligton, US, pp. 411-425.

Crossrefs

Cf. A109004, A000265.

Programs

Maple

gcd_bin_count := proc(a, b) local count, odd, A, B, D;
if a = 0 or a = b or b = 0 then return 0 fi; count := 0;
odd := n -> n*2^(-padic:-ordp(n, 2));  # A000265
A := odd(a); B := odd(b);
while B <> A do count := count + 1;
   D := ifelse(A < B, B - A, A - B);
   B := ifelse(A < B, A, B);
   A := odd(D);
od; count end:
a := n -> local k; add(gcd_bin_count(n, k), k = 0..n):
seq(a(n), n = 0..61);

Python

# See the links.