Today, I wanted to write a program to count how many integer pairs $(a, b)$ that satisfy: $$1 \leq a < b \leq n, \gcd(a, b) = 1$$
My first instinct was to write a function that check every pair. However, I noticed a problem. As $n$ gets large, the code will take long to run, since it has a time complexity of $O(n^2 \log n)$ (I'm looking at every pair, so that's $O(n^2)$, each pair's gcd check is $O(\log n)$, . Therefore, I wanted to write code that has less time complexity. So I looked into the function in an induction manner, "what happens if we add $n + 1$ into the mix of the $n$ numbers from $1$ to $n$?". Then I realized that if you want to calculate $f(n)$, you need to compare all pairs $(a, b), 1 \leq a < b \leq n$ of integers from $1$ to $n$, and $$f(n + 1) = \text{Number of pairs from } 1 \text{ to } n, \text{a.k.a } f(n) +\\ \text{Number of integers coprime with } n + 1 \text{ a.k.a } \phi(n + 1) $$ because after we already ran through all pairs from $1$ to $n$, adding $n + 1$ would add only new pairs with it, which equals $\phi(n + 1)$. (Here $\phi(x)$ denotes the Euler totient function)
With that new knowledge, I can add a second "equivalent" definition to $f(n)$: $$f_o(n) = \sum_{k = 1}^n \phi(n)$$. (The $o$ subscript here means "other definition"
However "equivalent" is in quotes here, because apparently this second definition would always be one more than the first one, a.k.a $f_o(n) = f(n) + 1$ for all integer inputs $n$ I've tried. I don't know why it happened. What do you think?
P.S I find a method to calculate $\phi(n)$ for all integers from $1$ to $n$ inclusive, and store the results in an array. The algorithm code is here. This would make the time complexity for calculating all this down to $O(n \log \log n)$, according to the site.
Ok so right the moment I pressed post button I figured out the answer. You see, if $n = 1$, there would not be any pair at all, but $\phi(1) = 1$, and the second definition picked that extra $1$ up. All I need to do is to start the iteration of the second definition from $2$ and I'm set.