# Efficient encoding of integers with constant digit sum

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.

• What do you want to do with the encoded data? Also, if the computation time is really completely irrelevant, then there is no need to store any data: you can recompute everything when you need the data instead of accessing the stored data. Jan 14, 2012 at 13:16
• What I want to do with the data is a long story, but not relevant for this. To day I use a B-tree map to associate a given integer (with const. digit sum) to a sequence number, and the map is then used for decoding. I just thought that this could be done smarter. Jan 14, 2012 at 13:54
• As I said, which operations you want to perform with the data is the integral part of your question. I voted to close as not a real question. Jan 14, 2012 at 14:20
• @TsuyoshiIto: OP writes "computing time is not completely unimportant". And I think the idea here is that we have an arbitrary subset $X$ of integers with a constant digit sum, and hence some storage is needed. In general, I think this is a reasonably good question. In base 2 the question is very closely related to the efficient storage of sparse vectors. Jan 14, 2012 at 16:30
• I had been completely misunderstanding the question. My apologies. And thanks to @Jukka for letting me realize it. Jan 15, 2012 at 23:12

Just omit the last digit.

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

• But if your typical data looks like {"1000002000101000", "100000100000010001001"}, merely encoding it as {"100000200010100", "10000010000001000100"} does not seem to be the most efficient approach. I thing the approach outlined by @ctgPi sounds good, as it actually exploits sparsity. Jan 16, 2012 at 1:21
• Yeah, but the only assumption he gave about his input numbers is that they all have the same digit sum. I assumed that was the point of the question. The more general question "How do I encode integers?" would be out of scope as too vague. Jan 16, 2012 at 8:19

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).

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.

• This is actually the implementation I'm using right now. I just had the feeling that this could be done smarter. Jan 16, 2012 at 14:05

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}$$

• There is something strange about that displayed formula as it is adding only powerr of $b$. I expected to see the digits someplace. For example, why is the leading digit always 1? But otherwise, this might even be optimal. Jan 19, 2012 at 7:19

$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]


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;
• There is no need to enumerate permutations beforehand. You can add permutations to the list as and when you encounter a new one. Jan 18, 2012 at 12:32
• @Pratik: yes, the permutations can be generated dinamically. Jan 18, 2012 at 19:03