Skip to main content
1 of 5
user76568
  • 401
  • 1
  • 4
  • 13

Implementing the Farey sequence efficiently

There is of course the the silly implementation:

FareySequence[n_] := Union[Flatten[Table[j/i, {i, 1, n}, {j, 0, i}]]]

However, There is this property of Farey sequences: $F_0=0, \ F_n=1, \\ F_k=F_{k-1} + 1/(D_kD_{k-1})$

where $F$ is the Farey sequence and $D$ is the denominator sequence of $F$ in reduced form.

This calls for a very simple recurring/functional implementation. But I'm new to Mathematica and can't find the right combination of built in functions, and pure functions..

Ideas?

user76568
  • 401
  • 1
  • 4
  • 13