0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Todor Markov
    Feb 12, 2019 at 9:42
  • $\begingroup$ Hm no, I'm looking for $10^{19} <= j <= 10^{20}$ $\endgroup$
    – S. L.
    Feb 12, 2019 at 9:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .