cp's OEIS Frontend

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.

%I A338579 #14 Nov 17 2020 14:21:56
%S A338579 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,
%T A338579 128,129,18,3,24,25,4,31,256,257,9,20,6,2,7,29,16,512,513,34,19,21,48,
%U A338579 49,28,30,63,1024,1025,17,5,3,23,2,26,4,8,32,2048
%N 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.
%C A338579 Fractions are reduced to lowest terms.
%H A338579 Hugo Pfoertner, <a href="/A338579/b338579.txt">Table of n, a(n) for n = 2..1226</a>, rows 2..50, flattened.
%e A338579 The triangle begins
%e A338579      N     1   2  3  4  5  6   7   8   9   10   11   12   13    14    15
%e A338579    D \------------------------------------------------------------------
%e A338579    2 |     2   .  .  .  .  .   .   .   .    .    .    .    .     .     .
%e A338579    3 |     3   4  .  .  .  .   .   .   .    .    .    .    .     .     .
%e A338579    4 |     5   2  8  .  .  .   .   .   .    .    .    .    .     .     .
%e A338579    5 |     9   6  7 16  .  .   .   .   .    .    .    .    .     .     .
%e A338579    6 |    17   3  2  4 32  .   .   .   .    .    .    .    .     .     .
%e A338579    7 |    33  10 12 13 15 64   .   .   .    .    .    .    .     .     .
%e A338579    8 |    65   5 11  2 14  8 128   .   .    .    .    .    .     .     .
%e A338579    9 |   129  18  3 24 25  4  31 256   .    .    .    .    .     .     .
%e A338579   10 |   257   9 20  6  2  7  29  16 512    .    .    .    .     .     .
%e A338579   11 |   513  34 19 21 48 49  28  30  63 1024    .    .    .     .     .
%e A338579   12 |  1025  17  5  3 23  2  26   4   8   32 2048    .    .     .     .
%e A338579   13 |  2049  66 36 40 22 96  97  27  57   61  127 4096    .     .     .
%e A338579   14 |  4097  33 35 10 41 12   2  13  56   15   62   64 8192     .     .
%e A338579   15 |  8193 130  9 37  3  6 192 193   7    4   60   16  255 16384     .
%e A338579   16 | 16385  65 68  5 80 11  47   2  50   14  113    8  125   128 32768
%e A338579 .
%e A338579 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.
%e A338579 T(14,4) = T(7,2) = 10, because the fraction 4/14 reduced to lowest terms is 2/7.
%e A338579 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.
%o A338579 (PARI) \\ using _Yosu Yurramendi_'s formulas
%o A338579 a338579(lim)={
%o A338579 my(a7305=vectorsmall(2+2^(lim+2)),a7306=vectorsmall(2+2^(lim+2)));
%o A338579   a7305[1]=1;
%o A338579   for(m=1,lim,
%o A338579      for(k=0,2^(m-1)-1,
%o A338579       a7305[2^m+k]=a7305[2^(m-1)+k];
%o A338579       a7305[2^m+2^(m-1)+k]=a7305[2^(m-1)+k]+a7305[2^m-k-1]
%o A338579      )
%o A338579   );
%o A338579   a7306[1]=1;a7306[2]=2;
%o A338579   for(m=0,lim,
%o A338579      for(k=1,2^m,
%o A338579       a7306[2^(m+1)+k]=a7306[2^m+k] + a7306[k];
%o A338579       a7306[2^(m+1)-k+1]=a7306[2^m+k]
%o A338579      )
%o A338579   );
%o A338579    my(findinFS(x)=for(k=2,#a7306,
%o A338579       if(!(a7305[k-1]/a7306[k]-x),return(k)));0);
%o A338579   for(de=2,lim+2,for(nu=1,de-1,my(q=nu/de);print1(findinFS(q),", ")))
%o A338579 };
%o A338579 a338579(10);
%o A338579 (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
%Y A338579 Cf. A007305, A007306, A054424, A054425.
%K A338579 nonn,tabl
%O A338579 2,1
%A A338579 _Hugo Pfoertner_, Nov 10 2020