### ljsh_king's blog

By ljsh_king, history, 6 weeks ago,

I was reading this article, and saw example 1 (number of coprime pairs in range [1, n]). I tried to solve this problem with similar formula. Here's what I wrote:

$\sum_{i=1}^n \sum_{j=1}^n [gcd(a_i, a_j) = 1]$

$= \sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(a_i, a_j)} \mu{(d)}$

$= \sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^{\infty} [d|a_i][d|a_j]\mu{(d)}$

$= \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i]) (\sum_{j=1}^n [d|a_j])$

$= \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i])^2$

We can calculate $\mu{(d)}$ using linear sieve in $O(max(a_i))$

and $\sum_{i=1}^n [d|a_i]$ for each $d$ in $O(n * \sqrt{max(a_i)})$

But it turns out that when the input is

2
1 2


mu = {1, -1}

cnt = {2, 1}

Gives output of $1 * 2^2 + -1 * 1^2 = 3$ which is absolutely wrong.

Can anyone point out my mistake? Thanks.

• +8

 » 6 weeks ago, # |   +7 The $3$ pairs are $(1, 1), (1, 2), (2, 1)$. It's relatively easy to fix the code in such a way that the order of $i, j$ doesn't matter.
•  » » 6 weeks ago, # ^ |   +3 That make sense. Thanks for pointing that out!
The text passage contains a mathematical problem related to calculating the number of coprime pairs in a given range, and it includes a detailed formula and an example with an incorrect output. The passage also includes a comment that explains the mistake and provides the correct pairs.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
### ljsh_king's blog

By ljsh_king, history, 6 weeks ago,

I was reading this article, and saw example 1 (number of coprime pairs in range [1, n]). I tried to solve this problem with similar formula. Here's what I wrote:

$\sum_{i=1}^n \sum_{j=1}^n [gcd(a_i, a_j) = 1]$

$= \sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(a_i, a_j)} \mu{(d)}$

$= \sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^{\infty} [d|a_i][d|a_j]\mu{(d)}$

$= \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i]) (\sum_{j=1}^n [d|a_j])$

$= \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i])^2$

We can calculate $\mu{(d)}$ using linear sieve in $O(max(a_i))$

and $\sum_{i=1}^n [d|a_i]$ for each $d$ in $O(n * \sqrt{max(a_i)})$

But it turns out that when the input is

2
1 2


mu = {1, -1}

cnt = {2, 1}

Gives output of $1 * 2^2 + -1 * 1^2 = 3$ which is absolutely wrong.

Can anyone point out my mistake? Thanks.

• +8

 » 6 weeks ago, # |   +7 The $3$ pairs are $(1, 1), (1, 2), (2, 1)$. It's relatively easy to fix the code in such a way that the order of $i, j$ doesn't matter.
•  » » 6 weeks ago, # ^ |   +3 That make sense. Thanks for pointing that out!
user
The text passage contains a mathematical problem related to calculating the number of coprime pairs in a given range, and it includes a detailed formula and an example with an incorrect output. The passage also includes a comment that explains the mistake and provides the correct pairs.

TYPE: SINGLE_QUESTION_WITH_ANSWER