A054531 Triangular array T read by rows: T(n,k) = n/gcd(n,k) (n >= 1, 1 <= k <= n).

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

Offset: 1

Author

N. J. A. Sloane, Apr 09 2000

Keywords

• nonn
• tabl
• frac
• easy

Comments

Sum of n-th row = A057660(n). - Reinhard Zumkeller, Aug 12 2009

Read as a linear sequence, this is conjectured to be the length of the shortest cycle of pebble-moves among the partitions of n (cf. A201144). - Andrew V. Sutherland, Nov 27 2011

The triangle of fractions A226314(i,j)/A054531(i,j) is an efficient way to enumerate the rationals [Fortnow]. - N. J. A. Sloane, Jun 09 2013

Examples

			Triangle begins
   1;
   2,  1;
   3,  3,  1;
   4,  2,  4,  1;
   5,  5,  5,  5,  1;
   6,  3,  2,  3,  6,  1;
   7,  7,  7,  7,  7,  7,  1;
   8,  4,  8,  2,  8,  4,  8,  1;
   9,  9,  3,  9,  9,  3,  9,  9,  1;
  10,  5, 10,  5,  2,  5, 10,  5, 10,  1;
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11,  1;
  12,  6,  4,  3, 12,  2, 12,  3,  4,  6, 12,  1;
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,  1;
		

Links

• Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
• Lance Fortnow, Counting the Rationals Quickly, Computational Complexity Weblog, Monday, March 01, 2004.
• R. J. Mathar, Plots of cycle graphs of the finite groups up to order 36, (2015).
• Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Crossrefs

Cf. A050873, A164306, A226314, A277227 (row reversed, k=0..n-1).

Programs

Haskell

a054531 n k = div n $ gcd n k
a054531_row n = a054531_tabl !! (n-1)
a054531_tabl = zipWith (\u vs -> map (div u) vs) [1..] a050873_tabl
-- Reinhard Zumkeller, Jun 10 2013

Mathematica

Table[n/GCD[n,k], {n,1,10}, {k,1,n}]//Flatten (* G. C. Greubel, Sep 13 2017 *)

PARI

for(n=1,10, for(k=1,n, print1(n/gcd(n,k), ", "))) \\ G. C. Greubel, Sep 13 2017