# need a function

Jack Brennen jb at brennen.net
Sat Jun 14 09:26:46 CEST 2008

```If you're permitted a lookup table of size 32, just use TAB[n%37];
I'm sure you can figure out how to fill in TAB[].  (The value of
the function for non-powers-of-two will be pretty much useless,
but if you know the input is a power of two, it works good.

n%37 can be written as n-(n/37)*37, if / throws away the remainder.

If you don't require the function to be "small":

f(n) = (n/2)%2+
(n/4)%2+
(n/8)%2+
(n/16)%2+
...+
(n/2^30)%2+
(n/2^31).

Use the substitution a%b = a-(a/b)*b.

(Again, assuming that / throws away the remainder.)

Brendan McKay wrote:
> Hi seqfans.  This little problem might amuse someone and the answer
> might even be useful.
>
> We are considering arithmetic in the non-negative integers mod 2^32.
> The problem is, define a function f(n) using only +-*/ (where / throws
> away the remainder) such that f(2^i) = i for i=0,1,...,31.
>
> If that is too onerous, you can also use bit-wise boolean operations.
>
> The corresponding problem for 2^64 is also of interest.
>
> Cheers, Brendan.
>
>

```