cp's OEIS Frontend

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.

%I A383441 #18 May 18 2025 08:13:05
%S A383441 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,
%T A383441 63,64,72,62,96,69,104,49,80,84,86,64,123,103,118,77,130,94,152,115,
%U A383441 128,151,174,90,163,138,164,144,197,157,188,144,187,206,229,157,251
%N 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.
%C A383441 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.
%D A383441 Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, section 4.7, p. 83.
%D A383441 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.
%H A383441 Peter Luschny, <a href="/A383441/b383441.txt">Table of n, a(n) for n = 0..10000</a>
%H A383441 Richard P. Brent, <a href="https://doi.org/10.48550/arXiv.1303.2772">Further analysis of the binary Euclidean algorithm</a>, Technical Report PRG TR-7-99, Oxford University Computing Laboratory, November 1999, arXiv:1303.2772 [cs.DS].
%H A383441 Peter Luschny, <a href="https://github.com/PeterLuschny/Gists/blob/main/BinaryGcd.py">Binary Gcd</a>, May 2025.
%H A383441 Peter Luschny, <a href="/A383441/a383441.png">Illustration of the distribution of the values</a>.
%H A383441 Damien Stehlé and Paul Zimmermann, <a href="https://inria.hal.science/inria-00071533v1/document">A Binary Recursive Gcd Algorithm</a>, 6th International Symposium on Algorithmic Number Theory - ANTS VI, 2004, Burligton, US, pp. 411-425.
%p A383441 gcd_bin_count := proc(a, b) local count, odd, A, B, D;
%p A383441 if a = 0 or a = b or b = 0 then return 0 fi; count := 0;
%p A383441 odd := n -> n*2^(-padic:-ordp(n, 2));  # A000265
%p A383441 A := odd(a); B := odd(b);
%p A383441 while B <> A do count := count + 1;
%p A383441    D := ifelse(A < B, B - A, A - B);
%p A383441    B := ifelse(A < B, A, B);
%p A383441    A := odd(D);
%p A383441 od; count end:
%p A383441 a := n -> local k; add(gcd_bin_count(n, k), k = 0..n):
%p A383441 seq(a(n), n = 0..61);
%o A383441 (Python)  # See the links.
%Y A383441 Cf. A109004, A000265.
%K A383441 nonn
%O A383441 0,4
%A A383441 _Peter Luschny_, May 16 2025