Skip to main content
completed answer.
Source Link
Henri Cohen
  • 13.1k
  • 1
  • 34
  • 62

Partial answer: elementary arithmetic transformations show that $$S(n,1,1)=\sum_{1\le y\le n}\dfrac{1}{y}\sum_{d\mid y}\phi(d)\lfloor n/d\rfloor$$ which allows for much faster computation since it is essentially a single sum. I didn't push the analysis further, but my guess is that $S(n,1,1)$ is asymptotic to $Cn\log(n)^2$ (with a log squared), perhaps with $C=3/\pi^2=1/(2\zeta(2))$.

Complete answer: I was really lazy. From the expression above, it is immediate to show that $$S(n,1,1)=\sum_{1\le d\le n}\dfrac{\phi(d)}{d}\log(n/d)+O(n\log(n))\;,$$ and the main term is indeed asymptotic to $Cn\log(n)^2$ with $C=3/\pi^2$ if I am not mistaken.

Partial answer: elementary arithmetic transformations show that $$S(n,1,1)=\sum_{1\le y\le n}\dfrac{1}{y}\sum_{d\mid y}\phi(d)\lfloor n/d\rfloor$$ which allows for much faster computation since it is essentially a single sum. I didn't push the analysis further, but my guess is that $S(n,1,1)$ is asymptotic to $Cn\log(n)^2$ (with a log squared), perhaps with $C=3/\pi^2=1/(2\zeta(2))$.

Partial answer: elementary arithmetic transformations show that $$S(n,1,1)=\sum_{1\le y\le n}\dfrac{1}{y}\sum_{d\mid y}\phi(d)\lfloor n/d\rfloor$$ which allows for much faster computation since it is essentially a single sum. I didn't push the analysis further, but my guess is that $S(n,1,1)$ is asymptotic to $Cn\log(n)^2$ (with a log squared), perhaps with $C=3/\pi^2=1/(2\zeta(2))$.

Complete answer: I was really lazy. From the expression above, it is immediate to show that $$S(n,1,1)=\sum_{1\le d\le n}\dfrac{\phi(d)}{d}\log(n/d)+O(n\log(n))\;,$$ and the main term is indeed asymptotic to $Cn\log(n)^2$ with $C=3/\pi^2$ if I am not mistaken.

Source Link
Henri Cohen
  • 13.1k
  • 1
  • 34
  • 62

Partial answer: elementary arithmetic transformations show that $$S(n,1,1)=\sum_{1\le y\le n}\dfrac{1}{y}\sum_{d\mid y}\phi(d)\lfloor n/d\rfloor$$ which allows for much faster computation since it is essentially a single sum. I didn't push the analysis further, but my guess is that $S(n,1,1)$ is asymptotic to $Cn\log(n)^2$ (with a log squared), perhaps with $C=3/\pi^2=1/(2\zeta(2))$.