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 :
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