A049805 Triangular array T read by rows: T(n,k) is the number of Farey fractions of order n that are <= 1/k for k=1..n, for n>=1.

2, 3, 2, 5, 3, 2, 7, 4, 3, 2, 11, 6, 4, 3, 2, 13, 7, 5, 4, 3, 2, 19, 10, 7, 5, 4, 3, 2, 23, 12, 8, 6, 5, 4, 3, 2, 29, 15, 10, 8, 6, 5, 4, 3, 2, 33, 17, 12, 9, 7, 6, 5, 4, 3, 2, 43, 22, 15, 11, 9, 7, 6, 5, 4, 3, 2, 47, 24, 16, 12, 10, 8, 7, 6, 5, 4, 3, 2

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• tabl

Comments

So, T(n, k) is also the index of fraction 1/k in the Farey fractions of order n. - Michel Marcus, Jun 27 2014

Start with array [1,k], and for each integer i from k+1 to n, insert i between every consecutive pair that sums to i. The length of the resulting array is T(n,k). For example, with n=5 and k=2 we have [1,2] -> [1,3,2] -> [1,4,3,2] -> [1,5,4,3,5,2] which has length 6, so T(5,2)=6. This is from a discovery of Leo Moser as described by Martin Gardner. - Curtis Bechtel, Oct 05 2024

Examples

			Rows: {2}; {3,2}; {5,3,2}; ...; e.g. in row 3, 5 reduced fractions (0/1,1/3,1/2,2/3,1/1) are <=1; 3 are <=1/2; 2 are <=1/3.
Triangle starts:
  2;
  3, 2;
  5, 3, 2;
  7, 4, 3, 2;
  11, 6, 4, 3, 2;
  13, 7, 5, 4, 3, 2;
  ...
		

References

• Martin Gardner, The Last Recreations, 1997, chapter 12.

Links

• Curtis Bechtel, Table of n, a(n) for n = 1..5050

Crossrefs

First column: T(n, 1) = A005728(n+1).

Cf. A006842, A006843.

Programs

Mathematica

T[n_, k_] := Count[FareySequence[n], f_ /; f <= 1/k];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 25 2018 *)

PARI

row(nn) = my(frow = farey(n)); for (k=1, n, print1(vecsearch(frow, 1/k), ", ");); \\ Michel Marcus, Jun 27 2014