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

Author

Travis Hoppe, Jul 09 2022

Keywords

• nonn

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.

Examples

			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.
		

Crossrefs

Cf. A006842/A006843 (Farey sequences).

Cf. A005728 (number of distinct points).

Programs

Mathematica

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

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

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