Efficient computation of ratios between divisor sums

Jon Maiga, 2018-12-10

During the development of sequencedb.net I kept on encountering bitwise formulas that matched sequences involving ratios of divisor sums. I couldn’t fully understand why, so in this article I examine the ratio between the divisor sum, $\sigma$, and its relation to bitwise operations. Specifically I show that

$r_\sigma(k,n)=\frac{\sigma(2^kn)}{\sigma(n)}=\frac{xor(2^kn, 2^kn-1)}{xor(n,n-1)}\text{ where }k \in \mathbb{N}$

To be clear, using bitwise operations for this purpose is not new (see oeis.org entries below), but I couldn’t find any good explanation or a general formula. So here goes!

Divisor sum

Let’s start with a brief introduction to divisor sum.

A000203 a(n)=sigma(n), the sum of the divisors of n.

1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60,

I’ll use the sigma sign $\sigma(n)$ to denote the sum of divisors of $n$. The divisor sum is exactly what it sounds like, sum up all divisors of a number inclusive itself and one.

$\sigma(1)=1=1$
$\sigma(2)=2+1=3$
$\sigma(3)=3+1=4$
$\sigma(4)=4+2+1=7$
$\sigma(5)=5+1=6$
$\sigma(6)=6+3+2+1=12$
$\sigma(7)=7+1=8$
$\sigma(8)=8+4+2+1=15$

We will examine ratios between divisor sums such as if we know $\sigma(n)$ can we directly calculate $\sigma(an)$ without explicitly summing divisors? It turns out we can, at least for any $a=2^k$.

Highest power of 2 dividing n

Before we start looking on the ratios between divisor sums let’s establish some relations.

A006519 Highest power of 2 dividing n.

1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4,…

Let capital $P_2(n)$ be the highest power of two dividing n.

Odd numbers doesn’t have any 2 as divisor, therefore every odd $n$ in the sequence is 1. Some examples

$P_2(3)=2^0=1$
$P_2(5\cdot2)=2^1=2$
$P_2(3\cdot2\cdot2)=2^2=4$
$P_2(2\cdot2\cdot2\cdot2)=2^4=16$

Since the binary system uses the power of two, we can find $P_2(n)$ using the bitwise trick

$P_2(n)=and(n,-n)$

This works on systems that use two’s complement to represent negative numbers. The two’s complement $*n=2^{BITS}-n$, or equivalently $*n=\tilde n+1$, where $\tilde n$ is bitwise negation (flip all the bits).

After negation, the bits of $n$ and $\tilde n$ are disjoint. Then $\tilde n + 1$ will cause 1 bit overlap at the lowest zero of $\tilde n$ (the binary addition will negate any 1’s on the way) - this is the lowest 1 in $n$ which represents the highest power of 2 dividing $n$. The and operation will mask this bit out.

Example, using 8 bits and $n=28$, the overlapping boxed lowest bit gets masked out

op	binary
$n$	$00011\fbox100_2$
$\tilde n$	$11100011_2$
$-n=\tilde n + 1$	$11100\fbox100_2$
$and(n,-n)$	$00000100_2$

Another way of calculating $P_2(n)$ without taking the complement is to use $xor$

$P_2(n)=\frac{xor(n, n-1)+1}{2}$

We use the same example, $n=28$ to get a feel of how it works

op	binary
$n$	$00011100_2$
$n-1$	$00011011_2$
$xor(n,n-1)$	$00000111_2$
$xor(n,n-1)+1$	$00001000_2$
$\frac{xor(n,n-1)+1}{2}$	$00000100_2$

Using $xor$ requires a few more operations than $and$ but the reason I’m mentioning it is because it comes in very handy when we calculate the divisor sum of $P_2(n)$.

As a note, $2^kP_2(n) = P_2(2^kn)$ holds. If we think of multiplication by two as left shifts (pretty common back in the days for optimization purposes), it doesn’t matter if we shift the lowest bit $k$ steps before or after we find the highest power of 2 dividing $n$ (lowest set bit) - in both cases it has moved $k$ steps to the left.

Since $P_2(n)$ is a power of two, taking $log_2(P_2(n))=log_2(2^k)=k$ will give us the exponent, $k$ of the highest power dividing n.

Now let’s connect this with the divisor sum starting with $\sigma(P_2(n))$ and the example, $\sigma(16)=1+2+4+8+16=2^5-1$

The sum of all power of two divisors up and including $P_2(n)$ equals $2^{log_2(P_2(n))+1}-1=2\cdot2^{log_2(P_2(n))}-1=2\cdot P_2(n)-1$.

$\sigma(P_2(n))=2P_2(n)-1$

Finally recalling the relationship between $P_2(n)$ and $xor$ we conveniently arrive at

$\sigma(P_2(n))=xor(n,n-1)$

For example $\sigma(16)=16+8+4+2+1=2\cdot16-1=xor(16, 15)=31$. See the binary example above to understand why this work, after the $xor$ operation all bits are set up until, and including, the highest power of 2 dividing $n$ - which equal the sum of divisors.

Ratios between divisor sums

Using the given identities we can effectively find ratios between divisor sums as long as the ratios between $n$ is a power of two. For example the ratio between the $n$ in $\frac{\sigma(2n)}{\sigma(n)}$ is $2^1$, $\frac{\sigma(4n)}{\sigma(n)}$ is $2^2$ and also for negative powers, $\frac{\sigma(n)}{\sigma(8n)}$ where the ratio is $2^{-3}$.

Lets introduce a new function, the sigma ratio function

$r_\sigma(k,n)=\frac{\sigma(2^kn)}{\sigma(n)}\text{ where }k \in \mathbb{N}$

What is pretty neat is that we can calculate $r_\sigma(k,n)$ without involvement of the traditional $\sigma$ function. Instead we can solely rely on the computationally cheap bitwise operation $xor$.

Let’s start with an example for $k=1$ and $n=28$.

$r_\sigma(1, 28)=\frac{\sigma(2^1 28)}{\sigma(28)}=\frac{\sigma(2^3 7)}{\sigma(2^2 7)}=\frac{\sigma(2^3)\sigma(7)}{\sigma(2^2)\sigma(7)}=\frac{\sigma(2^3)}{\sigma(2^2)}=\frac{15}{7}$

Since the $\sigma$ function is multiplicative we may cancel the part that is not a power of two, $\sigma(7)$ and we are only left with the divisor sum of power of twos. We can generalize this as

$r_\sigma(k,n)=\frac{\sigma(2^kn)}{\sigma(n)}=\frac{\sigma(2^k P_2(n))}{σ(P_2​(n))}=\frac{\sigma(P_2(2^kn))}{σ(P_2​(n))}$

Recall from the previous section that

$\sigma(P_2(n))=2P_2(n)-1=xor(n,n-1)$ Substituting this yields our final form

$r_\sigma(k, n)=\frac{xor(2^kn, 2^kn-1)}{xor(n,n-1)}\text{ where }k \in \mathbb{N}$

Application

Lets try with $k=2$ which is a ratio of $4$

$n$	$\sigma(n)$	$\sigma(4n)$	$r_\sigma(2, n)$
1	1	7	7/1
2	3	15	5/1
3	4	28	7/1
4	7	31	31/7
5	6	42	7/1
6	12	60	5/1
7	8	56	7/1
8	15	63	21/5
9	13	91	7/1

It works!

I am not sure what practical applications this formula may have but maybe it’s useful to be able quickly find $\sigma(2^kn)$ if you already know $\sigma(n)$, if so you just rearrange $\frac{\sigma(2^kn)}{\sigma(n)}=r_\sigma(k, n)$ into

$\sigma(2^kn)=\sigma(n)\cdot r_\sigma(k, n)$

Identities

Here is a small collection of some bitwise identities that may be helpful.

identity	oeis	sequence
$and(n,-n)$	A006519 Highest power of 2 dividing n.	1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16
$log_2(and(n,-n))$	A007814 Exponent of highest power of 2 dividing n	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4
$log2​(and(n,−n))+1$	A001511 The ruler function: 2^a(n) divides 2n. Or, a(n) = 2-adic valuation of 2n.	1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5
$2and(n,-n)=-xor(n,-n)$	A171977 a(n) = 2^(k+1) where 2^k is the highest power of 2 dividing n.	2, 4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2, 32
$σ(and(n, -n))=2and(n,-n)-1=xor(n, n-1)$	A038712 Let k be the exponent of highest power of 2 dividing n	1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31

Sequences with ratios

ratio	numerator	denominator
$\frac{\sigma(2n)}{\sigma(n)}$	A088837 3, 7, 3, 15, 3, 7, 3, 31, 3, 7, 3, 15, 3, 7, 3, 63	A038712 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31
$\frac{\sigma(4n)}{\sigma(n)}$	A088839 7, 5, 7, 31, 7, 5, 7, 21, 7, 5, 7, 31, 7, 5, 7, 127	A088840 1, 1, 1, 7, 1, 1, 1, 5, 1, 1, 1, 7, 1, 1, 1, 31
$\frac{\sigma(8n^2)}{\sigma(4n^2)}$	A065915 15, 63, 15, 255, 15, 63, 15, 1023, 15, 63, 15, 255, 15, 63, 15, 4095	A065916 7, 31, 7, 127, 7, 31, 7, 511, 7, 31, 7, 127, 7, 31, 7, 2047,

Written with StackEdit.