A355616 a(n) is the number of distinct lengths between consecutive points of the Farey sequence of order n.

1, 1, 2, 3, 5, 6, 9, 11, 14, 15, 21, 23, 29, 31, 34, 38, 48, 49, 59, 63, 67, 71, 83, 86, 97, 100, 110, 115, 132, 133, 150, 158, 165, 169, 182, 187, 208, 213, 222, 228, 252, 254, 280, 287, 297, 304, 331, 337, 362, 367, 379, 387, 418, 423, 437, 450, 464, 472, 509, 513, 548, 556, 573, 589, 608, 611, 652, 665, 681, 685

Offset

1,3

Comments

The Farey sequence of order n (row n of A006842/A006843) is the set of points x/y on the unit line where 1 <= y <= n and 0 <= x <= y.

Links

Table of n, a(n) for n=1..70.

Example

For n=5, the Farey sequence (completely reduced fractions) is [0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1]. The distinct lengths between consecutive points are {1/5, 1/20, 1/12, 1/15, 1/10} so a(5) = 5.

Mathematica

a[n_] := FareySequence[n] // Differences // Union // Length;
Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Jul 16 2022 *)

Prog

(Python)
from fractions import Fraction
from itertools import chain
def compute(n):
    marks = [[(a, b) for a in range(0, b + 1)] for b in range(1, n + 1)]
    marks = sorted(set([Fraction(a, b) for a, b in chain(*marks)]))
    dist = [(y - x) for x, y in zip(marks, marks[1:])]
    return len(set(dist))
(PARI) vp(n) = my(list = List()); for (k=1, n, for (i=0, k, listput(list, i/k))); vecsort(list, , 8);
a(n) = my(v=vp(n)); #Set(vector(#v-1, k, abs(v[k+1]-v[k]))); \\ Michel Marcus, Jul 10 2022

Crossrefs

Cf. A006842/A006843 (Farey sequences).

Cf. A005728 (number of distinct points).

Sequence in context: A113238 A104214 A349523 * A046657 A102825 A070991

Adjacent sequences: A355613 A355614 A355615 * A355617 A355618 A355619

Keyword

nonn

Author

Travis Hoppe, Jul 09 2022

Status

approved