A109004 - OEIS

%I #31 Oct 17 2019 00:16:33

%S 0,1,1,2,1,2,3,1,1,3,4,1,2,1,4,5,1,1,1,1,5,6,1,2,3,2,1,6,7,1,1,1,1,1,

%T 1,7,8,1,2,1,4,1,2,1,8,9,1,1,3,1,1,3,1,1,9,10,1,2,1,2,5,2,1,2,1,10,11,

%U 1,1,1,1,1,1,1,1,1,1,11,12,1,2,3,4,1,6,1,4,3,2,1,12,13,1,1,1,1,1,1,1,1,1,1,1,1,13

%N Table of gcd(n,m) read by antidiagonals, n >= 0, m >= 0.

%D L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, p. 335.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.

%D D. E. Knuth, The Art of Computer Programming, Addison-Wesley, section 4. 5. 2

%H Alois P. Heinz, <a href="/A109004/b109004.txt">Antidiagonals n = 0..140, flattened</a>

%H Marcelo Polezzi, <a href="http://www.jstor.org/stable/2974739">A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor</a>, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.

%F a(n, m) = a(m, n) = a(m, n-m) = a(m, n mod m), n >= m.

%F a(n, m) = n + m - n*m + 2*Sum_{k=1..m-1} floor(k*n/m).

%F Multiplicative in both parameters with a(p^e, m) = gcd(p^e, m). - _David W. Wilson_, Jun 12 2005

%e 0;

%e 1, 1;

%e 2, 1, 2;

%e 3, 1, 1, 3;

%e 4, 1, 2, 1, 4;

%e 5, 1, 1, 1, 1, 5;

%e 6, 1, 2, 3, 2, 1, 6;

%e ...

%t a[n_, m_] := GCD[n, m]; Table[a[n - m, m], {n,0,10}, {m,0,n}]//Flatten (* _G. C. Greubel_, Jan 04 2018 *)

%o (PARI) {a(n, m) = gcd( n, m)}

%o (PARI) {a(n, m) = local(x); n = abs(n); m = abs(m); if( !m, n, -2 * sum( k=1, m, x = k * n / m; x - floor( x) - 1/2))} /* _Michael Somos_, May 22 2011 */

%Y Rows, columns and diagonals: A089128, A109007, A109008, A109009, A109010, A109011, A109012, A109013, A109014, A109015.

%Y A003989 is (1, 1) based.

%K nonn,easy,mult,tabl

%O 0,4

%A _Mitch Harris_