A358298 Array read by antidiagonals: T(n,k) (n>=0, k>=0) = number of lines defining the Farey diagram Farey(n,k) of order (n,k).

2, 3, 3, 4, 6, 4, 6, 11, 11, 6, 8, 19, 20, 19, 8, 12, 29, 36, 36, 29, 12, 14, 43, 52, 60, 52, 43, 14, 20, 57, 78, 88, 88, 78, 57, 20, 24, 77, 100, 128, 124, 128, 100, 77, 24, 30, 97, 136, 162, 180, 180, 162, 136, 97, 30, 34, 121, 166, 216, 224, 252, 224, 216, 166, 121, 34

Offset: 0

Author

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

Keywords

• nonn
• tabl

Comments

We work with lines with equation ux + vy + w = 0 in the (x,y) plane.

This line has slope -u/v, and crosses the vertical y axis at the intercept point y = -w/v

For the Farey diagram Farey(m,n), u is an integer between -(m-1) and +(m-1), v is between -(n-1) and +(n-1) and w can be any integer.

The only lines that are used are those that hit the unit square 0 <= x <= 1, 0 <= y <= 1 in at least two points.

This means that we only need to look at w's with |w| <= |u| + |v|.

T(m,n) is the number of such lines.

For illustrations of Farey(3,3) and Farey(3,4) see Khoshnoudirad (2015), Fig. 2, and Darat et al. (2009), Fig. 2. For further illustrations see A358882-A358885.

Examples

			The full array T(n,k), n >= 0, k>= 0, begins:
  2, 3, 4, 6, 8, 12, 14, 20, 24, 30, 34, 44, 48, 60,  ...
  3, 6, 11, 19, 29, 43, 57, 77, 97, 121, 145, 177, 205,  ...
  4, 11, 20, 36, 52, 78, 100, 136, 166, 210, 246, 302,  ...
  6, 19, 36, 60, 88, 128, 162, 216, 266, 326, 386, 468, ...
  8, 29, 52, 88, 124, 180, 224, 298, 360, 444, 518, 628, ...
  12, 43, 78, 128, 180, 252, 316, 412, 498, 608, 706,  ...
  14, 57, 100, 162, 224, 316, 388, 508, 608, 738, 852, ...
  ...
		

Links

• Alain Daurat, M. Tajine, and 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; doi:10.2298/AADM150219008K. See Theorem 1, |DF(m,n)|.

Crossrefs

Cf. A358299.

Row 0 is essentially A225531, row 1 is A358300, main diagonal is A358301.

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.

Programs

Maple

A005728 := proc(n) 1+add(numtheory[phi](i), i=1..n) ; end proc: # called F_n in the paper
Amn:=proc(m,n) local a,i,j;  # A331781 or equally A333295. Diagonal is A018805.
a:=0; for i from 1 to m do for j from 1 to n do
if igcd(i,j)=1 then a:=a+1; fi; od: od: a; end;
# The present sequence is:
Dmn:=proc(m,n) local d,t1,u,v,a; global A005728, Amn;
a:=A005728(m)+A005728(n);
t1:=0; for u from 1 to m do for v from 1 to n do
d:=igcd(u,v); if d>=1 then t1:=t1 + (u+v)*numtheory[phi](d)/d; fi; od: od:
a+2*t1-2*Amn(m,n); end;
for m from 1 to 8 do lprint([seq(Dmn(m,n),n=1..20)]); od:

Mathematica

A005728[n_] := 1 + Sum[EulerPhi[i], {i, 1, n}];
Amn[m_, n_] := Module[{a, i, j}, a = 0; For[i = 1, i <= m, i++, For[j = 1, j <= n, j++, If[GCD[i, j] == 1, a = a + 1]]]; a];
Dmn[m_, n_] := Module[{d, t1, u, v, a}, a = A005728[m] + A005728[n]; t1 = 0; For[u = 1, u <= m, u++, For[v = 1, v <= n, v++, d = GCD[u, v]; If[d >= 1 , t1 = t1 + (u + v)* EulerPhi[d]/d]]]; a + 2*t1 - 2*Amn[m, n]];
Table[Dmn[m - n, n], {m, 0, 10}, {n, 0, m}] // Flatten (* Jean-François Alcover, Apr 03 2023, after Maple code *)