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

n≡⌊akbk−1⌋(modbk−1)n \equiv \left\lfloor\frac{a^k}{b^k-1}\right\rfloor \pmod{b^k-1}

So for choices of kk where n<bk−1n < b^k-1, this wacky expression evaluates to nn:

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

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

⌊akbk−1⌋=⌊bknbk−1⌋=⌊bkn−1+1bk−1⌋=bk(n−1)+...+bk+1+⌊1bk−1⌋=bk(n−1)+...+bk+1⏟n terms \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 nn powers of bkb^k. Under mod bk−1b^k-1, each term becomes 11 so the terms clearly sum to nn.

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 ctz(x)\text{ctz}(x)ctz(x)\text{ctz}(x), or count trailing zeroes, is the number of zeroes after the LSB in the binary representation of xx, where ctz(0)=0\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