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,2

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

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.

Example

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;

Mathematica

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

Prog

(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
(PARI) for(n=1, 10, for(k=1, n, print1(n/gcd(n, k), ", "))) \\ G. C. Greubel, Sep 13 2017

Crossrefs

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

Sequence in context: A134625 A325477 A277227 * A324602 A319226 A307449

Adjacent sequences: A054528 A054529 A054530 * A054532 A054533 A054534

Keyword

nonn,tabl,frac,easy

Author

N. J. A. Sloane, Apr 09 2000

Status

approved