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 , or count trailing zeroes, is the number of zeroes after the LSB in the binary representation of , where . in Python 2 is
With our new trick, it’s clear that on occasions where
x is always small enough, we can further shorten the above expression to