Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got some expression

$$\sum_{i=1}^n\left( 2^{i-1} a_i \sum_{k=0}^{n-i}10^k \binom{n-i}{k} \right)$$

$a_i$ stands for i-th digits in number. I came up with this formula from task in which we had to delete some set of digits from given number and then sum those numbers

so for example we have number 123 then possible numbers we can get are: $$ 1 + 2 + 3 + 12 + 13 + 23 + 123 $$

I won't really explain why this formula works, but computing it it will give $O(n^2)$ time. Can we compress it somehow to get $O(n)$ ? I'm mostly interested in second sum.

Cheers,

Chris

share|improve this question
5  
The second sum looks familiar, binomial expansion of $(1+10)^{n-i}$. –  André Nicolas Oct 8 '12 at 14:22
    
Hey Andre, thanks for reply, could you elaborate or give some hints why it's equal to $(1+10)^{n-i}$? Thanks. –  Chris Oct 8 '12 at 14:28
1  
We have by the Binomial Theorem $(1+a)^m=\sum_{k=0}^m \binom{m}{k}a^k$. Let $m=n-i$ and $a=10$. –  André Nicolas Oct 8 '12 at 14:36
    
Oh, you are right, thank you very much! –  Chris Oct 8 '12 at 14:38

2 Answers 2

up vote 1 down vote accepted

We have by the Binomial Theorem $$(1+a)^m=\sum_{k=0}^m \binom{m}{k}a^k.$$ Let $m=n-i$ and $a=10$. That simplifies the inner sum.

share|improve this answer
    
Well, it is $11^{n-i}$, so there is some dependence on $i$. –  André Nicolas Oct 8 '12 at 14:59

The problem on digits has a linear-time evaluation by recursion on the $a_i$. The complexity is $O(n (\log n)^c)$ in bit operations, and $O(n)$ in arithmetic operations.

If $S_n$ is the sum of all numbers formed by deletions from the substring of $n$ first digits, then $S_{n+1} = S_n + (10S_n + 2^n a_{n+1})$. The recursion starts from $S_0 = 0$. This implies that $a_i$ has a coefficient of $2^{i-1}11^{n-i}$ when the sum is written as a linear function of the digits, but the recursive evaluation is faster than computing large powers of $11$ at every step. On a computer the efficiency of the sum can be optimized by starting from $2^{n-1}$ and performing "divide by 2, multiply by 11" at every step to get the coefficients, and this is about the same complexity as calculation from the recurrence.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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