Break number into units with custom base

Question

It's a really simple question but I don't understand where I'm wrong. Let's say there's an array of numbers A = [a, b, c, d, ...], and each element is in range [0, N). I want to convert this array to a single number (and back), almost like if these elements are digits of a number in base N. So for example, for N == 64:

seq_to_num([0, 0, 0, 0]) == 0
seq_to_num([0, 0, 0, 1]) == 1
seq_to_num([0, 0, 1, 0]) == 64
seq_to_num([63, 63, 63, 63]) == 64**4 - 1

num_to_seq(67, 4) == [0, 0, 1, 3]

Bruteforce solution is to have smth like

import itertools

def seq_to_num(seq):
    for i, c in enumerate(itertools.product(range(BASE), repeat = 4)):
        if c == seq:
            return i

But it's quite an overkill to use iteration here in my opinion. And for reversing the number I would need to keep an array of combinations and things get pretty ugly.

I know it's super trivial, but I'm getting wrong numbers. Here's my code:

BASE = 64

def seq_to_num(seq):
    size = len(seq)

    return sum([pow(BASE, size - i) * digit for i, digit in enumerate(seq)])

def num_to_seq(num, places):
    seq = [0] * places

    while num != 0:
        num, rem = divmod(num, BASE)

        seq.insert(0, rem)

    return reversed(seq)

What am I missing?

Should you be iterating the sequence in reverse? `enumerate(seq[::-1])`? — wwii, Jul 20 '22 at 00:39
I think `seq_to_num([64, 64, 64, 64])` isn't `64 ** 4`. It should be `64 ** 4 + 64 ** 3 + 64 ** 2 + 64`. — minolee, Jul 20 '22 at 00:41
Each element will be in the range [0,N-1] presumably, rather than [0,N], if this is base N. — jarmod, Jul 20 '22 at 00:48
I've updated the description and math to better reflect what's going on — user37741, Jul 20 '22 at 00:55
`sum([pow(BASE, i) * digit for i, digit in enumerate(seq[::-1])])` — wwii, Jul 20 '22 at 00:57

Shane Schrute · Answer 1 · 2022-07-20T03:12:40.547

seq_to_num is as easy as iterating over the list and summing the value at each position. Given A and N as defined above, this can be done like:

def seq_to_num(A, N):
    return sum([a * (N ** idx) for idx, a in enumerate(A[::-1])])

Reversing is trickier. The inputs you're defining for num_to_seq aren't sufficient to reverse it, you need to use the base N and the current number trying to reverse num:

from math import floor, log

def num_to_seq(num, N):
    aggregator = 0
    array = []
    for idx in range(int(log(num)/log(N)) + 1):
        current = floor((num - aggregator) / (N ** idx)) % N
        array.append(current)
        aggregator += current * (N ** idx)
    return array[::-1]

What this essentially does is divide out the portion of the number that hasn't been calculated yet by the current base index and takes the portion of that which falls within the [0, N) range as the current digit, then subtracts the value of the current digit from what is left to calculate.

You can calculate ahead of time that a number num in base N will require no more than first whole integer greater than log_N(num) to complete. You get this by solving num < N^idx for idx.

Essentially, it will brute force the digits until it's captured all of the digits. It's not pretty, but it works.

You can verify that they are inverses of each by calling them nested and comparing the output vector with the input vector. A script similar to below will return an AssertionError if they aren't inverses of each other:

N = 15
A = [2,1,14,0]
assert A == num_to_seq(seq_to_num(A, N), N)

N = 64
A = [63,63,63,63]
assert A == num_to_seq(seq_to_num(A, N), N)

# etc

Break number into units with custom base

1 Answers1