All Questions
13
questions
6
votes
2
answers
201
views
How prove this inequality $\sum_{i=1}^{n}\sum_{j=1}^{n}\text{lcm}(i,j)\le\frac{n^3}{5}(n+4)$?
Let $n$ be postive integers. Show that
$$\sum_{i=1}^{n}\sum_{j=1}^{n}[i,j]\le\dfrac{n^3}{5}(n+4)\,,$$ where $[a,b]$ denote the least common multiple of $a$ and $b$.
$S_1=1=\dfrac{1^3}{5}(4+1)=1$
...
- 93.6k
1
vote
1
answer
99
views
How to prove this inequality: $\sum_{i=1}^{n}\sum_{j=1}^{n}\text{lcm}(i,j)\ge\frac{7}{8}n^3$?
Let $n$ be postive integers. Show that
$$\sum_{i=1}^{n}\sum_{j=1}^{n}[i,j]\ge\dfrac{7}{8}n^3\,,$$ where $[a,b]$ denote the least common multiple of $a$ and $b$.
For $n=1,2,3 $, it is clear. How ...
- 93.6k
2
votes
0
answers
138
views
Find the asympt. expan. as $N \rightarrow \infty$ of $\sum_{r,s,t=1}^{N} \left[\sqrt{s^2 \pm 4 r t} \in \mathbb{Z}\right] \left[\gcd(r,s,t)=1\right]$
Where $[...]$ are the Iverson brackets. This expression arises from my research on counting the number of reducible quadratics with coefficients constrained by naive height $N \ge 1$ and $r$, $s$, $t$...
- 967
0
votes
2
answers
75
views
How do we efficiently compute the value of expression given below?
How to compute the value of following expression efficiently?
$$\sum_{x=1}^N\sum_{y=1}^N \frac{xy}{\gcd(x,y)^2}$$
I tried by my self but I am getting TLE with my solution.
Problem from HackerEarth.
0
votes
1
answer
283
views
Compute $\sum_{i=1}^n\frac i{\gcd(i,n)}$
Compute $$\sum_{i=1}^n\frac i{\gcd(i,n)}$$
The actual problem description is as follows :
$$\sum_{i=1}^{15}\frac i{\gcd(i,{15})}$$
But I'd like a formula which could be used for large $n$.
- 51
0
votes
2
answers
36
views
Elementary Number Theory - question maybe using modular arithmetic
Let $m$, $k$ be natural numbers. Then show that
$$\sum\limits_{\substack{1\le n \le mk \\\gcd(n,m)=1}} 1 =k \sum_{\substack{1\le n \le m\\\gcd(n,m)=1}} 1.$$
I've thought about this question a lot, ...
- 101
5
votes
1
answer
223
views
Is there a closed form for the double sum $\sum_{n,k} \frac{1}{\text{lcm}^3 (n,k)}$
Is there a closed form for the double sum with least common multiple: $$\sum_{n \geq 1} \sum_{k \geq 1} \frac{1}{\text{lcm}^3 (n,k)}$$
For truncated sums, Mathematica gives:
$$\sum_{n = 1}^{2500} \...
- 31.7k
5
votes
2
answers
2k
views
Relation between $\gcd$ and Euler's totient function .
How to show that $$\gcd(a,b)=\sum_{k\mid a\text{ and }k\mid b}\varphi(k).$$
$\varphi$ is the Euler's totient function.
I was trying to prove the number of homomorphisms from a cyclic group of order $...
- 2,646
7
votes
1
answer
1k
views
how to calculate double sum of GCD(i,j)?
I stumbled upon a programming question which wanted me to calculate :
$$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$
now I wrote a code to solve this problem but it takes polynomial time to ...
- 235
0
votes
1
answer
104
views
Calculate the sum under gcd
I have a question: How can I calculate
$$\sum_{i=1\atop \gcd(i,75)=1}^{75} i=?$$
- 853
2
votes
1
answer
707
views
Euler's totient function and related sum
I am supposed to calculate the following sum :
$\sum _{d|n} (n/d) * \phi (n/d)$ where the sum is over all divisors (d) of a given number (n) and $\phi (x)$ is Euler's totient function .
Since the ...
user180000
-1
votes
1
answer
373
views
$\sum_{i=1}^n \frac{n}{\text{gcd}(i,n)}.$ [closed]
Find the value of this series:
$$\sum_{i=1}^n \frac{n}{\text{gcd}(i,n)}.$$
- 19
2
votes
2
answers
151
views
Prove or disprove: $ \sum_{b \vee d = x} \tau(b) \tau(d) = \tau(x)^3$
Can somebody prove or disprove? Let $\tau$ be the divisors function, so that $\tau(6) = \#\{ 1,2,3,6\} = 4$
$$ \sum_{b \vee d = x} \tau(b) \tau(d) = \tau(x)^3$$
Here I am using $b \vee d = \mathrm{...
- 24.5k