0

Given a number $j$, is there a way to determine that it is the length of a valid Farey sequence.

The length is given by:

$$|F_n| = \frac{1}{2}(n+3)n - \sum_{d=2}^n |F_\frac{n}{d}|$$

For example, 2, 7, 16875 all valid (lengths of sequence of orders 1, 4, 235), but 4 is invalid, since there is no valid Farey sequence of that length.

For now, I see no option but to compute $|F_n|$ up to $|F_n| <= j$ for $n=1...n$. This approach is fine for small j ($j<10^6$) but becomes unpractical above that. Is there a better way?

S. L.
  • 157
  • Using $|F_n| = |F_{n-1}| + \phi(n)$ should allow much more efficient computation using a sieve to compute $\phi$, perhaps up to $j<10^12$ or thereabouts. Do you think that's good enough? – Todor Markov Feb 12 '19 at 09:42
  • Hm no, I'm looking for $10^{19} <= j <= 10^{20}$ – S. L. Feb 12 '19 at 09:58

0 Answers0