6
$\begingroup$

Define $$f(n)=\sum_{d|n}gcd(d,\frac{n}{d})$$ $$F(x)=\sum_{n=1}^xf(n)$$ for natural numbers d,n and x.

I would like to know if there is some simplified form of $F(x)$ in terms of arithmetic functions, or atleast some computationally feasible form for large $x$.($x$ is of the order $10^{15}$ or higher).

A brute force approach is not efficient because of the $d|n$.Exchanging the summations is a slight improvement.But even after that I can't evaluate $F(x)$ for $x>10^7$ within reasonable time for which I believe a total mathematical algorithmic change is needed.

How can we manipulate the given expression so that the computation is reasonably fast?

EDIT:I just found out this is one of the Project Euler problems-problem no. 530

$\endgroup$
4
  • 1
    $\begingroup$ Actually we dont even need n, since there is a sum over n too while defining F(x). $\endgroup$ Sep 2, 2020 at 8:34
  • $\begingroup$ Perhaps you can precompute the values of $f(n)$ and $F(x)$. $\endgroup$
    – cgss
    Sep 2, 2020 at 8:34
  • 2
    $\begingroup$ No idea whether this is of any use. But for squarefree $n$, $f(n)$ is just the number of divisors of $n$. $\endgroup$
    – Peter
    Sep 2, 2020 at 8:54
  • 1
    $\begingroup$ No idea whether this is of any use, but if we define $$c(p,i):=\begin{cases} 2p^{\tfrac{i+1}{2}}&\text{ if }i\equiv1\pmod{2}\\ p^{\tfrac i2+1}+p^{\tfrac i2}&\text{ if }i\equiv0\pmod{2}\ \end{cases},$$ then for the function $S(n,k)$ defined by the recursion $$S(n,k):=\sum_{i=0}^{\lfloor\log_{p_k}x\rfloor}\frac{c(p_k,i)-2}{p_k-1}S\big(\lfloor\tfrac{x}{p_k^i}\rfloor,k+1\big),$$ and $S(0,k)=0$ and $S(1,k)=1$, we have $$S(x,1)=\sum_{n=1}^x\sum_{d\mid n}\gcd(d,\tfrac dn)=F(x).$$ Here $p_k$ denotes the $k$-th prime, starting from $p_1=2$. $\endgroup$ Sep 3, 2020 at 16:44

2 Answers 2

4
$\begingroup$

PARTIAL ANSWER: Here is an alternative formula for $F(x)$: $$F(x)=\sum_{k=1}^{\sqrt{x}}g_x(k)k$$ where $$g_x(k) = |\{ (a,b) : abk^2 \le x, \ \gcd(a,b)=1 \}|$$

proof:

For a fixed $x>0$, consider the following set $$I_x=\{ (k, d, n) \ : \ k=\gcd(d, n/d), \ \ d|n,\ \ n \le x\}$$ Then your $F(x)$ is just $$F(x)= \sum_{(k,d,n) \in I_x} k$$ Let's study how this set $I_x$ is made.

First of all, note that for all $(k,d,n) \in I_x$ you have that $k$ divides both $d$ and $n/d$, hence $$k^2 \ \mbox{ divides } n = d \cdot (n/d)$$ In particular $k \le \sqrt{x}$.

On the other hand, for arbitrary $k \le \sqrt{x}$ you have $(k,k,k^2) \in I_x$. This means that all numbers $k \le \sqrt{x}$ appear at least once as the first coordinate of a triple $(k,d,n) \in I_x$, while all numbers $k > \sqrt{x}$ don't.

So, let's call $$g_x(k) = |\{ (d,n) \ : \ (k,d,n) \in I_x \}|$$ This function counts how many times $k$ appears as a first coordinate of a triple $(k,d,n) \in I_x$, so that $$F(x)= \sum_{(k,d,n) \in I_x} k=\sum_{k=1}^{\sqrt{x}} g_x(k) \cdot k$$ To conclude the proof we have to show that $$g_x(k) = 2 \lfloor \frac{x}{k^2} \rfloor-1$$

For a fixed $k \le \sqrt{x}$, you have that $(k,d,n) \in I_x$ if and only if $k= \gcd(d,n/d)$. This means that $d=ak$ and $n/d=bk$ for some $a,b$. Thus we can consider the set of quintuples $$J_x= \{ (k,a,b,d,n) \ : \ d=ak, \ n/d=bk, \ \gcd(a,b)=1, \ d|n, \ n \le x \}$$ which is in clear bijection with $I_x$ by the map $(k,a,b,d,n) \mapsto (k,d,n)$. Note that $a=d/k$ and $b=n/(dk)=n/(abk^2)$. So that our $J_x$ is in bijection with the set $$L_x = \{ (k, a, b) : \ abk^2 \le x , \ \gcd(a,b)=1\}$$ by the map $(k,a,b,d,n) \mapsto (k,a,b)$, because $n=abk^2 \le x$. In other words $g_x(k)$ counts the number of pairs $(a,b)$ of coprime numbers $a,b$ such that $abk^2 \le x$, or $$ab \le \frac{x}{k^2}$$

continues...

OK, MY BAD, NOW I NOTICED THAT THIS NUMBER IS NOT $2 \lfloor \frac{x}{k^2} \rfloor-1$, BUT IT'S TRICKIER. I'll leave this answer for who wants to conclude my computations.

$\endgroup$
3
  • $\begingroup$ Appears to be a very nice approach (+1) $\endgroup$
    – Peter
    Sep 2, 2020 at 9:15
  • $\begingroup$ $(k,k,k) \not\in I_x$. Perhaps you meant $(k,k,k^2)$? $\endgroup$
    – cgss
    Sep 2, 2020 at 9:30
  • $\begingroup$ Sorry guys, while I was writing the proof I noticed that my idea was good, but more complicated than I thought. $\endgroup$
    – Crostul
    Sep 2, 2020 at 9:47
2
$\begingroup$

It can be proved that $\displaystyle \sum_{d\mid n} (d,n/d) = \sum_{d^2\mid n}\tau(n/d^2)\varphi(d)$.

So one can show that $\displaystyle F(x) = \sum_{n\le \sqrt{x}}\varphi(n)\sum_{m \le x/n^2} \left\lfloor\frac{x}{n^2 m}\right\rfloor$.

This is the best i can do, but this is still computationally unfeasible for $x \approx 10^{15}$.

$\endgroup$
5
  • $\begingroup$ With this formula, my computer calculate $F(10^9)$ in about 13 minutes. Since it grows at least linearly, $x = 10^{15}$ is definitely out of range. $\endgroup$
    – jjagmath
    Sep 2, 2020 at 14:34
  • $\begingroup$ You have a typo in your formula for $F(x)$, it ought to be $$F(x) = \sum_{n \leqslant \sqrt{x}} \varphi(n) \sum_{m \leqslant x / n^2} \biggl\lfloor \frac{x}{m\cdot n^2}\biggr\rfloor\,.$$ And you can easily make that computationally feasible ($7$ seconds for $x = 10^{15}$ in not yet optimised C on my old laptop) using two tricks. First, don't compute $\varphi(n)$ for each $n$ separately, precompute all needed values in an array, similar to a sieve of Eratosthenes (takes $O(\sqrt{x})$ space and $O(\sqrt{x}\,\log \log x)$ time as long as you can use a builtin integer type). $\endgroup$ Sep 3, 2020 at 11:23
  • $\begingroup$ (For $10^{15}$, 64-bit integers suffice.) Second, for the inner sum use Dirichlet's trick (hyperbola method), $$T(y) = \sum_{k \leqslant y} \tau(k) = \sum_{k \leqslant y} \biggl\lfloor \frac{y}{k}\biggr\rfloor = 2\sum_{k \leqslant \sqrt{y}} \biggl\lfloor \frac{y}{k}\biggr\rfloor - \lfloor \sqrt{y}\rfloor^2$$ to compute $T(y)$ in $O(\sqrt{y})$ time. That gives an overall time complexity of $$\sum_{n \leqslant \sqrt{x}} O\biggl(\sqrt{\frac{x}{n^2}}\biggr) = O\bigl(\sqrt{x}\,\log x\bigr)\,.$$ If that's not fast enough one can start to optimise. $\endgroup$ Sep 3, 2020 at 11:23
  • $\begingroup$ @DanielFischer Thank you, i corrected the typo. Doh! how I forgot the Dirichlet's trick?! That make it computationally feasible! $\endgroup$
    – jjagmath
    Sep 3, 2020 at 14:45
  • $\begingroup$ I kinda hoped you'd also include the algorithmic suggestions in your answer. $\endgroup$ Sep 3, 2020 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.