Efficient encoding of integers with constant digit sum

Question

How can a large set of integers all with a known constant digit sum be encoded?

Example of integers in base 10, with digit sum 5:

14, 41, 104, 113, 122, 131, 140, 203 ....

The most important factor is space, but computing time is not completely unimportant.

Answer 1

Just omit the last digit.

(Extra text to get over the 30-chaacter minimum.)

Answer 2

What about writing each number as a sum of powers of 10 (or whatever is the base for your problem) in ascending order and then delta-encode the exponents with some universal code? You might need to nudge the deltas since most codes start with '1', but if you use e.g. Levenstein coding to encode 122:

122 = 10^0 + 10^0 + 10^1 + 10^1 + 10^2

The exponent tuple is (0, 0, 1, 1, 2), and the deltas (pretend there's an extra 0 at the beginning of the sequence) are (0, 0, 1, 0, 1), so this encodes as "0010010" binary. You might want to encode somewhere (beginning of the sequence?) what are the base and sum of the digits, though.

This has a minor inefficiency in that you will never see nine consecutive zero deltas. If you're that desperate for space, you can stipulate that if a zero delta would cause a digit overflow, one is subtracted from it during encoding (and added to it during decoding). For instance, 19 would be encoded as (0 * 9, 0), not (0 * 9, 1).

Answer 3

Simple idea, but fits problem statement. I propose following encoding:

Pair of integers: $(S, N)$

Where

• $S$ - desired sum
• $N$ - place of number in sorted sequence of all possible positive integers with desired sum of digits.

For your example sequence of integers with sum=5 :

(5,1) = 5
(5,2) = 14
(5,3) = 23
(5,4) = 32
(5,5) = 41
(5,6) = 50
(5,7) = 105
(5,8) = 114
...

As you stated, that complexity is not important, you can even enumerate all integers and count those fitting given sum, once you find n-th you are done. Of course it's brute-force approach, just as proof of concept of encoding. For sure you can make searching for "n-th" number much more efficient (but as it is not part of your question and complexity is not important, I will not elaborate).

To be more specific, you might ask: "Pair of integers - how to encode those integers?"

You can choose integer encoding as you like. Examples: Fixed length 64bit, Prefix code generated with Huffman encoding, etc.

P.S. I assumed from your example sequence, you mean numbers greater than zero.

Answer 4

Let's say you are dealing with numbers in base $b$ with up to $n$ digits whose digit values sum to $M$. To encode a number $N$ of length $l = \lfloor \log_b N \rfloor + 1 \leq n$, just create a bit vector of length $\log n + (M - 1)\log l$.

The first $\log n$ bits of the vector tell you how many digits $N$ has. The second $l$ bits tell you the position $p$ (from the right) of the first not-zero bit. The subsequent $M - 2$ blocks of $log l$ bits tell you offsets $d_i$ for $1 \leq i \leq M - 2$. You use these offsets to reconstruct the number quickly, as:

$$ N = b^{l - 1} + b^{p} + \sum_{1 \leq i \leq M - 2} b^{p + \sum_{1 \leq j \leq i} d_i} $$

Answer 5

$X = \{\{0,5\}, \{1,4\}, \{1,1,3\}, \{1,1,1,2\}, \{1,1,1,1,1\}, \{2,3\}, \{2,2,1\} \}$

$X$ is partition of 5 where only single digit numbers are allowed.

Observation:
Any number with digit sum 5 can be represented by permutation of one of the above sets stuffed with 0s.

Example:

$\begin{eqnarray*} 14 \rightarrow 10^040^0 \rightarrow 14:0,0\\ 104 \rightarrow 10^{1}40^0 \rightarrow 14:1,0\\ 10000000000004 \rightarrow 10^{12}40^0 \rightarrow 14:12,0\\ 100040000000000000000 \rightarrow 10^{3}40^{16} \rightarrow 14:3,16 \end{eqnarray*}$

All these four numbers can be stored in a dictionary with 14 as key and list of number of zeros to stuff between each non-zero digits.

{
14: [
      [0,0],
      [1,0],
      [12,0],
      [3,16]
    ]
}

Space savings:

$log_{10}$ roughly computes length of a number in base 10. If you store a number N, as a string then $L \approx \log_{10}N$ bytes are required (assuming 1 byte per char).

But if we use representation of numbers given above then approximate number of bytes needed are $\approx \log_{10}L$. Reason for this is lots of zeros in the number.

$$space \ savings \approx 1 - \frac{log_{10} \ L}{L} = 1-\frac{log_{10}\ log_{10} \ N}{log_{10}\ N}$$

Python Code:

d = {} 
def insert(n):
        key, xs = '', []
        for x in n:
                if x is not '0':
                        key += x
                        xs += [0]
                else:
                        xs[-1] += 1

        if not key in d.keys():
                d[key] = []
        d[key] += [xs]

Answer 6

LAST EDIT: just a refinement of the previous answer.

Suppose you have $n$ numbers, the digits must sum to $k$.

First enumerate the permutations of the digits that sum to $k$, merged with the combinations of non-empty 0 subsequences; for example, if $k=5$:

 0: 5      1: 5z
 2: 23     3: 23z     4: 2z3    5: 2z3z
 6: 32     7: 32z     8: 3z2    9: 3z2z
 ...
 __: 11111  __: 11111z ......   ___: 1z1z1z1z1z

 (z means: non-empty zero sequence)

We can represent a single number $v$, with the corresponding index $I(v)$ in the above enumeration plus the lengths of the non-empty interleaving 0 sequences.

For example:

v = 2 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0
      +-seq1--+   +seq2-+   +--seq3-----+
       |seq1|=5   |seq2|=4    |seq3|=7
I(v) = 2z1z2z
v can be represented with (2z1z2z,(5,4,7))
( "2z1z2z" should be replaced with the entry number of 2z1z2z in the permutation table)

We can group the $n$ values $v_i$ of the set according to $I({v_i})$.

set: [ 2300, 10112, 100112, 2003000, 2000300000 ]

representation: [ 23z:[[2]], 1z112:[[1],[2]], 2z3z:[[2,3],[3,5] ]

We can gain more space if we add a lookup-table of the most frequent 0 (non contiguous) subsequences ( 0_0, 0_0_0, ...):

set: [ 2300, 100112, 100110002,  2003000, 2000300000, 3000200000 ]

representation:
zero-sequences-table: [ h1:[2,3], h2:[3,5] ]
encoded-set: [23:[2], 1z112:[2,h1], 2z3z:[h1,h2], 3z2z:[h2]]

Note:

• the numbers with few digits should be left unencoded;
• as noted by Pratik both the permutation table and the zero-sequences-table can be generated dinamically;