A383441 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

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.

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);