# Short expression for the logarithm

Here is a weird trick I learned some time ago. Suppose we want to compute $n=\log_b a$ and we know $n$, $a$ and $b>1$ are positive integers. It turns out that

$n \equiv \left\lfloor\frac{a^k}{b^k-1}\right\rfloor \pmod{b^k-1}$

So for choices of $k$ where $n < b^k-1$, this wacky expression evaluates to $n$:

`a**k/(b**k-1)%(b**k-1)`

This calls for an explanation. First, let’s assume $b^k-1>1$ since if $b^k-1=1$, both sides evaluate to zero under mod $1$. Expanding the right hand side, we get

$\begin{aligned} \left\lfloor\frac{a^k}{b^k-1}\right\rfloor &= \left\lfloor\frac{b^{kn}}{b^k-1}\right\rfloor \\ &= \left\lfloor\frac{b^{kn}-1+1}{b^k-1}\right\rfloor \\ &= b^{k(n-1)}+...+b^k+1+\left\lfloor\frac{1}{b^k-1}\right\rfloor \\ &= \underbrace{b^{k(n-1)}+...+b^k+1}_{n\text{ terms}} \end{aligned}$

We are left with a sum of $n$ powers of $b^k$. Under mod $b^k-1$, each term becomes $1$ so the terms clearly sum to $n$.

Of course, this is a comically inefficient way to compute log and only works for perfect powers. As the title suggests, it has little use outside of code golf. It *is* very short though.

As an example, the shortest expression for $\text{ctz}(x)$$\text{ctz}(x)$, or *count trailing zeroes*, is the number of zeroes after the LSB in the binary representation of $x$, where $\text{ctz}(0)=0$. in Python 2 is

`len(bin(x&-x))-3`

With our new trick, it’s clear that on occasions where `x`

is always small enough, we can further shorten the above expression to

`(x&-x)**6/63%63`