Template:Zhegalkin matrix/triangle Pi compressed

From testwiki
Jump to navigation Jump to search

Template:Collapsible START

These integers encode the columns of a bottom left Sierpiński triangle in a square matrix.
These are vectors of Walsh permutations, so T(n,k)=Πn(2k).

0         1
1         3,     2
2        15,    10,    12,     8
3       255,   170,   204,   136,   240,   160,   192,   128
4     65535, 43690, 52428, 34952, 61680, 41120, 49344, 32896, 65280, 43520, 52224, 34816, 61440, 40960, 49152, 32768

Template:Collapsible START

The function arity_and_atom_to_integer creates entries of Template:Oeislink.

def arity_and_atom_to_integer(arity, atom):
    result = 0
    max_place = (1 << arity) - (1 << atom) - 1
    for exponent in range(max_place + 1):
        if not bool(~max_place & max_place - exponent):
            place_value = 1 << exponent
            result += place_value
    return result


def arity_to_vector_of_zhegalkin_permutation(arity):

    degree = 2 ** arity
    atom_integers = [arity_and_atom_to_integer(arity, atom) for atom in range(arity)]

    vector = []

    for i in range(degree):
        entry = 2 ** degree - 1
        for key, val in enumerate(f'{i:b}'):
            if val == '1':
                entry &= atom_integers[key]
        vector.append(entry)

    return vector


assert [arity_to_vector_of_zhegalkin_permutation(3) == [255, 170, 204, 136, 240, 160, 192, 128]]

Template:Collapsible END Template:Collapsible END