*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!

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

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.

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}$

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

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 |

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.