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