login
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.
12

%I #20 Oct 16 2024 21:53:37

%S 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,

%T 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,

%U 7,6,5,4,3,2,47,24,16,12,10,8,7,6,5,4,3,2

%N 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.

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

%C 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

%D Martin Gardner, The Last Recreations, 1997, chapter 12.

%H Curtis Bechtel, <a href="/A049805/b049805.txt">Table of n, a(n) for n = 1..5050</a>

%e 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.

%e Triangle starts:

%e 2;

%e 3, 2;

%e 5, 3, 2;

%e 7, 4, 3, 2;

%e 11, 6, 4, 3, 2;

%e 13, 7, 5, 4, 3, 2;

%e ...

%t T[n_, k_] := Count[FareySequence[n], f_ /; f <= 1/k];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 25 2018 *)

%o (PARI) row(nn) = my(frow = farey(n)); for (k=1, n, print1(vecsearch(frow, 1/k), ", ");); \\ _Michel Marcus_, Jun 27 2014

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

%Y Cf. A006842, A006843.

%K nonn,tabl

%O 1,1

%A _Clark Kimberling_