3
$\begingroup$

I want to optimise some subtask and I'm not good enough in math.
Given: There are ticket numbers with $k$ digits from 0 to 9. Let $n$ is sum of digits for the ticket number.
Needed: calculate count for all possible $n$ from 0 to $9*k$. I can do it with brute force with $O(10^k)$, but I want do better.
When $n < 10$, this is Weak Composition with pretty simple formula with good $O(n, k)$, so I easily obtained counts for first ten $n$.
Starting from $n=10$, this is Weak Composition with Restrictions and I didn't manage to obtain formula from the few related SO posts.
Exactly, I need help with recursive/iterative formula $count(n, k)$ for $n$ from 10 to $(9*k)/2$ (due to gaussian distribution)
Typical $k$ is small: 4,6,8.

$\endgroup$
4
+50
$\begingroup$

Your name suggests that you can read Russian. If so, you can look these articles. In particluar, in the second paper is provided a recurrent formula for $count(n,k)=N_k(n)$ in their notation (they swap $n$ and $k$):

$$N_k(n)=\sum_{l=0}^9 N_{k-1}(n-l),$$

where if $n<9$ then $N_{k-1}(n-l)=0$ for $l>n$;

and a table for $N_k(n)$ for $k\le 4$.

I’m going to relook these papers for additional results.

$\endgroup$
1
  • 1
    $\begingroup$ 10 answers out from 10! Thanks a lot! I've added some notes in answer form for non-mathematicians, who will face with the same problem. $\endgroup$ Aug 14 '17 at 12:41
2
$\begingroup$

The bounty does wonders! Alex Ravsky's answer is exact thing I was looking for. All hail "Kvant" magazine № 12, 1976 year! :)

Formula allows me to calculate all $N_k(n)$ where $n$ is from $0$ to $9K / 2$ and k is const like $K = 4, 5, 6, etc$. Values for $n$ from $9K / 2 + 1$ to $9K$ is mirror of the first half. It seems, the formula is the fastest way to do this due to small loops amount and $+ -$ operations only.

Only thing I want to add is my coding improvements:
Memoization. Formula is extremely suited for it:

  • it takes very small memory amount - $O((9K/2+1)*K)$
  • hit ratio - 100%
  • it reduces calculations a lot - for $K=6$ only $168$ ones are new out from total $1203$

k=1 precalculation. Using memoization allows us to precalculate $N_1(n)$ and avoid formula branch for $k=1$.

$\sum$ optimization. $l > n$ case is contiguous, so just changing upper bound from $9$ to $min(n, 9)$ allows us to avoid unnecessary loops with $l > n$ checkings:

$$N_k(n)=\sum_{l=0}^{min(n,9)} N_{k-1}(n-l)$$

Below is Ruby example:

# N_k(n)
def f(n, k, memo)
  memo[n][k-1] ||=
    (0..[n, 9].min).reduce(0){ |sum, l| sum + f(n-l, k-1, memo) }
end

K = 4
median = 9 * K / 2

memo = Array.new(median + 1) { Array.new(K) }
memo.each_with_index{ |a, n| a[0] = n > 9 ? 0 : 1 } # k==1 precalculation

puts (0..median).map{ |n| f(n, K, memo) }.join(' ')

Output:

1 4 10 20 35 56 84 120 165 220 282 348 415 480 540 592 633 660 670
$\endgroup$
3
  • 1
    $\begingroup$ Thanks for your kind words. The referenced papers contains also other interesting formulae for $N_k(n)$, which I was going to add to my answer, but yesterday my computer unexpectedly died, so I urgently had to assemble another from handy stuff. :-) $\endgroup$ Aug 14 '17 at 13:08
  • $\begingroup$ Disclaimer: I am not a bounty hunter, although my profile suggests the opposite. :-) It happened because the easiest way for me to find an interesting, hard and unanswered question is to look at featured questions. :-) $\endgroup$ Aug 14 '17 at 13:08
  • 1
    $\begingroup$ Haha, my SO strategy is same for getting interesting and hard question! $\endgroup$ Aug 14 '17 at 14:18
2
$\begingroup$

Small examples, where the number at array index $i$ tells you how many $k$-digit numbers have digit sum $i$:

k = 0: [1]
k = 1: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
k = 2: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
k = 3: [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55, 45, 36, 28, 21, 15, 10, 6, 3, 1]
k = 4: [1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 282, 348, 415, 480, 540, 592, 633, 660, 670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]

For example for $k=4$, the digit sums $0$, $1$ and $2$ appear in $1$, $4$ and $10$ numbers, respectively.

How to get from the $k$ array to the $k+1$ array? Well, that means using one more digit. How many numbers have a certain digit sum $i$ now? If the added digit is $3$, then the earlier $k$ digits must sum to $i-3$. So look up in the $k$ array how many $k$-digit numbers have digit sum $i-3$. Same for the other $9$ digit options. And then just add up those ten possibilities. So if we call the array $f$, you get $f_{k+1}[i] = \sum_{d=0}^9 f_k[i-d]$ (Where out-of-bounds indexes hold value $0$).

A Ruby implementation/demo:

k = 4
p k.times.reduce([1]) { |f| ([0] * 9 + f + [0] * 9).each_cons(10).map(&:sum) }

Output:

[1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 282, 348, 415, 480, 540, 592, 633, 660, 670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1]

Note the left added [0] * 9 emulate the out-of-bounds zeros mentioned above and the right added [0] * 9 initialize the new higher digit sums we can reach with the new digit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.