2
$\begingroup$

Question links to paper which states: $$ \sigma(n)= \frac{6}{n^2(n-1)}\sum_{k=1}^{n-1}(3n^2-10k^2)\sigma(k)\sigma(n-k) \qquad (1) $$

where $\sigma(n)$ is the sum of divisors of $n$.

Another similar result from OEIS about Euler totient function: $$ \phi(n)=\sum_{i=1}^n |k(n,i)| \qquad (2) $$

where $k(n,i)$ is the Kronecker symbol.

And

$$ \phi(n) = \operatorname{binomial}(n+1, 2) - \sum_{i=1}^{n-1} \phi(i)\lfloor n/i\rfloor \qquad (3) $$

Observe that the RHS of all of the above doesn't require the factorization of $n$ and in addition (2) doesn't require factorization at all.

We find the (1) and (3) factorization of $n$-free identities counter-intuitive.

Q1 Is there any intuition why such identities exist?

Q2 Are there similar factorization of $n$-free identities for $\omega(n)$ or $\Omega(n)$ (the number of prime factors of $n$) (not counting the generating function)?

$\endgroup$
7
  • 6
    $\begingroup$ There is no reason why identities about $\sigma(n)$ should involve factorization. To begin with, the very definition of $\sigma(n)$ is an identity without factorization. The same goes for $\phi(n)$, but additionally note that the expression in (2) is quite silly: $|k(n,i)|$ is just a funny way of writing the indicator function of coprimality, hence (2) is just an obfuscation of the defining formula $\phi(n)=|\{i\le n:\gcd(n,i)=1\}|$. $\endgroup$ Sep 24, 2020 at 10:29
  • 2
    $\begingroup$ I think the surprising fact is that formula (1) does not involve divisors of $n$. The definition of $\sigma(n)$ does not involve the factorization of $n$, but divisors of $n$. $\endgroup$ Sep 24, 2020 at 11:44
  • 3
    $\begingroup$ There is also Euler's recurrence $$\sigma(n)=\sigma(n-1)+\sigma(n-2)-\sigma(n-5)-\sigma(n-7)+\sigma(n-12)+\sigma(n-15)-\cdots$$ where $1,2,5,7,12,15,\dots$ are the pentagonal numbers. $\endgroup$ Sep 24, 2020 at 13:01
  • 1
    $\begingroup$ @GerryMyerson: you are confusing $\sigma(n)$ with $p(n)$, the number of partitions of $n$. Perhaps you are thinking of $np(n) = \sum_{i=1}^n \sigma(i)p(n-i)$. $\endgroup$ Sep 24, 2020 at 14:16
  • 2
    $\begingroup$ Gerry's comment is almost correct, but you need to set $\sigma(0)=n$ when $n$ is a pentagonal number. $\endgroup$ Sep 24, 2020 at 20:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.