>>412
手助けになればいいけど、下の定理2.1.6を使えば Σ_(k=√n) sin(n/k) = O(n^(1/3)) まで落とせそう
https://spectrum.library.concordia.ca/978881/

Theorem2.1.6 (2nd derivative test)
fは区間[a,b]上で二階連続的微分可能であり、c>1 であって
0<λ≦f''(t)≦cλ (for∀t∈[a,b])
が成り立っているとする。この時、
Σ_(a<k≦b) e^(2πif(k)) = O_c( (b-a)λ^(1/2) + λ^(-1/2) ).□

具体的には m を正の整数（この場合およそ (√n)/(2π) ）として、j=0,1,… に対して a_j = m･2^(-j-1), b_j = a･2^(-j) と定めて、
f(x)=N/x として各区間 [a_j,b_j] に対して定理を適用する訳なんだけど、
この場合 j の値にかかわらず c=8 で一様にとれるから、j=0,1,…,r で足し合わせても同じ implied constant で抑えられる。
あとは r の値をうまく調整すればOK