Bekh's blog

How to solve UVA12995 — Farey Sequence
By Bekh, history, 4 years ago, In English

The problem can be found here: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4878

I know the final answer but idk how to get it myself.
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Apologies. I misread the problem.

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Consider two fractions $$$\frac{x}{y}$$$ and $$$\frac{a}{b}$$$. And let's assume that $$$b \geqslant y$$$. For a fixed $$$a$$$ we are interested in such fractions $$$\frac{x}{y}$$$ that $$$|ay - bx| = 1$$$. Also we must pick only fractions with $$$gcd(x,y) = 1$$$, but that's not a problem, since other fractions will not be a solution for this equation.

Let's first consider case $$$ay - bx = +1$$$. Since $$$gcd(a, b) = 1$$$, there always exist infinite many solutions in the form $$$x = at + x_0$$$, $$$y = bt + y_0$$$. Remember, we decided to choose $$$y \leqslant b$$$. Also, $$$y = b$$$ or $$$y = 0$$$ are not solutions (if $$$b \neq 1$$$, but that's a special case). So let's choose $$$t$$$ such that $$$1 \leqslant y \leqslant b - 1$$$. And it can be seen that for that $$$y$$$, $$$x$$$ will be a legit numerator (that is, $$$0\leqslant x < y$$$).

So for every $$$a$$$ such that $$$gcd(a, b) = 1$$$, we have exactly one solution. One more comes from $$$ay - bx = -1$$$. That gives us $$$2\sum\limits_{i=1}^n \varphi(i)$$$. And from that we have to subtract number of consecutive pairs, which is $$$1$$$ smaller than number of fractions, which is $$$\sum\limits_{i=1}^n \varphi(n)+1$$$.

That gives $$$\sum\limits_{i=1}^n \varphi(i)$$$, but I believe that $$$\pm 1$$$ comes from the case $$$b = 1$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey,

    thank you for the detailed answer. However, there are two parts that are not very clear to me.

    1. How do you know that there is exactly 1 $$$t$$$ that satisfies our constraints? I tried to prove it by observing the possible range of values for $$$t$$$ but I think I'm missing something.

    $$$1 \leq y \leq b - 1$$$

    $$$1 \leq bt + y_0 \leq b - 1$$$

    $$$ \frac{1 - y_0}{b} \leq t \leq \frac{b - 1 - y_0}{b} $$$

    So the size of the range of possible values of $$$t$$$ is:
    $$$\frac{b - 1 - y_0 - (1 - y_0)}{b} = \frac{b - 2}{b}$$$

    Which is actually less than $$$1$$$ so something is clearly lacking my understanding.

    1. How do you know that for the $$$y$$$ we pick, $$$x$$$ will follow $$$0 \leq x \lt y$$$
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      For the first part: we can search for $$$t$$$ such that $$$0 \leqslant bt + y_0 \leqslant b - 1$$$. Then there are exactly $$$b$$$ integers in $$$[0; b-1]$$$, so there will be exactly one solution. But $$$y = 0$$$ is not a solution (because $$$-bx \neq 1$$$ for $$$b \neq 1$$$)

      About $$$x$$$: from $$$ay - bx = 1$$$, $$$x = \frac{ay - 1}{b}$$$. For $$$y \in [1;b-1]$$$, $$$0 < ay - 1 < by$$$ (since $$$a < b$$$), so $$$0 < x < y$$$

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks a lot, Maksim. It is perfectly clear to me right now. I just wanna verify one last thing.

        it should be $$$0 \leq x \leq y$$$. Right?
        $$$0 \leq y$$$ since we cannot guarantee that $$$ay - 1 > 0$$$, but that won't be a problem for us since $$$\frac{0}{1}$$$ is the only pair with $$$x == 0$$$ (because $$$gcd(x, y) == 1$$$) and it is part of our farey sequence and should be counted.

        $$$x \leq y$$$ comes from the second equation $$$ay - bx = -1$$$. as $$$x = \frac{ay + 1}{b}$$$ this time. But this also won't be a problem for us since the only pair that will have $$$x == y$$$ is $$$\frac{1}{1}$$$ (also because $$$gcd(x, y) == 1$$$ and it is also part of the farey sequence and should be counted.

        Also for those who are interested on where I went wrong in my proof of the first part: We are not interested in the 'size' of the range of possible values of $$$t$$$. We are interested in the number of possible integer solutions for $$$t$$$. The size could be less than $$$1$$$ and still span an integer. e.g. [0.9, 1.1] has size 0.2 but still spans an integer in the middle.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          To be fair, I didn't care much about less or less-equal, or $$$\pm 1$$$, because you already had an answer and just asked for an explanation :)

          Yes, $$$0 \leqslant x$$$, not $$$0 < x$$$, that's my mistake.

          And $$$x \leqslant y$$$ is a correct sign too, I agree, sorry for this.

          I was thinking about considering $$$b=1$$$ as a special case, but $$$y=1$$$ is not a special case, so I should have thought about that.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No worries :). I'm just always super afraid to be doing something wrong when dealing with math and always wanna verify I'm not missing an obvious thing. Thanks again!

            → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

For two fractions $$$\frac{m_1}{n_1}$$$ and $$$\frac{m_2}{n_2}$$$ to have $$$m_2 n_1 - m_1 n_2 = 1$$$ They must be adjacent in some farey sequence $$$F_x$$$, but not necessarily $$$F_n$$$. So we can reframe the problem as "Count the number of pairs of fractions that are in $$$F_n$$$ and were previously neighbors in $$$F_i$$$, $$$i < n$$$

The sequence $$$F_n$$$ has $$$\phi(n)$$$ extra elements from $$$F_{n-1}$$$ (as all numbers which are not coprime will need to be simplified, thus denominator will decrease, thus won't be new fractions). Every extra element "separates" two fractions that were previously adjacent, i.e. it adds $$$\phi(n)$$$ pairs. Formally, $$$A_1 = 0$$$, $$$A_n = A_{n-1} + \phi(n)$$$.

From there it's easy to see that for $$$n \geq 2$$$: $$$A_n = \sum_{i=2}^{n}{\phi(i)}=\sum_{i=1}^{n}{\phi(i)} - \phi(1) = \sum_{i=1}^{n}{\phi(i)} - 1$$$.

→ Reply