A006842 -id:A006842 - cp's OEIS frontend

A358886 Number of regions formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

4, 56, 1040, 6064, 53104, 115496, 629920, 1457744, 3952264, 6835568

Offset: 1

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

The number of points along each edge is given by A005728(n).

We call this graph the Completed Farey Diagram of order (n,k). The (ordinary) Farey diagram Farey(n,k) is a subgraph. In the latter graph, not all pairs of boundary points are joined by lines.

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.
Wikipedia, Farey sequence.

Cf. A358888 (edges), A358887 (vertices), A358889 (k-gons), A006842, A006843, A005728, A358882.

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) = A358888(n) - A358887(n) + 1 by Euler's formula.

A358889 Table read by rows: T(n,k) = number of k-gons, k >= 3, formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,m)/A006843(n,m), m = 1..A005728(n).

Original entry on oeis.org

4, 48, 8, 712, 304, 24, 3368, 2400, 280, 16, 27424, 20360, 4784, 504, 32, 56000, 47088, 10912, 1400, 88, 8, 292424, 255608, 69368, 11504, 960, 56, 658800, 590208, 175856, 30160, 2496, 200, 24, 1748112, 1593912, 506496, 93584, 9616, 520, 24, 2981448, 2778456, 890368, 166912, 17192, 1144, 48

Offset: 1

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

The number of points along each edge is given by A005728(n).

			The table begins:
 4;
 48,      8;
 712,     304,     24;
 3368,    2400,    280,    16;
 27424,   20360,   4784,   504,    32;
 56000,   47088,   10912,  1400,   88,    8;
 292424,  255608,  69368,  11504,  960,   56;
 658800,  590208,  175856, 30160,  2496,  200,  24;
 1748112, 1593912, 506496, 93584,  9616,  520,  24;
 2981448, 2778456, 890368, 166912, 17192, 1144, 48;
.
.

Scott R. Shannon, Image for n = 5.
Wikipedia, Farey sequence.

Cf. A358886 (regions), A358887 (vertices), A358888 (edges), A006842, A006843, A005728, A358885.

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 = A358886(n).

A358887 Number of vertices formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Original entry on oeis.org

5, 37, 705, 4549, 42357, 94525, 531485, 1250681, 3440621, 5985201

Offset: 1

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

The number of points along each edge is given by A005728(n).

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.
Wikipedia, Farey sequence.

Cf. A358888 (edges), A358886 (regions), A358889 (k-gons), A006842, A006843, A005728, A358882, A358883.

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) = A358888(n) - A358886(n) + 1 by Euler's formula.

A358888 Number of edges formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Original entry on oeis.org

8, 92, 1744, 10612, 95460, 210020, 1161404, 2708424, 7392884, 12820768

Offset: 1

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

The number of points along each edge is given by A005728(n).

See A358886 and A358887 for images of the square.

Wikipedia, Farey sequence.

Cf. A358886 (regions), A358887 (vertices), A358889 (k-gons), A006842, A006843, A005728, A358882, A358884.

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) = A358886(n) + A358887(n) - 1 by Euler's formula.

A358948 Number of regions formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Original entry on oeis.org

1, 12, 228, 1464, 12516, 29022, 153564, 364650, 996672, 1750326, 5274156, 7761498

Offset: 1

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

The number of points along each edge is given by A005728(n).

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.
N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: Video, Slides, Updates. (Mentions this sequence.)
Wikipedia, Farey sequence.

Cf. A358949 (vertices), A358950 (edges), A358951 (k-gons), A358886, A006842, A006843, A005728, A358882.

a(n) = A358950(n) - A358949(n) + 1 by Euler's formula.

A358949 Number of vertices formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Original entry on oeis.org

3, 10, 148, 1111, 9568, 23770, 126187, 308401, 855145, 1521733, 4591405, 6831040

Offset: 1

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

The number of points along each edge is given by A005728(n).

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.
N. J. A. Sloane, New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences, Doron Zeilberger's Exper. Math. Seminar, Rutgers, Sep 14 2023: Video, Slides, Updates. (Mentions this sequence.)
Wikipedia, Farey sequence.

Cf. A358948 (regions), A358950 (edges), A358951 (k-gons), A358887, A006842, A006843, A005728, A358882.

a(n) = A358950(n) - A358948(n) + 1 by Euler's formula.

A358951 Irregular table read by rows: T(n,k) = number of k-gons, k >= 3, formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,m)/A006843(n,m), m = 1..A005728(n).

Original entry on oeis.org

1, 12, 180, 42, 6, 810, 576, 72, 6, 6786, 4932, 744, 48, 6, 13662, 12522, 2568, 258, 12, 72582, 64932, 14376, 1632, 36, 6, 164484, 155088, 38688, 5958, 414, 18, 439524, 422370, 114804, 18462, 1392, 120, 750108, 749928, 211518, 35226, 3336, 204, 6, 2265462, 2240994, 647184, 109602, 10230, 666, 18

Offset: 1

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

The number of points along each edge is given by A005728(n).

			The table begins:
1;
12;
180, 42, 6;
810, 576, 72, 6;
6786, 4932, 744, 48, 6;
13662, 12522, 2568, 258, 12;
72582, 64932, 14376, 1632, 36, 6;
164484, 155088, 38688, 5958, 414, 18;
439524, 422370, 114804, 18462, 1392, 120;
750108, 749928, 211518, 35226, 3336, 204, 6;
2265462, 2240994, 647184, 109602, 10230, 666, 18;
3263436, 3312270, 990072, 176172, 18294, 1188, 66;
.
.

Scott R. Shannon, Image for n = 7.
Wikipedia, Farey sequence.

Cf. A358948 (regions), A358949 (vertices), A358950 (edges), A358889, A006842, A006843, A005728, A358882.

Sum of row n = A358948(n).

A358950 Number of edges formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Original entry on oeis.org

3, 21, 375, 2574, 22083, 52791, 279750, 673050, 1851816, 3272058, 9865560, 14592537

Offset: 1

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

The number of points along each edge is given by A005728(n).

See A358948 and A358949 for images of the square.

Wikipedia, Farey sequence.

Cf. A358948 (regions), A358949 (vertices), A358951 (k-gons), A358888, A006842, A006843, A005728, A358882.

a(n) = A358948(n) + A358949(n) - 1 by Euler's formula.

A308483 Irregular triangle read by rows: T(n,k) = Farey(n,k+1) - Farey(n,k) where Farey(n,k) = A006842(n,k)/A006843(n,k).

Original entry on oeis.org

1, 2, 2, 3, 6, 6, 3, 4, 12, 6, 6, 12, 4, 5, 20, 12, 15, 10, 10, 15, 12, 20, 5, 6, 30, 20, 12, 15, 10, 10, 15, 12, 20, 30, 6, 7, 42, 30, 20, 28, 21, 15, 35, 14, 14, 35, 15, 21, 28, 20, 30, 42, 7, 8, 56, 42, 30, 20, 28, 21, 24, 40, 35, 14, 14, 35, 40, 24, 21, 28, 20, 30, 42, 56, 8

Offset: 1

Isaac Kaufmann, May 30 2019

This is also the product of the denominators of pairs of consecutive terms in the Farey sequence.
Each term of this sequence is an integer: (Proof by induction)
Assume that the reciprocal of Farey differences of order n are the product of the consecutive denominators, i.e., if x/y and c/d are adjacent, then |x/y - c/d| = 1/dy. Let a/b and p/q be adjacent in Farey sequence up to n, such that n+1 = b+q (so only their mediant is in the middle).
As |a/b - p/q| = 1/bq, |aq - bp| = 1, so |aq - bp + ab - ab| = 1, so |a/b - (a+p)/(b+q)| = 1. The base case is trivial. QED

			T(1,1) = 1/(1 - 0);
T(2,1) = 1/(1/2 - 0);
T(2,2) = 1/(1 - 1/2);
T(3,1) = 1/(1/3 - 0);
T(3,2) = 1/(1/2 - 1/3);
T(3,3) = 1/(2/3 - 1/2);
T(3,4) = 1/(1 - 2/3);
...
If written as an array:
  1;
  2,  2;
  3,  6,  6,  3;
  4, 12,  6,  6, 12,  4;
  5, 20, 12, 15, 10, 10, 15, 12, 20, 5;
  ...

Cf. A006842, A006843.

rowf(n) = {my(vf = [0]); for (k=1, n, for (m=1, k, vf = concat(vf, m/k); ); ); vecsort(Set(vf));} \\ A006842/A006843
row(n) = my(vf = rowf(n)); vector(#vf-1, k, 1/(vf[k+1] - vf[k])); \\ Michel Marcus, Jun 07 2019

T(n,k) = Farey(n,k+1) - Farey(n,k) with Farey(n,k) = A006842(n,k)/A006843(n,k).

T(n,k) = A006843(n,k)*A006843(n,k+1).

More terms from Michel Marcus, Jun 07 2019

A005728 Number of fractions in Farey series of order n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, 81, 97, 103, 121, 129, 141, 151, 173, 181, 201, 213, 231, 243, 271, 279, 309, 325, 345, 361, 385, 397, 433, 451, 475, 491, 531, 543, 585, 605, 629, 651, 697, 713, 755, 775, 807, 831, 883, 901, 941, 965

Offset: 0

N. J. A. Sloane

Sometimes called Phi(n).
Leo Moser found an interesting way to generate this sequence, see Gardner.
a(n) is a prime number for nine consecutive values of n: n = 1, 2, 3, 4, 5, 6, 7, 8, 9. - Altug Alkan, Sep 26 2015
Named after the English geologist and writer John Farey, Sr. (1766-1826). - Amiram Eldar, Jun 17 2021

			a(5)=11 because the fractions are 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.

Martin Gardner, The Last Recreations, 1997, chapter 12.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, a foundation for computer science, Chapter 4.5 - Relative Primality, pages 118 - 120 and Chapter 9 - Asymptotics, Problem 6, pages 448 - 449, Addison-Wesley Publishing Co., Reading, Mass., 1989.
William Judson LeVeque, Topics in Number Theory, Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
Andrey O. Matveev, Farey Sequences, De Gruyter, 2017, Table 1.7.
Leo Moser, Solution to Problem P42, Canadian Mathematical Bulletin, Vol. 5, No. 3 (1962), pp. 312-313.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antoine Mathys, Table of n, a(n) for n = 0..20000 (terms 0 to 1000 from T. D. Noe)
Richard K. Guy, Letter to N. J. A. Sloane, 1986.
Richard K. Guy, Letter to N. J. A. Sloane, 1987.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]
Brady Haran and Grant Sanderson, Prime Pyramid (with 3Blue1Brown), Numberphile video (2022).
Sameen Ahmed Khan, Mathematica notebook.
Sameen Ahmed Khan, How Many Equivalent Resistances?, RESONANCE, May 2012.
Sameen Ahmed Khan, Farey sequences and resistor networks, Proc. Indian Acad. Sci. (Math. Sci.), Vol. 122, No. 2 (May 2012), pp. 153-162.
Sameen Ahmed Khan, Beginning to count the number of equivalent resistances, Indian Journal of Science and Technology, Vol. 9, No. 44 (2016), pp. 1-7.
Andrey O. Matveev, Farey Sequences: Errata + Haskell code
Shmuel Schreiber and N. J. A. Sloane, Correspondence, 1980.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021. (Includes this sequence)
Vladimir Sukhoy and Alexander Stoytchev, Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle, Scientific Reports, Vol. 10, Article No. 4852 (2020).
Vladimir Sukhoy and Alexander Stoytchev, Formulas and algorithms for the length of a Farey sequence, Scientific Reports, Vol. 11 (2021), Article No. 22218.
Eric Weisstein's World of Mathematics, Farey Sequence.
Wikipedia, Farey sequence.

For the Farey series see A006842/A006843.
Essentially the same as A049643.
Cf. A002088, A055197, A055201.

List([0..60],n->Sum([1..n],i->Phi(i)))+1; # Muniru A Asiru, Jul 31 2018

a005728 n = a005728_list
a005728_list = scanl (+) 1 a000010_list
-- Reinhard Zumkeller, Aug 04 2012

[1] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // Vincenzo Librandi, Sep 27 2015

A005728 := proc(n)
    1+add(numtheory[phi](i),i=1..n) ;
end proc:
seq(A005728(n),n=0..80) ; # R. J. Mathar, Nov 29 2017

Accumulate@ Array[ EulerPhi, 54, 0] + 1
f[n_] := 1 + Sum[ EulerPhi[m], {m, n}]; Array[f, 55, 0] (* or *)
f[n_] := (Sum[ MoebiusMu[m] Floor[n/m]^2, {m, n}] + 3)/2; f[0] = 1; Array[f, 55, 0] (* or *)
f[n_] := n (n + 3)/2 - Sum[f[Floor[n/m]], {m, 2, n}]; f[0] = 1; Array[f, 55, 0] (* Robert G. Wilson v, Sep 26 2015 *)
a[n_] := If[n == 0, 1, FareySequence[n] // Length];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2022 *)

a(n)=1+sum(k=1,n,eulerphi(k)) \\ Charles R Greathouse IV, Jun 03 2013

from functools import lru_cache
@lru_cache(maxsize=None)
def A005728(n): # based on second formula in A018805
    if n == 0:
        return 1
    c, j = -2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A005728(k1)-3)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

a(n) = 1 + Sum_{i=1..n} phi(i).
a(n) = n*(n+3)/2 - Sum_{k=2..n} a(floor(n/k)). - David W. Wilson, May 25 2002
a(n) = a(n-1) + phi(n) with a(0) = 1. - Arkadiusz Wesolowski, Oct 13 2012
a(n) = 1 + A002088(n). - Robert G. Wilson v, Sep 26 2015

cp's OEIS Frontend

A358886 Number of regions formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A358887 Number of vertices formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A358888 Number of edges formed inside a square with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A358948 Number of regions formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A358949 Number of vertices formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A358950 Number of edges formed inside a triangle with edge length 1 by the straight line segments mutually connecting all vertices and points that divide the sides into segments with lengths equal to the Farey series of order n = A006842(n,k)/A006843(n,k), k = 1..A005728(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A308483 Irregular triangle read by rows: T(n,k) = Farey(n,k+1) - Farey(n,k) where Farey(n,k) = A006842(n,k)/A006843(n,k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A005728 Number of fractions in Farey series of order n.

Views

Author

Keywords