A338579 Triangle T(D,N) read by rows, 1 <= N < D >= 2, where T(D,N) is the position of the fraction N/D in the Farey tree (or Stern-Brocot subtree) A007305/A007306.

2, 3, 4, 5, 2, 8, 9, 6, 7, 16, 17, 3, 2, 4, 32, 33, 10, 12, 13, 15, 64, 65, 5, 11, 2, 14, 8, 128, 129, 18, 3, 24, 25, 4, 31, 256, 257, 9, 20, 6, 2, 7, 29, 16, 512, 513, 34, 19, 21, 48, 49, 28, 30, 63, 1024, 1025, 17, 5, 3, 23, 2, 26, 4, 8, 32, 2048

Offset: 2

Author

Hugo Pfoertner, Nov 10 2020

Keywords

• nonn
• tabl

Comments

Fractions are reduced to lowest terms.

Examples

			The triangle begins
     N     1   2  3  4  5  6   7   8   9   10   11   12   13    14    15
   D \------------------------------------------------------------------
   2 |     2   .  .  .  .  .   .   .   .    .    .    .    .     .     .
   3 |     3   4  .  .  .  .   .   .   .    .    .    .    .     .     .
   4 |     5   2  8  .  .  .   .   .   .    .    .    .    .     .     .
   5 |     9   6  7 16  .  .   .   .   .    .    .    .    .     .     .
   6 |    17   3  2  4 32  .   .   .   .    .    .    .    .     .     .
   7 |    33  10 12 13 15 64   .   .   .    .    .    .    .     .     .
   8 |    65   5 11  2 14  8 128   .   .    .    .    .    .     .     .
   9 |   129  18  3 24 25  4  31 256   .    .    .    .    .     .     .
  10 |   257   9 20  6  2  7  29  16 512    .    .    .    .     .     .
  11 |   513  34 19 21 48 49  28  30  63 1024    .    .    .     .     .
  12 |  1025  17  5  3 23  2  26   4   8   32 2048    .    .     .     .
  13 |  2049  66 36 40 22 96  97  27  57   61  127 4096    .     .     .
  14 |  4097  33 35 10 41 12   2  13  56   15   62   64 8192     .     .
  15 |  8193 130  9 37  3  6 192 193   7    4   60   16  255 16384     .
  16 | 16385  65 68  5 80 11  47   2  50   14  113    8  125   128 32768
.
T(7,2) = 10 because A007306(10) = 7 and A007305(10) = 2 is the required double match, i.e., the position of the fraction 2/7 in the Farey tree is 10.
T(14,4) = T(7,2) = 10, because the fraction 4/14 reduced to lowest terms is 2/7.
T(16,12) = 8, because the fraction 12/16 reduced to lowest terms is 3/4, with the double match A007306(8)=4 and A007305(8)=3.
		

Links

• Hugo Pfoertner, Table of n, a(n) for n = 2..1226, rows 2..50, flattened.

Crossrefs

Cf. A007305, A007306, A054424, A054425.

Programs

PARI

\\ using Yosu Yurramendi's formulas
a338579(lim)={
my(a7305=vectorsmall(2+2^(lim+2)),a7306=vectorsmall(2+2^(lim+2)));
  a7305[1]=1;
  for(m=1,lim,
     for(k=0,2^(m-1)-1,
      a7305[2^m+k]=a7305[2^(m-1)+k];
      a7305[2^m+2^(m-1)+k]=a7305[2^(m-1)+k]+a7305[2^m-k-1]
     )
  );
  a7306[1]=1;a7306[2]=2;
  for(m=0,lim,
     for(k=1,2^m,
      a7306[2^(m+1)+k]=a7306[2^m+k] + a7306[k];
      a7306[2^(m+1)-k+1]=a7306[2^m+k]
     )
  );
   my(findinFS(x)=for(k=2,#a7306,
      if(!(a7305[k-1]/a7306[k]-x),return(k)));0);
  for(de=2,lim+2,for(nu=1,de-1,my(q=nu/de);print1(findinFS(q),", ")))
};
a338579(10);

PARI

T(d,n) = my(ret=1); d-=n; while(n!=d, ret<<=1; if(n>d, n-=d;ret++, d-=n)); ret+1; \\ Kevin Ryde, Nov 11 2020