A050873 Triangular array T read by rows: T(n,k) = gcd(n,k).

1, 1, 2, 1, 1, 3, 1, 2, 1, 4, 1, 1, 1, 1, 5, 1, 2, 3, 2, 1, 6, 1, 1, 1, 1, 1, 1, 7, 1, 2, 1, 4, 1, 2, 1, 8, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• tabl
• look

Comments

The function T(n,k) = T(k,n) is defined for all integer k,n but only the values for 1 <= k <= n as a triangular array are listed here.

For each divisor d of n, the number of d's in row n is phi(n/d). Furthermore, if {a_1, a_2, ..., a_phi(n/d)} is the set of positive integers <= n/d that are relatively prime to n/d then T(n,a_i * d) = d. - Geoffrey Critzer, Feb 22 2015

Starting with any row n and working downwards, consider the infinite rectangular array with k = 1..n. A repeating pattern occurs every A003418(n) rows. For example, n=3: A003418(3) = 6. The 6-row pattern starting with row 3 is {1,1,3}, {1,2,1}, {1,1,1}, {1,2,3}, {1,1,1}, {1,2,1}, and this pattern repeats every 6 rows, i.e., starting with rows {9,15,21,27,...}. - Bob Selcoe and Jamie Morken, Aug 02 2017

Examples

			Rows:
  1;
  1, 2;
  1, 1, 3;
  1, 2, 1, 4;
  1, 1, 1, 1, 5;
  1, 2, 3, 2, 1, 6; ...
		

Links

• T. D. Noe, Rows n=1..100, flattened
• Marcelo Polezzi, A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.
• Eric Weisstein's World of Mathematics, Greatest Common Divisor
• Wikipedia, Greatest Common Divisor

Crossrefs

Cf. A003989.

Cf. A002262, A054531, A226314.

Cf. A018804 (row sums), A245717.

Cf. A132442 (sums of divisors).

Cf. A003418.

Programs

Haskell

a050873 = gcd
a050873_row n = a050873_tabl !! (n-1)
a050873_tabl = zipWith (map . gcd ) [1..] a002260_tabl
-- Reinhard Zumkeller, Dec 12 2015, Aug 13 2013, Jun 10 2013

Mathematica

ColumnForm[Table[GCD[n, k], {k, 12}, {n, k}], Center] (* Alonso del Arte, Jan 14 2011 *)

PARI

{T(n, k) = gcd(n, k)} /* Michael Somos, Jul 18 2011 */

Formula

a(n) = gcd(A002260(n), A002024(n)); A054521(n) = A000007(a(n)). - Reinhard Zumkeller, Dec 02 2009

T(n,k) = A075362(n,k)/A051173(n,k), 1 <= k <= n. - Reinhard Zumkeller, Apr 25 2011

T(n, k) = T(k, n) = T(-n, k) = T(n, -k) = T(n, n+k) = T(n+k, k). - Michael Somos, Jul 18 2011

T(n,k) = A051173(n,k) / A051537(n,k). - Reinhard Zumkeller, Jul 07 2013