This site is supported by donations to The OEIS Foundation.

# User:Daniel Suteu

Open-source software developer, with main interests in programming languages, algorithms, mathematics (number theory), poetry and science.

In March 2013, I started the Sidef programming language project, which combines many good things from good languages, trying to make programming easier and more enjoyable, focusing primarily on simplicity, elegance and readability.

Among other things, the language comes with fast built-in methods for primality testing and prime factorization, along with many other number-theoretic functions, most of them provided by Dana Jacobsen's excellent Math::Prime::Util::GMP module. Also built-in, we have support for arbitrary large integers, rationals, floats and complex numbers, using the GMP, MPFR and MPC libraries.

The language can be tried online at: https://tio.run/#sidef.

WWW:

## Partial sums of arithmetical functions

For any arithmetical function ${\displaystyle f(k)}$, we have the following identity for m>=0:

${\displaystyle \sum _{k=1}^{n}\sum _{d|k}f(d)(k/d)^{m}=\sum _{k=1}^{n}f(k)\sum _{j=1}^{\left\lfloor n/k\right\rfloor }j^{m}=\sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

where ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials, defined as:

${\displaystyle F_{n}(x)={\frac {B_{n+1}(x+1)-B_{n+1}(1)}{n+1}}}$

where ${\displaystyle B_{n}(x)}$ are the Bernoulli polynomials. The Faulhaber polynomials are particularly useful in efficiently summing the m-th powers, for m >= 0, of the first n positive integers:

${\displaystyle \sum _{k=1}^{n}k^{m}=F_{m}(n)}$

...and are also useful in efficiently computing second partial sums of m-th powers (sums of power sums), for m >= 0:

${\displaystyle \sum _{k=1}^{n}\sum _{j=1}^{k}j^{m}=(n+1)F_{m}(n)-F_{m+1}(n)}$

In this section, we're interested in computing the following partial sum in sublinear time, for m>=0, where ${\displaystyle f(k)}$ is an arithmetic function:

${\displaystyle \sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

If the partial sums of ${\displaystyle f(k)}$ can be computed efficiently:

${\displaystyle S(n)=\sum _{k=1}^{n}f(k)}$

then we can create the following sublinear formula:

${\displaystyle \sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )=\sum _{k=1}^{\left\lfloor {\sqrt {n}}\right\rfloor }F_{m}(k)(S(\left\lfloor n/k\right\rfloor )-S(\left\lfloor n/(k+1)\right\rfloor ))+\sum _{k=1}^{\left\lfloor n/(\left\lfloor {\sqrt {n}}\right\rfloor +1)\right\rfloor }f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

More generally, the partial sums over the Dirichlet convolution of two arithmetic functions ${\displaystyle f}$ and ${\displaystyle g}$, can be computed in sublinear time, if the individual partial sums of ${\displaystyle f}$ and ${\displaystyle g}$ can be computed efficiently:

${\displaystyle R(n)=\sum _{k=1}^{n}f(k)}$

${\displaystyle S(n)=\sum _{k=1}^{n}g(k)}$

Assuming that ${\displaystyle R(n)}$ and ${\displaystyle S(n)}$ can be computed efficiently, then we can use the Dirichlet hyperbola method to compute the following partial sum in sublinear time:

${\displaystyle \sum _{k=1}^{n}\sum _{d|k}f(d)g(k/d)=\sum _{k=1}^{\left\lfloor {\sqrt {n}}\right\rfloor }(f(k)S(\left\lfloor n/k\right\rfloor )+g(k)R(\left\lfloor n/k\right\rfloor ))-R(\left\lfloor {\sqrt {n}}\right\rfloor )S(\left\lfloor {\sqrt {n}}\right\rfloor )}$

## Partial sums of the sigma function

For m >= 0 and j >= 0, we have:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)=\sum _{k=1}^{n}k^{m+j}F_{m}(\left\lfloor n/k\right\rfloor )=\sum _{k=1}^{n}k^{m}F_{m+j}(\left\lfloor n/k\right\rfloor )}$

which can be computed in sub-linear time by using the Dirichlet hyperbola method:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)=\sum _{k=1}^{\lfloor {\sqrt {n}}\rfloor }(k^{m}F_{m+j}(\left\lfloor n/k\right\rfloor )+k^{m+j}F_{m}(\left\lfloor n/k\right\rfloor ))-F_{m+j}(\left\lfloor {\sqrt {n}}\right\rfloor )F_{m}(\left\lfloor {\sqrt {n}}\right\rfloor )}$

where ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials.

An asymptotic approximation to this partial sum, with m >= 0 and j >= 1, is given by the following formula:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)\sim {\frac {\zeta (j+1)n^{j+m+1}}{j+m+1}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the Jordan totient function

The Jordan totient function is a generalization of the Euler's totient function, and is defined as:

${\displaystyle J_{m}(n)=n^{m}\prod _{p|n}(1-1/p^{m})}$

and is multiplicative with:

${\displaystyle J_{m}(p^{k})=p^{km}-p^{(k-1)m}}$

An elegant formula for computing partial sums of the Jordan totient function, is given in terms of the Möbius function and the Faulhaber polynomials:

${\displaystyle \sum _{k=1}^{n}J_{m}(k)=\sum _{k=1}^{n}\mu (k)F_{m}(\left\lfloor n/k\right\rfloor )}$

An asymptotic approximation to this partial sum, with m >= 1, is given as:

${\displaystyle \sum _{k=1}^{n}J_{m}(k)\sim {\frac {n^{m+1}}{(m+1)\zeta (m+1)}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the Dedekind psi function

The generalized Dedekind psi function can be defined in terms of the Jordan totient function, as:

${\displaystyle \psi _{m}(n)={\frac {J_{2m}(n)}{J_{m}(n)}}}$

and is multiplicative with:

${\displaystyle \psi _{m}(p^{k})=p^{km}+p^{(k-1)m}}$

Partial sums of the Dedekind psi function can be expressed in terms of the absolute value of the Möbius function and the Faulhaber polynomials:

${\displaystyle \sum _{k=1}^{n}\psi _{m}(k)=\sum _{k=1}^{n}|\mu (k)|F_{m}(\left\lfloor n/k\right\rfloor )}$

with the following asymptotic approximation for m >= 1:

${\displaystyle \sum _{k=1}^{n}\psi _{m}(k)\sim {\frac {n^{m+1}\zeta (m+1)}{(m+1)\zeta (2(m+1))}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the omega(n) and bigomega(n) functions

We define the generalized ${\displaystyle \omega _{m}(n)}$ and ${\displaystyle \Omega _{m}(n)}$ functions as:

${\displaystyle \omega _{m}(n)=\sum _{p^{k}|n}{\frac {n^{m}}{p^{m}}}}$

${\displaystyle \Omega _{m}(n)=\sum _{p^{k}|n}\sum _{j=1}^{k}{\frac {n^{m}}{p^{jm}}}}$

where ${\displaystyle p^{k}}$ are primes ${\displaystyle p}$ dividing ${\displaystyle n}$, with multiplicity ${\displaystyle k}$.

For ${\displaystyle \omega _{m}(n)}$ we have the following sequences:

${\displaystyle \omega _{0}(n)=}$ A001221(n)

${\displaystyle \omega _{1}(n)=}$ A069359(n)

${\displaystyle \omega _{2}(n)=}$ A322078(n)

Similarly, for ${\displaystyle \Omega _{m}(n)}$, we have:

${\displaystyle \Omega _{0}(n)=}$ A001222(n)

${\displaystyle \Omega _{1}(n)=}$ A095112(n)

${\displaystyle \Omega _{2}(n)=}$ A322664(n)

Partial sums of this functions can be expressed in terms of the Faulhaber polynomials, as:

${\displaystyle \sum _{k=1}^{n}\omega _{m}(k)=\sum _{p}^{n}F_{m}(\left\lfloor n/p\right\rfloor )}$

${\displaystyle \sum _{k=1}^{n}\Omega _{m}(k)=\sum _{p^{k}}^{n}F_{m}(\left\lfloor n/p^{k}\right\rfloor )}$

where ${\displaystyle p}$ and ${\displaystyle p^{k}}$ (with k>=1) run over the prime numbers and the prime powers, respectively, less than or equal to ${\displaystyle n}$.

For m>=1, the partial sums of ${\displaystyle \omega _{m}(k)}$ can be described asymptotically as:

${\displaystyle \sum _{k=1}^{n}\omega _{m}(k)\sim F_{m}(n)P(m+1)}$

where ${\displaystyle F_{m}(n)}$ are the Faulhaber polynomials and ${\displaystyle P(s)}$ is the Prime zeta function, defined as:

${\displaystyle P(s)=\sum _{p}{\frac {1}{p^{s}}}}$

Very similarly, for m>=1, the partial sums of ${\displaystyle \Omega _{m}(k)}$ satisfy:

${\displaystyle \sum _{k=1}^{n}\Omega _{m}(k)\sim F_{m}(n)Q(m+1)}$

where ${\displaystyle F_{m}(n)}$ are the Faulhaber polynomials and ${\displaystyle Q(s)}$ is defined as:

${\displaystyle Q(s)=\sum _{k=1}^{\infty }\sum _{p}{\frac {1}{p^{sk}}}=\sum _{p}{\frac {1}{p^{s}-1}}}$

where ${\displaystyle p}$ runs over the prime numbers.

## Partial sums - OEIS sequences

Considering the following partial sum, where ${\displaystyle f(k)}$ is an arithmetic function and ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials:

${\displaystyle R_{m}(n)=\sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

gives us the following table of interesting sequences:

+------------+------------+------------+
|    f(k)    |   R_0(n)   |   R_1(n)   |
+------------+------------+------------+
| A000012(k) | A006218(n) | A024916(n) |
| A000027(k) | A024916(n) | A143127(n) |
| A010051(k) | A013939(n) | A322068(n) |
| A008966(k) | A064608(n) | A173290(n) |
| A008683(k) | A000012(n) | A002088(n) |
| A000290(k) | A064602(n) | A143128(n) |
| A000010(k) | A000217(n) | A272718(n) |
| A034444(k) | A061503(n) | A306775(n) |
| A007434(k) | A000330(n) |            |
| A069513(k) | A022559(n) |            |
+------------+------------+------------+


## Generalized Pillai arithmetical function

For any arithmetic function ${\displaystyle f(k)}$, we have the following identity:

${\displaystyle \sum _{k=1}^{n}f(gcd(n,k))=\sum _{d|n}f(d)\phi (n/d)}$

where ${\displaystyle \phi (x)}$ is the Euler totient function.