2
$\begingroup$

Find the sum of all positive integers whose digits (in base ten) form a strictly decreasing sequence with first digit $9$.

The method I thought of for solving this was very computational and it depended on a lot of casework. Is there a nicer way to solve this question?

Note that there are $\displaystyle\sum_{n=0}^{9} \binom{9}{n} = 2^9$ such numbers.

$\endgroup$
  • 1
    $\begingroup$ Form a strictly increasing what? If the first digit is $9$ it's hard for the digits to increase from there... $\endgroup$ – lulu Jul 6 '16 at 22:14
  • $\begingroup$ @lulu Thanks, typo. $\endgroup$ – user19405892 Jul 6 '16 at 22:15
  • $\begingroup$ So...you want the digits to decrease? Thus $9876543210$ is good, as is $9531$ but $99$ is not, yes? $\endgroup$ – lulu Jul 6 '16 at 22:15
  • $\begingroup$ @lulu Yeah, that's right. $\endgroup$ – user19405892 Jul 6 '16 at 22:16
  • $\begingroup$ Let's see...there are $2^9$ such numbers (any subset of $\{8,7,6,5,4,3,2,1,0\}$ can be ordered decreasingly in a unique way). So brute force is a bit grim, at least armed only with pencil and paper. There must be a shortcut... $\endgroup$ – lulu Jul 6 '16 at 22:20
3
$\begingroup$

For each digit $a$ from $0$ to $9$, let us count how many numbers there are in our sum with a digit of $a$ in the $10^n$ place. First, suppose $a<9$. A number with a digit of $a$ in the $10^n$ place has a subset of $\{0,1,\dots,a-1\}$ for its last $n$ digits, so there are $\binom{a}{n}$ choices for the last $n$ digits. The preceding digits (omitting the initial $9$) can form any subset of $\{8,7,\dots,a+1\}$, so there are $2^{8-a}$ choices for the preceding digits. So in total, all of the digits of $a$ in our numbers contribute $\sum_n 2^{8-a}\binom{a}{n}\cdot a10^n$ to the sum. By the binomial theorem, this is equal to $$2^{8-a}a(10+1)^a=2^8a\left(\frac{11}{2}\right)^a.$$

For $a=9$, we have no choice of preceding digits, so we just have $\binom{9}{n}$ choices. So the sum of the $9$ digits contributes $$\sum_n \binom{9}{n}9\cdot 10^n=9\cdot 11^9.$$

So in total, the sum is $$9\cdot 11^9+2^8\sum_{a=0}^8 a\left(\frac{11}{2}\right)^a.$$ Let us write $x=\frac{11}{2}$ and simplify the sum in the second term: $$\sum_{a=0}^8 ax^a=\sum_{b=1}^8\sum_{c=b}^8x^c=\sum_{b=1}^8\frac{x^9-x^b}{x-1}=\frac{8x^9-\frac{x^9-x}{x-1}}{x-1}.$$

Putting it all together, the original sum is $$9\cdot 11^9+2^8\cdot\frac{8x^9-\frac{x^9-x}{x-1}}{x-1}$$ for $x=\frac{11}{2}$. According to Wolfram Alpha, this evaluates to $23259261861$. That is, assuming I haven't made some algebra mistake somewhere.

$\endgroup$
  • $\begingroup$ Nice -- I didn't know this other way to get $\sum_aax^a$. $\endgroup$ – joriki Jul 6 '16 at 23:06
1
$\begingroup$

If the digit with value $10^j$ is $k$, there are $\binom kj$ options for the digits after that and $2^{8-k}$ options for the digits before that (corresponding to the subsets of the digits between $k$ and $9$), except for $k=9$ there is $1$ option for the digits before (namely none). Thus the sum of the contributions from the $10^j$ digit is

$$ 10^j\left(\sum_{k=0}^8k\binom kj2^{8-k}+9\binom9j\right)\;, $$

and the sum of the contributions from all digits is

\begin{align} \sum_{j=0}^910^j\sum_{k=0}^8\left(k\binom kj2^{8-k}+9\binom9j\right) &= \sum_{k=0}^8k\cdot11^k2^{8-k}+9\cdot11^9 \\ &= 2^8\cdot q\frac{\mathrm d}{\mathrm dq}\left.\frac{q^9-1}{q-1}\right|_{q=\frac{11}2}+9\cdot11^9 \\ &= 2^8\cdot\frac{11}2\cdot\frac{8\left(\frac{11}2\right)^9-9\left(\frac{11}2\right)^8+1}{\left(\frac{11}2-1\right)^2}+9\cdot11^9 \\ &=23259261861\;. \end{align}

Here's code to check this result.

$\endgroup$
  • $\begingroup$ Can you check the answer for this question: Determine the sum of all positive integers whose digits (in base ten) form either a strictly increasing or a strictly decreasing sequence. I get $25937423487$. $\endgroup$ – user19405892 Jul 6 '16 at 23:04
  • $\begingroup$ @user19405892: It looks like you included numbers that start with '0'? I get $25617209040$ (but you can check for yourself by adapting the code I posted). $\endgroup$ – joriki Jul 6 '16 at 23:12
  • $\begingroup$ How did you involve the derivative to calculate the sum? $\endgroup$ – user19405892 Jul 7 '16 at 0:41
  • $\begingroup$ @user19405892: $\sum_kkq^k=q\frac{\mathrm d}{\mathrm dq}\sum_kq^k$. $\endgroup$ – joriki Jul 7 '16 at 2:33
  • 1
    $\begingroup$ @user19405892 are you familiar with the derivative? Just remember that $kq^{k-1} = \frac{d}{dk} q^k$ (it is just the power rule). Multiply both sides by $q$ and you get that $kq^k = k\frac{d}{dk} q^k$. All that is left to do is take $q$ and $\frac{d}{dq}$ outside the sum (taking the derivative out isn't always valid, but it is here because polynomials are nice functions in this regard) $\endgroup$ – Brevan Ellefsen Jul 7 '16 at 3:44
1
$\begingroup$

Here a simple way to compute it with haskell. The idea is to take all subsequences of "876543210", prepend "9", parse that as an integer and sum them all:

Prelude> (sum $ map (read.("9"++)) $ Data.List.subsequences "876543210")::Integer
23259261861
$\endgroup$
  • $\begingroup$ Could have used ('9':) (but that doesn't generalize as well), and the type annotation is not needed. $\endgroup$ – Christian Sievers Jul 6 '16 at 23:40
1
$\begingroup$

Suppose we treat the general problem of computing the sum of the contributions of the subsets of $[n]$ containing $n$ where the contribution is to order the elements of the set in a decreasing sequence, multiply by a power of ten corresponding to the element's position starting from the right and sum these values. (We will modify this at the end to account for the zero digit.)

Let $A_{n, q}$ be the sum of the contributions from subsets of $[n]$ with leading value $n$ and $q$ additional digits. We get the recurrence

$$A_{n+1, q} = \sum_{m=1}^n \left(A_{m, q-1} + {m-1\choose q-1} 10^q \times (n+1)\right).$$

The boundary conditions here are $A_{n, 0} = n$, $A_{0, q} = 0$ and $A_{n, q} = 0$ when $q\ge n.$

Introduce the generating function $$A(z, u) = \sum_{n\ge 0} \sum_{q\ge 0} A_{n,q} u^q z^n.$$

Multiply the recurrence by $u^q z^{n+1}$ and sum over $n\ge 0$ and $q\ge 1$ to get

$$A(z, u) - \sum_{n\ge 0} (n+1) z^{n+1} = \sum_{n\ge 0} \sum_{q\ge 1} u^q z^{n+1} \sum_{m=1}^n [z^m] [u^{q-1}] A(z, u) \\ + \sum_{n\ge 0} \sum_{q\ge 1} u^q z^{n+1} \sum_{m=1}^n {m-1\choose q-1} 10^q \times (n+1).$$

The first term is

$$\sum_{n\ge 0} u z^{n+1} \sum_{m=1}^n [z^m] \sum_{q\ge 1} u^{q-1} [u^{q-1}] A(z, u) \\ = \sum_{n\ge 0} u z^{n+1} \sum_{m=1}^n [z^m] A(z, u) \\ = uz \sum_{n\ge 0} z^{n} [z^n] \frac{1}{1-z} A(z, u) \\ = \frac{uz}{1-z} A(z, u).$$

The second term is

$$\sum_{n\ge 0} (n+1) z^{n+1} \sum_{m=1}^n \sum_{q\ge 1} u^q {m-1\choose q-1} 10^q \\ = \sum_{n\ge 0} (n+1) z^{n+1} \sum_{m=1}^n 10u (1+10u)^{m-1} = 10u \sum_{n\ge 0} (n+1) z^{n+1} \frac{(1+10u)^n-1}{(1+10u)-1} \\ = \sum_{n\ge 0} (n+1) z^{n+1} ((1+10u)^n-1) = \frac{z}{(1-(1+10u)z)^2} - \frac{z}{(1-z)^2}.$$

Solving the equation we get

$$A(z, u) = \frac{z(1-z)}{(1-(1+10u)z)^2 (1-z(1+u))}.$$

At this point we no longer need the classification according to the number of digits since we seek to sum the contributions having from $0$ extra digits to $n-1$ extra digits, the maximum possible. We thus set $u=1$ and obtain

$$B(z) = \frac{z(1-z)}{(1-11z)^2 (1-2z)} \\ = \frac{10}{99} \frac{1}{(1-11z)^2} - \frac{101}{891} \frac{1}{1-11z} + \frac{1}{81} \frac{1}{1-2z}.$$

Extracting coefficients and multiplying by $11$ to account for the zero digit which may or may not be present at the end we finally obtain the closed form

$$\frac{10}{9} (n+1) 11^n -\frac{101}{81} 11^n + \frac{11}{81} 2^n \\ = \frac{10}{9} n 11^n - \frac{11}{81} (11^n - 2^n).$$

This produces the following sequence starting at $n=1$:

$$11, 253, 4257, 63085, 872861, 11569833, 148920497, \\ 1876301845, 23259261861, 284671240513, 3448396611737, \\ 41419505367405, 493973128085261,\ldots$$

In particular the value for $n=9$ is

$$\bbox[5px,border:2px solid #00A000]{\Large 23259261861.}$$

The Maple code for the above was as follows:

with(combinat);

A :=
proc(n, q)
option remember;
    if q = 0 then return n end if;

    add(A(m, q - 1) +
        binomial(m - 1, q - 1)*10^q*n, m = 1 .. n - 1)
end;

AZU :=
proc()
option remember;
local LHS, RHS;

    LHS := AGFSYM - z/(1-z)^2;

    RHS := u*z/(1-z)*AGFSYM + z/(1-(1+10*u)*z)^2-z/(1-z)^2;

    solve(LHS=RHS, AGFSYM);
end;

AGF := (n, q) -> coeftayl(coeftayl(AZU(), u=0, q), z=0, n);

X := n -> 10/9*n*11^n - 11/81*(11^n-2^n);

ENUM :=
proc(n)
option remember;
local dset, dlst, val, res;

    res := 0;

    for dset in powerset(n) do
        dlst :=
        sort([seq(el-1, el in dset), n]);

        val := add(dlst[p]*10^(p-1), p=1..nops(dlst));

        res := res + val;
    od;

    res;
end;
$\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.