2

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).

Community
  • 1
Thev
  • 391
  • It gives the desired values. Use $p=2, 3$, with $e=2$. – André Nicolas Dec 26 '15 at 03:30
  • $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$. – Andrew Dudzik Dec 26 '15 at 03:32
  • @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? – Thev Dec 26 '15 at 03:34
  • @Slade Thank you. Similiar to what I asked Andre, how do I generalise what values of p and e to use? – Thev Dec 26 '15 at 03:35
  • @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)$. – Andrew Dudzik Dec 26 '15 at 03:36
  • @Slade Makes sense. I'm still a little fuzzy though. Could you maybe explain how I would use this to work out a(5) ? – Thev Dec 26 '15 at 03:38
  • @TheveshTheva $a(5^1) = \frac{2(5^{(1+1)/2}-1)}{5-1} = 2$. – Andrew Dudzik Dec 26 '15 at 03:40
  • @Slade Thank you! I think that's cleared it up for me! – Thev Dec 26 '15 at 03:43

1 Answers1

0

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.

André Nicolas
  • 507,029