In these recent posts, I have been talking about hunting for functions with certain properties. I decided to try an exhaustive search of a particular function space to find the functions I was looking for, by identifying a 1:1 relationship between numbers and functions, then iterating through all of the numbers and testing the corresponding function.

In brief, I treated the number as an efficient encoding of the truth table for the function. By "efficient", I mean I used an encoding system in which every number in the range represented a valid and distinct truth table, and all possible functions were represented in the range. Since I'm talking about functions that operate on discrete, finite sets of values, the number of truth tables is finite.

First, I used a system I came up with a while ago to represent permutations as numbers. I originally devised this as a way to encode every possible shuffled state of a deck of cards, but it really works for any permutation. Encode the permutation

**f**_{a} as follows:

**R**_{p}**(****f**_{a}**) = N! (****f**_{a:0}**(0)/N! + ****f**_{a:1}**(1)/(N-1)! + ****f**_{a:2}**(2)/(N-2)! ... ****f**_{a:3}**(N-1)/1!)**
Where

**f**_{a:n} returns the zero-based index of

**f**_{a}(n) within the ordered set of values returned by

**f**_{a}(x) where

**x >= n**.

So, for example, the permutation

**f**_{a}**(x) = x + 2 (modulo 4)** can be represented as the number

**10**. Here's how the encoding works:

**f**_{a:0 }returns the zero-based index of

**f**_{a}(0) in the set [0, 1, 2, 3]. That is, it returns 2, since

**f**_{a}(0) = 2, and 2 is found at position 2 in the set.

**f**_{a:1 }returns the zero-based index of

**f**_{a}(1) in the set [0, 1, 3]. That is, it returns 2, since

**f**_{a}(1) = 3, and 3 is found at position 2 in the set.

**f**_{a:2 }returns the zero-based index of **f**_{a}(2) in the set [0, 1]. That is, it returns 0, since **f**_{a}(2) = 0, and 0 is found at position 0 in the set.

**f**_{a:3 }returns the zero-based index of **f**_{a}(3) in the set [1]. That is, it returns 0, since **f**_{a}(3) = 1, and 1 is found at position 0 in the set.

So:

**R**_{p}**(λx → x + 3) = 4! (2/4! + 2/3! + 0/2! + 0/1!) = 10**
In my last post, I treated the function

**f(a, b)** as selecting permutation

**f**_{a} from an indexed set, and applying it to value

**b**. The

**N** permutations required for distinct values of

**a** can all be encoded together in a single number, as follows:

**R**_{f}**(****f****) = R**_{p}**(f**_{0}**)(N!)**^{0} + **R**_{p}**(f**_{1}**)(N!)**^{1}** + ... + ****R**_{p}**(f**_{N-1}**)(N!)**^{N-1}

So the function

**f(x, y) = x + y (modulo 4)** can be encoded as follows, given that

**R**_{p}(f_{0}) = 0, R_{p}(f_{1}) = 1, R_{p}(f_{2}) = 10, R_{p}(f_{3}) = 3.

**R**_{f}**(λx, y → x + y) = 0(4!)**^{0}** + ****1(4!)**^{1}** + 10****(4!)**^{2}** + ****3(4!)**^{3}** = 0 + 24 + 5760 + 41472 = 47256**

For my function-space exploration, I simply reversed this process for each number to generate the truth table, and I used the truth table to test for the properties I was looking for. However, for the fun of it, here is how you would apply the function to a set of values. Given the function above, you would apply it to the values 2 and 3 as follows:

**R**_{p}**(f**_{2}**) = floor(R**_{f}(f) / (4!)^{2}) % 4! = floor(47256 / 576) % 4 = 10

**f**_{2:0}**(0) = floor(4! ****R**_{p}**(f**_{2}**) / 4!)**** % 4 = 2**, therefore **f**_{2}**(0) = 2** (i.e. zero-indexed value 2 from [0, 1, 2, 3])

**f**_{2:1}**(1) = floor(3! ****R**_{p}**(f**_{2}**) / 4!) % 3 = **** 2**, therefore **f**_{2}**(1) = 3** (i.e. zero-indexed value 2 from [0, 1, 3])

**f**_{2:2}**(2) = floor(2! ****R**_{p}**(f**_{2}**) / 4!) % 2 = **** 0**, therefore **f**_{2}**(2) = 0** (i.e. zero-indexed value 0 from [0, 1])

**f**_{2:3}**(3) = floor(1! ****R**_{p}**(f**_{2}**) / 4!) % 1 = **** 0**, therefore **f**_{2}**(3) = 1** (i.e. zero-indexed value 0 from [1])

So **2 + 3 (modulo 4) = 1**.

The looooooong way.