I'm doing some "research" for a high school competition, and I stumbled upon a problem I'll describe below. I'll be thankful for any references where can I find any results on this topic – I can't find anything, but on the other hand I would be very surprised if nobody had ever thought of that.
I have a number $N$, and I want to find such $a \in \{1,2,\ldots,N\}$ that $\gcd(a,N)=1$ and continued fraction of $\frac{a}{N}$ has a
- minimal sum of denominators (I mean coefficients, I'm not sure of correct terminology in English)
or
- maximal number of denominators
I'm directly interested only in 1), but 2) would suffice for me for deriving some bounds.
I'm able to prove that the answer to 1) lies between $\log (N)$ and $\sqrt{N}\log (N)$, and I think my method implies that the answer to 2) is between $\frac{1}{2} \log (N) - o(\log (N))$ and $\log (N)$ (to be exact, these logarithms have to have base $\phi$, anyway any improvement of constant here would give much better bounds in 1)).
As I have said, I'm looking if something like this has already been done by someone with broader knowledge than mine. I couldn't find anything similar, but on the other hand I'm not used to doing such searches and I think it's more probable that I wasn't searching well than that nothing was done in this subject.
EDIT: I've just realize that my $O(\sqrt{n} \log(n))$ bound I was so proud of can be trivially replaced by $O(\sqrt{n})$ by taking simply $a \approx \sqrt{N}$ (my former strategy was taking $a \approx \frac{N}{\phi}$, which should work much better in average case, but has worse worst case performance).