2
$\begingroup$

I have the following summation:

$$F(k)=\sum\limits_{n=1}^k\sum\limits_{d|n}\gcd\left({d},{\frac{n}{d}}\right)$$

At this OEIS link (http://oeis.org/A055155), this exact summation is found. (Credits to Lucian for pointing this out on my previous post here.

They give a formula for it, which is as follows:

Multiplicative:

For even e: $$a(p^e) = {\frac{p^{\frac{e}{2}}(p+1)-2}{p-1}}$$

For odd e: $$a(p^e) = {\frac{2(p^{\frac{e+1}{2}}-1)}{p-1}}$$

Some sample results: a(4) should give 4, a(9) should give 5.

Can anyone get these results using the formula? Or have I interpreted it wrongly?

The way I see it, if calculating a(4), the variable e takes the value of 4, and the variable p takes the value 4^(1/4).

$\endgroup$
8
  • $\begingroup$ It gives the desired values. Use $p=2, 3$, with $e=2$. $\endgroup$ – André Nicolas Dec 26 '15 at 3:30
  • $\begingroup$ $a(4) = a(2^2) = \frac{2^{2/2} (2+1)-2}{2-1} = 4$, $a(9) = a(3^2) = \frac{3^{2/2}(3+1)-2)}{3-1} = 5$. $\endgroup$ – Slade Dec 26 '15 at 3:32
  • $\begingroup$ @André Ah, okay! but for other numbers, how do I know which values of p and e to use? What if the number wasn't a perfect square? $\endgroup$ – Thev Dec 26 '15 at 3:34
  • $\begingroup$ @Slade Thank you. Similiar to what I asked Andre, how do I generalise what values of p and e to use? $\endgroup$ – Thev Dec 26 '15 at 3:35
  • $\begingroup$ @TheveshTheva $p$ is prime. There is at most one way to write $n$ in the form $p^e$. For numbers with more than one prime factor, you use the fact that $a(n)$ is multiplicative, e.g. $a(p^e q^f) = a(p^e)a(q^f)$. $\endgroup$ – Slade Dec 26 '15 at 3:36
0
$\begingroup$

If you want $a(n)$ for general $n\gt 1$, first express $n$ as a product of prime powers, $$n=p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t},$$ where the primes $p_i$ are distinct.

Then use the formulas to find $a(p_i^{e_i})$ for each $i$ separately, with $e=e_i$ and $p=p_i$. Your answer will be $$a(n)=a(p_1^{e_1})a(p_2^{e_2})\cdots a(p_t^{e_t}).$$ This does not go very far towards answering your $F(k)$ problem, for that could be a long unpleasant sum.

$\endgroup$

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.