I need to get the index $I_n(a, b)$ of $\frac{a}{b}$ in $F_n$ the Farey sequence of order n.

After some searching I landed on this paper, which I'm trying to understand (in parts, and even if there might be better/easier way to compute Farey indexes), more specifically the Remark 7.10 which I think could help me.

The problem is that I'm confused with a notation involving Euler's totient function.

Remark 7.10 (ii) (a) :

Considering Farey subsequences of the form $(\frac{h}{k} \in F_n : h \leq k)$, where $0 \lt m \leq n$,

If $f_t \in (\frac{h}{k} \in F_n : h \leq k) - \{\frac{1}{1}\} $, then
$$ t = \sum_{j=1}^n \phi(j; [1, min\{m, \lfloor j.f_t \rfloor \}]) $$

So far, what I got is an implementation of the "regular" totient function, $ \phi(n)$, which counts the number of integers less than n which are relatively prime to n, but I'm not sure how to implement what the author refers to with the notation above.

Also, if you know other ways of achieving the same task programmatically, don't hesitate to share it.

[Edit]: Actually I missed the part where the author describes the $\phi(.;.)$ notation :

Remark 7.2

Let $n \in \mathbb P$, and let S be a subset of [1, n]. We denote by $\phi(n; S)$ the number of elements from S that are relatively prime to n: $$ \phi(n; S) := |\{ s \in S: n \perp s \}| $$ thus, $ \phi(n; [1, n]) $ is the Euler function.

So, if I understand correctly, $\phi(j; [1, min\{m, \lfloor j.f_t \rfloor \}])$ counts only the totatives of j that are member of $ [1, min\{m, \lfloor j.f_t \rfloor \}] $.

Now I'm still confused with that $m$, if someone can explain what does it refer to exactly (from "Farey subsequences in Boolean context" to the above), it would be great !

  • $\begingroup$ Just to get the terminology straight, I take the Farey sequence of order $n$, to mean all positive rationals strictly between $0$ and $1$, with denominator $\leq n$ in lowest terms, arranged in increasing order, so that the first element is $\frac1n$ and the last is $\frac{n-1}n$. Is that the same definition you're using? $\endgroup$
    – saulspatz
    Commented Aug 13, 2021 at 16:50
  • $\begingroup$ The $m$ first arises in your own comment, "Considering Farey subsequences of the form $(\frac{h}{k} \in F_n \colon h \leq k)$, where $0 \lt m \leq n$". What does $m$ mean there? $\endgroup$ Commented Aug 13, 2021 at 16:53
  • $\begingroup$ @saulspatz yes that's the same definition. $\endgroup$ Commented Aug 13, 2021 at 16:59
  • $\begingroup$ @GregMartin Actually it's also quoted from the paper. The m appears early in the point 7 "Farey subsequences in Boolean context". I think I'm making progress in the understanding, it would seem I just need to set m=1 (for referring to the entire sequence Fn, not a subsequence..). $\endgroup$ Commented Aug 13, 2021 at 17:07
  • $\begingroup$ I think the formula you want is given here $\endgroup$
    – saulspatz
    Commented Aug 13, 2021 at 17:12


You must log in to answer this question.

Browse other questions tagged .