A006843 -id:A006843 - cp's OEIS frontend

A007305 Numerators of Farey (or Stern-Brocot) tree fractions.

0, 1, 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 5, 4, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11, 10, 11, 9, 6, 1, 2, 3, 3, 4, 5, 5, 4, 5, 7, 8, 7, 7, 8, 7, 5, 6, 9, 11, 10, 11, 13, 12, 9, 9, 12, 13, 11

Offset: 0

N. J. A. Sloane

From Yosu Yurramendi, Jun 25 2014: (Start)
If the terms (n>0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
   1,
   1,2,
   1,2,3,3,
   1,2,3,3,4,5,5,4,
   1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,
   1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,
then the sum of the m-th row is 3^m (m = 0,1,2,), each column k is constant, and the constants are from A007306, denominators of Farey (or Stern-Brocot) tree fractions (see formula).
If the rows are written in a right-aligned fashion:
                                                                          1,
                                                                        1,2,
                                                                   1, 2,3,3,
                                                       1, 2, 3, 3, 4, 5,5,4,
                                  1,2, 3, 3, 4, 5, 5,4,5, 7, 8, 7, 7, 8,7,5,
  1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,
then each column is an arithmetic sequence. The differences of the arithmetic sequences also give the sequence A007306 (see formula). The first terms of columns are from A007305 itself (a(A004761(n+1)) = a(n), n>0), and the second ones from A049448 (a(A004761(n+1)+2^A070941(n)) = A049448(n), n>0). (End)
If the sequence is considered in blocks of length 2^m, m = 0,1,2,..., the blocks are the reverse of the blocks of A047679: (a(2^m+1+k) = A047679(2^(m+1)-2-k), m = 0,1,2,..., k = 0,1,2,...,2^m-1). - Yosu Yurramendi, Jun 30 2014

			A007305/A007306 = [ 0/1; 1/1; ] 1/2; 1/3, 2/3; 1/4, 2/5, 3/5, 3/4; 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, ...
Another version of Stern-Brocot is A007305/A047679 = 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5, 5, 1/5, 5/4, 4/5, ...

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 117.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..4096
A. Bogomolny, Stern-Brocot Tree
A. Bogomolny, Inspiration for Maple code
A. Brocot, Calcul des rouages par approximation, nouvelle méthode, Revue Chonométrique 3, 186-194, 1861.
G. A. Jones, The Farey graph, Séminaire Lotharingien de Combinatoire, B18e (1987), 2 pp.
Shin-ichi Katayama, Modified Farey trees and Pythagorean triples, Journal of mathematics, the University of Tokushima, 47, 2013.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
Hugo Pfoertner, Ratio A007305(n)/A007306(n) vs n, using Plot 2.
N. J. A. Sloane, Stern-Brocot or Farey Tree
Noam Zimhoni, A forest of Eisensteinian triplets, arXiv:1904.11782 [math.NT], 2019.
Index entries for fraction trees
Index entries for sequences related to Stern's sequences

Cf. A007306, A006842, A006843, A047679, A054424, A057114, A152975.

A007305 := proc(n) local b; b := proc(n) option remember; local msb, r;
if n < 3 then return 1 fi; msb := ilog2(n); r := n - 2^msb;
if ilog2(r) = msb - 1 then b(r) + b(3*2^(msb-1) - r - 1) else b(2^(msb - 1) + r) fi end: if n = 0 then 0 else b(n-1) fi end: # Antti Karttunen, Mar 19 2000 [Corrected and rewritten by Peter Luschny, Apr 24 2024]
seq(A007305(n), n = 0..92);

sbt[n_] := Module[{R,L,Y}, R={{1,0},{1,1}}; L={{1,1},{0,1}}; Y={{1,0},{0,1}}; w[b_] := Fold[ #1.If[ #2 == 0,L,R] &,Y,b]; u[a_] := {a[[2,1]]+a[[2,2]],a[[1,1]]+a[[1,2]]}; Map[u,Map[w,Tuples[{0,1},n]]]]
A007305(n) = Flatten[Append[{0,1},Table[Map[First,sbt[i]],{i,0,5}]]]
A047679(n) = Flatten[Table[Map[Last,sbt[i]],{i,0,5}]]
(* Peter Luschny, Apr 27 2009 *)

a <- 1
for(m in 1:6) for(k in 0:(2^(m-1)-1)) {
  a[2^m+        k] <- a[2^(m-1)+k]
  a[2^m+2^(m-1)+k] <- a[2^(m-1)+k] + a[2^m-k-1]
}
a
# Yosu Yurramendi, Jun 25 2014

a(n) = SternBrocotTreeNum(n-1) # n starting from 2 gives the sequence from 1, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 5, 5, 4, 1, ...
From Reinhard Zumkeller, Dec 22 2008: (Start)
For n > 1: a(n+2) = if A025480(n-1) != 0 and A025480(n) != 0 then a(A025480(n-1)+2) + a(A025480(n)+2) else if A025480(n)=0 then a(A025480(n-1)+2)+1 else 0 + a(A025480(n-1)+2).
a(A054429(n)+2) = A047679(n).
a(n+2) = A047679(A054429(n)).
A153036(n+1) = floor(a(n+2)/A047679(n)). (End)
From Yosu Yurramendi, Jun 25 2014: (Start)
For m = 1,2,3,..., and k = 0,1,2,...,2^(m-1)-1, with a(1)=1:
a(2^m+k) = a(2^(m-1)+k);
a(2^m+2^(m-1)+k) = a(2^(m-1)+k) + a(2^m-k-1). (End)
a(2^(m+2)-k) = A007306(2^(m+1)-k), m=0,1,2,..., k=0,1,2,...,2^m-1. - Yosu Yurramendi, Jul 04 2014
a(2^(m+1)+2^m+k) - a(2^m+k) = A007306(2^m-k+1), m=1,2,..., k=1,2,...,2^(m-1). - Yosu Yurramendi, Jul 05 2014
From Yosu Yurramendi, Jan 01 2015: (Start)
a(2^m+2^q-1) = q+1, q = 0, 1, 2,..., m = q, q+1, q+2,...
a(2^m+2^q)   = q+2, q = 0, 1, 2,..., m = q+1, q+2, q+3,... (End)
a(2^m+k) = A007306(k+1), m >= 0, 0 <= k < 2*m.  - Yosu Yurramendi, May 20 2019
a(n) = A002487(A059893(n)), n > 0. - Yosu Yurramendi, Sep 29 2021

A006842 Triangle read by rows: row n gives numerators of Farey series of order n.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 1, 2, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 3, 4, 1, 0, 1, 1, 1, 1, 2, 1, 3, 2, 3, 4, 5, 1, 0, 1, 1, 1, 1, 2, 1, 2, 3, 1, 4, 3, 2, 5, 3, 4, 5, 6, 1, 0, 1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 5, 6, 7, 1, 0, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 3, 4, 1, 5, 4, 3, 5, 2, 5, 3, 7, 4, 5, 6, 7, 8, 1

Offset: 1

N. J. A. Sloane

			0/1, 1/1;
0/1, 1/2, 1/1;
0/1, 1/3, 1/2, 2/3, 1/1;
0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1;
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1;
... = A006842/A006843

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964
J. H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 152.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923. See Vol. 1.
Guthery, Scott B. A motif of mathematics. Docent Press, 2011.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 23.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
A. O. Matveev, Farey Sequences, De Gruyter, 2017.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 141.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..10563
Maxim Bruckheimer and Abraham Arcavi, Farey series and Pick’s area theorem, The Mathematical Intelligencer, 17.4 (1995): 64-67.
Cristian Cobeli and Alexandru Zaharescu, The Haros-Farey sequence at two hundred years, Acta Univ. Apulensis Math. Inform 5 (2003): 1-38.
Andrey O. Matveev, Neighboring Fractions in Farey Subsequences, arXiv:0801.1981 [math.NT], 2008-2010.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
N. J. A. Sloane, Stern-Brocot or Farey Tree
Eric Weisstein's World of Mathematics, Farey Sequence.
Index entries for sequences related to Stern's sequences

Row n has A005728(n) terms. - Michel Marcus, Jun 27 2014

Cf. A006843 (denominators), A049455, A049456, A007305, A007306. Also A177405/A177407.

Farey := proc(n) sort(convert(`union`({0},{seq(seq(m/k,m=1..k),k=1..n)}),list)) end: seq(numer(Farey(i)),i=1..5); # Peter Luschny, Apr 28 2009

Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Flatten[ Table[ Numerator[ Farey[n]], {n, 0, 9}]] (* Robert G. Wilson v, Apr 08 2004 *)
Table[FareySequence[n] // Numerator, {n, 1, 9}] // Flatten (* Jean-François Alcover, Sep 25 2018 *)

row(n) = {vf = [0]; for (k=1, n, for (m=1, k, vf = concat(vf, m/k););); vf = vecsort(Set(vf)); for (i=1, #vf, print1(numerator(vf[i]), ", "));} \\ Michel Marcus, Jun 27 2014

More terms from Robert G. Wilson v, Apr 08 2004

A049456 Triangle T(n,k) = denominator of fraction in k-th term of n-th row of variant of Farey series. This is also Stern's diatomic array read by rows (version 1).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 2, 3, 1, 1, 4, 3, 5, 2, 5, 3, 4, 1, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13

Offset: 1

N. J. A. Sloane

Row n has length 2^(n-1) + 1.
A049455/a(n) gives another version of the Stern-Brocot tree.
Define mediant of a/b and c/d to be (a+c)/(b+d). We get A006842/A006843 if we omit terms from n-th row in which denominator exceeds n.
Largest term of n-th row = A000045(n+1), Fibonacci numbers. - Reinhard Zumkeller, Apr 02 2014

			0/1, 1/1; 0/1, 1/2, 1/1; 0/1, 1/3, 1/2, 2/3, 1/1; 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1; 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, ... = A049455/A049456
Array begins
1...............................1
1...............2...............1
1.......3.......2.......3.......1
1...4...3...5...2...5...3...4...1
1.5.4.7.3.8.5.7.2.7.5.8.3.7.4.5.1
.................................

J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

Reinhard Zumkeller, Rows n = 1..13 of table, flattened
C. Giuli and R. Giuli, A primer on Stern's diatomic sequence, Fib. Quart., 17 (1979), 103-108, 246-248 and 318-320 (but beware errors).
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(2) 1929, pp. 59-67.
D. H. Lehmer, On Stern's Diatomic Series, Amer. Math. Monthly 36(1) 1929, pp. 59-67. [Annotated and corrected scanned copy]
M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for sequences related to Stern's sequences

Coincides with A002487 if pairs of adjacent 1's are replaced by single 1's.
Cf. A049455, A007305, A007306, A006842, A006843, A064881-A064886, A070878, A070879.
Cf. A000051 (row lengths), A034472 (row sums), A293160 (distinct terms in each row).

import Data.List (transpose)
a049456 n k = a049456_tabf !! (n-1) !! (k-1)
a049456_row n = a049456_tabf !! (n-1)
a049456_tabf = iterate
   (\row -> concat $ transpose [row, zipWith (+) row $ tail row]) [1, 1]
-- Reinhard Zumkeller, Apr 02 2014

A049456 := proc(n,k)
    option remember;
    if n =1 then
        if k >= 0 and k <=1 then
            1;
        else
            0 ;
        end if;
    elif type(k,'even') then
        procname(n-1,k/2) ;
    else
        procname(n-1,(k+1)/2)+procname(n-1,(k-1)/2) ;
    end if;
end proc: # R. J. Mathar, Dec 12 2014

Flatten[NestList[Riffle[#,Total/@Partition[#,2,1]]&,{1,1},10]] (* Harvey P. Dale, Mar 16 2013 *)

Each row is obtained by copying the previous row but interpolating the sums of pairs of adjacent terms. E.g. after 1 2 1 we get 1 1+2 2 2+1 1.

Row 1 of Farey tree is 0/1, 1/1. Obtain row n from row n-1 by inserting mediants between each pair of terms.

A049691 a(n)=T(n,n), array T as in A049687. Also a(n)=T(2n,2n), array T given by A049639.

Original entry on oeis.org

0, 3, 5, 9, 13, 21, 25, 37, 45, 57, 65, 85, 93, 117, 129, 145, 161, 193, 205, 241, 257, 281, 301, 345, 361, 401, 425, 461, 485, 541, 557, 617, 649, 689, 721, 769, 793, 865, 901, 949, 981, 1061, 1085, 1169, 1209, 1257, 1301, 1393, 1425, 1509, 1549

Offset: 0

Clark Kimberling

nonn

a(n) is related to the sequence b(n) = |{(x, y): gcd(x, y) = 1, 1<=x, y<=n}| (A018805) as follows: a(n) = b(n - 1) + 2 (for n > 1). - Shawn Westmoreland (westmore(AT)math.utexas.edu), Jun 11 2003
Comment from N. J. A. Sloane, Sep 08 2019 (Start)
The above comment can be rephrased as saying that a(n) is the cardinality of the subsequence F(B(2n),n) of the Farey series F_{2n} that is extensively studied in Matveev (2017). See the definition on page 1.
For example, F(B(2),1), F(B(4),2), F(B(6),3), and F(B(8),4) are:
  [0, 1/2, 1],
  [0, 1/3, 1/2, 2/3, 1],
  [0, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1],
  [0, 1/5, 1/4, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 3/4, 4/5, 1],
of cardinalities 3,5,9,13 respectively. See also A324796/A324797. (End)
a(n) is the number of visible points on an n X n square lattice when viewed from (0, 0), (0, n), (n, 0), or (n, n). - Torlach Rush, Nov 16 2020
Also number of elements in { c/d ; -d <= c <= d <= n }, i.e., distinct fractions with denominator not exceeding n and absolute value of numerator not exceeding the denominator. - M. F. Hasler, Mar 26 2023

A. O. Matveev, Farey Sequences, De Gruyter, 2017.

Andrew Howroyd, Table of n, a(n) for n = 0..1000
A. O. Matveev, Farey Sequences: Errata + Haskell code
Eric Weisstein's World of Mathematics, Visible Point

Cf. A000010, A018805, A049687, A324796, A324797.

A206297 is an essentially identical sequence.

Farey := proc(n) sort(convert(`union`({0}, {seq(seq(m/k, m=1..k), k=1..n)}), list)) end: # A006842/A006843
BF := proc(m) local a,i,h,k; global Farey; a:=[];
for i in Farey(2*m) do h:=numer(i); k:=denom(i);
if (h <= m) and (k-m <= h) then a:=[op(a),i]; fi; od: a; end;
[seq(nops(BF(m),m=1..20)]; # this sequence - N. J. A. Sloane, Sep 08 2019

a[0] = 0; a[n_] := 2 + Sum[Quotient[n, g]^2*MoebiusMu[g], {g, 1, n}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Oct 07 2017, translated from PARI *)

a(n) = if(n>0, 2, 0) + sum(g=1, n, (n\g)^2 * moebius(g)); \\ Andrew Howroyd, Sep 17 2017

a(n) = if(n>0, 1, 0) + 2 * sum(k=1, n, eulerphi(k)); \\ Torlach Rush, Nov 24 2020

a(n)=#Set(concat([[c/d|c<-[-d..d],d]|d<-[0..n]])) \\ For illustrative purpose only! - M. F. Hasler, Mar 26 2023

from functools import lru_cache
@lru_cache(maxsize=None)
def A049691(n):
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(A049691(k1)-2)
        j, k1 = j2, n//j2
    return n*(n-1)-c+j+2 # Chai Wah Wu, Aug 04 2024

a(n) = A206297(n+1) = 2 + A018805(n) for n > 0. - Andrew Howroyd, Sep 17 2017

a(n) = 1 + 2 * Sum{k=1..n} A000010(k), n > 0. - Torlach Rush, Nov 24 2020

Terms a(41) and beyond from Andrew Howroyd, Sep 17 2017

A358882 The number of regions in a Farey diagram of order (n,n).

Original entry on oeis.org

4, 56, 504, 2024, 8064, 18200, 50736, 99248, 202688, 343256, 657904, 983008, 1708672, 2485968, 3755184, 5289944, 8069736, 10539792, 15387320, 19913840

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Dec 05 2022

See A358298 and also the linked references for further details.

The first diagram where not all edge points are connected is n = 3. For example a line connecting points (0,1/3) and (1/3,0) has equation 3*y - 6*x - 1 = 0, and as one of the x or y coefficients is greater than n (3 in this case) the line is not included.

Alain Daurat, M. Tajine, M. Zouaoui, About the frequencies of some patterns in digital planes. Application to area estimators. Computers & Graphics. 33.1 (2009), 11-20.
Daniel Khoshnoudirad, Farey lines defining Farey diagrams and application to some discrete structures. Applicable Analysis and Discrete Mathematics. 9 (2015), 73-84.
Scott R. Shannon, Image for n = 1.
Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 7.
Scott R. Shannon, Image for n = 8.
Wikipedia, Farey sequence.

Cf. A358883 (vertices), A358884 (edges), A358885 (k-gons), A006842, A006843, A005728, A358886.
See A358298 for definition of Farey diagram Farey(m,n).
The Farey Diagrams Farey(m,n) are studied in A358298-A358307 and A358882-A358885, the Completed Farey Diagrams of order (m,n) in A358886-A358889.

a(n) = A358884(n) - A358883(n) + 1 by Euler's formula.

A358885 Table read by rows: T(n,k) = the number of regions with k sides, k >= 3, in a Farey diagram of order (n,n).

Original entry on oeis.org

4, 48, 8, 400, 104, 1568, 456, 6216, 1848, 13944, 4256, 38760, 11976, 75768, 23480, 154440, 48248, 261072, 82184, 500464, 157440, 747480, 235528, 1298584, 410088, 1890184, 595784, 2853416, 901768, 4015552, 1274392, 6127632, 1942104, 8002552, 2537240, 11683880, 3703440, 15123800, 4790040

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Dec 05 2022

See the linked references for further details.
The first diagram where not all edge points are connected is n = 3. For example a line connecting points (0,1/3) and (1/3,0) has equation 3*y - 6*x - 1 = 0, and as one of the x or y coefficients is greater than n (3 in this case) the line is not included.
It would be nice to have a proof (or disproof) that the number of sides is always 3 or 4.

			The table begins:
4;
48, 8;
400, 104;
1568, 456;
6216, 1848;
13944, 4256;
38760, 11976;
75768, 23480;
154440, 48248;
261072, 82184;
500464, 157440;
747480, 235528;
1298584, 410088;
1890184, 595784;
2853416, 901768;
4015552, 1274392;
6127632, 1942104;
8002552, 2537240;
11683880, 3703440;
15123800, 4790040;
.
.

Alain Daurat et al., About the frequencies of some patterns in digital planes. Application to area estimators. Computers & graphics. 33.1 (2009), 11-20.
Daniel Khoshnoudirad, Farey lines defining Farey diagrams and application to some discrete structures. Applicable Analysis and Discrete Mathematics. 9 (2015), 73-84.
Scott R. Shannon, Image for n = 5.
Wikipedia, Farey sequence.

Cf.  A358882 (regions), A358883 (vertices), A358884 (edges), A006842, A006843, A005728, A358889.
See A358298 for definition of Farey diagram Farey(m,n).
The Farey Diagrams Farey(m,n) are studied in A358298-A358307 and A358882-A358885, the Completed Farey Diagrams of order (m,n) in A358886-A358889.

Sum of row n = A358882(n).

A049455 Triangle read by rows: T(n,k) = numerator of fraction in k-th term of n-th row of variant of Farey series.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9

Offset: 1

N. J. A. Sloane

Stern's diatomic array read by rows (version 4, the 0,1 version).
This sequence divided by A049456 gives another version of the Stern-Brocot tree.
Row n has length 2^n + 1.
Define mediant of a/b and c/d to be (a+c)/(b+d). We get A006842/A006843 if we omit terms from n-th row in which denominator exceeds n.
Largest term of n-th row = A000045(n), Fibonacci numbers. - Reinhard Zumkeller, Apr 02 2014

			0/1, 1/1; 0/1, 1/2, 1/1; 0/1, 1/3, 1/2, 2/3, 1/1; 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1; 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, ... = A049455/A049456
The 0,1 version of Stern's diatomic array (cf. A002487) begins:
0,1,
0,1,1,
0,1,1,2,1,
0,1,1,2,1,3,2,3,1,
0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,
0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,3,3,7,4,5,1,
...

Martin Gardner, Colossal Book of Mathematics, Classic Puzzles, Paradoxes, and Problems, Chapter 25, Aleph-Null and Aleph-One, p. 328, W. W. Norton & Company, NY, 2001.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 8204 terms from Reinhard Zumkeller)
C. Giuli and R. Giuli, A primer on Stern's diatomic sequence, Fib. Quart., 17 (1979), 103-108, 246-248 and 318-320 (but beware errors).
Jennifer Lansing, Largest Values for the Stern Sequence, J. Integer Seqs., 17 (2014), #14.7.5.
M. Shrader-Frechette, Modified Farey sequences and continued fractions, Math. Mag., 54 (1981), 60-63.
N. J. A. Sloane, Stern-Brocot or Farey Tree
Index entries for sequences related to Stern's sequences

Cf. A049456. Also A007305, A007306, A006842, A006843, A070878, A070879.
Row sums are A007051.
Cf. A000051 (row lengths), A293165 (distinct terms).

import Data.List (transpose)
import Data.Ratio ((%), numerator, denominator)
a049455 n k = a049455_tabf !! (n-1) !! (k-1)
a049455_row n = a049455_tabf !! (n-1)
a049455_tabf = map (map numerator) $ iterate
   (\row -> concat $ transpose [row, zipWith (+/+) row $ tail row]) [0, 1]
   where u +/+ v = (numerator u + numerator v) %
                   (denominator u + denominator v)
-- Reinhard Zumkeller, Apr 02 2014

f[l_List] := Block[{k = Length@l, j = l}, While[k > 1, j = Insert[j, j[[k]] + j[[k - 1]], k]; k--]; j]; NestList[f, {0, 1}, 6] // Flatten (* Robert G. Wilson v, Nov 10 2019 *)

mediant(x, y) = (numerator(x)+numerator(y))/(denominator(x)+denominator(y));
newrow(rowa) = {my(rowb = []); for (i=1, #rowa-1, rowb = concat(rowb, rowa[i]); rowb = concat(rowb, mediant(rowa[i], rowa[i+1]));); concat(rowb, rowa[#rowa]);}
rows(nn) = {my(rowa); for (n=1, nn, if (n==1, rowa = [0, 1], rowa = newrow(rowa)); print(apply(x->numerator(x), rowa)););} \\ Michel Marcus, Apr 03 2019

Row 1 is 0/1, 1/1. Obtain row n from row n-1 by inserting mediants between each pair of terms.

More terms from Larry Reeves (larryr(AT)acm.org), Apr 12 2000

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.

Original entry on oeis.org

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

Clark Kimberling

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

			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;
  ...

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

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

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

Cf. A006842, A006843.

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 *)

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

A359690 Number of vertices in a regular drawing of a complete bipartite graph where the vertex positions on each part equal the Farey series of order n.

Original entry on oeis.org

5, 13, 69, 289, 1971, 3997, 20371, 45751, 120957, 205299, 629847, 897801, 2334409, 3461459, 5517131, 8468061

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Jan 11 2023

The number of vertices along each edge is A005728(n). No formula for a(n) is known.

Scott R. Shannon, Image for n = 1.
Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 7.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Wikipedia, Farey sequence.

Cf. A359691 (crossings), A359692 (regions), A359693 (edges), A359694 (k-gons), A005728, A331755, A359654, A358887, A358883, A006842, A006843.

a(n) = A359693(n) - A359692(n) + 1 by Euler's formula.

A358883 The number of vertices in a Farey diagram of order (n,n).

Original entry on oeis.org

5, 37, 313, 1253, 4977, 11253, 31393, 61409, 125525, 212785, 407757, 609361, 1059497, 1541005, 2328621, 3282329, 5006113, 6538721, 9545621, 12352197

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Dec 05 2022

See the linked references for further details.

Alain Daurat et al., About the frequencies of some patterns in digital planes. Application to area estimators. Computers & graphics. 33.1 (2009), 11-20.
Daniel Khoshnoudirad, Farey lines defining Farey diagrams and application to some discrete structures. Applicable Analysis and Discrete Mathematics. 9 (2015), 73-84.
Scott R. Shannon, Image for n = 1.
Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Wikipedia, Farey sequence.

Cf. A358882 (regions), A358884 (edges), A358885 (k-gons), A006842, A006843, A005728, A358887.
See A358298 for definition of Farey diagram Farey(m,n).
The Farey Diagrams Farey(m,n) are studied in A358298-A358307 and A358882-A358885, the Completed Farey Diagrams of order (m,n) in A358886-A358889.

a(n) = A358884(n) - A358882(n) + 1 by Euler's formula.

cp's OEIS Frontend

A007305 Numerators of Farey (or Stern-Brocot) tree fractions.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

R

Formula

A006842 Triangle read by rows: row n gives numerators of Farey series of order n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A049456 Triangle T(n,k) = denominator of fraction in k-th term of n-th row of variant of Farey series. This is also Stern's diatomic array read by rows (version 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A049691 a(n)=T(n,n), array T as in A049687. Also a(n)=T(2n,2n), array T given by A049639.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A358882 The number of regions in a Farey diagram of order (n,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A358885 Table read by rows: T(n,k) = the number of regions with k sides, k >= 3, in a Farey diagram of order (n,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A049455 Triangle read by rows: T(n,k) = numerator of fraction in k-th term of n-th row of variant of Farey series.

Views

Author

Keywords