# Short expression for the logarithm

Here is a weird trick I learned some time ago. Suppose we want to compute and we know , and are positive integers. It turns out that

So for choices of where , this wacky expression evaluates to :

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

This calls for an explanation. First, letâ€™s assume since if , both sides evaluate to zero under mod . Expanding the right hand side, we get

We are left with a sum of powers of . Under mod , each term becomes so the terms clearly sum to .

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 in Python 2 is `len(bin(x&-x))-3`

. But if we
limit the domain of the function to 62-bit integers, we can shorten it to `(x&-x)**6/63%63`

.