Reducing an indicator function summation into a simpler form.

Question

I want to simplify the following:

$\sum_{n=0}^x 1 - (1 - I[a \ne 0] * I[a \ge b]) * (1 - I[b \ne 0] * I[b \ge c]) * (1 - I[c \ne 0] * I[c \ge d]) * (1 - I[d = 0])$

Answer 1

Let $x$ be a base $y$ non-negative integer with at most $4$ digits. Let $a$, $b$, $c$, $d$ such that $0\le a,b,c,d<y$ and the following equations hold true: $$\left\{\begin{aligned} a&=\lfloor\frac{n}{1000}\rfloor\ mod\ 10 \\[2ex]b&=\lfloor\frac{n}{100}\rfloor\ mod\ 10 \\[2ex]c&=\lfloor\frac{n}{10}\rfloor\ mod\ 10 \\[2ex]d&=\lfloor n\rfloor\ mod\ 10 \end{aligned}\right.$$

The expression in the question, $1-(1-I[a\neq0]I[a\ge b])(1-I[b\neq0]I[b\ge c])(1-I[c\neq0]I[c\ge d])(1-I[d=0])$, will evaluate to $0$ if and only if $x$ is a non-zero $z$-digit number (i.e. the most significant digit of $x$ is the $z$th from the right) such that all $z$ digits are in ascending order. Otherwise, it will evaluate to $1$.

Let all the possible values of $x$ for which the expression evaluates to $1$ be called skipped numbers, and let all the possible values of $x$ for which the expression evaluates to $0$ be called non-skipped numbers.

For every non-skipped $x$, let $g(x)$ be the number of non-skipped numbers up to $x$.

$g(x)$ can then be described as follows:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ &\binom{y-1}1+ \sum_{i=y-c}^{y-2}\binom i1+(d-c) \\y^2\le x\le y^3-1\to\ &\binom{y-1}1+\binom{y-1}2+ \sum_{i=y-b}^{y-2}\binom i2+ \sum_{i=y-c}^{y-b-2}\binom i1+(d-c) \\y^3\le x\le y^4-1\to\ &\binom{y-1}1+\binom{y-1}2+\binom{y-1}3\\&+ \sum_{i=y-a}^{y-2}\binom i3+ \sum_{i=y-b}^{y-a-2}\binom i2+ \sum_{i=y-c}^{y-b-2}\binom i1+(d-c) \end{aligned}\right.$

For every integer $n\ge0$, let there be a function $h_n:\{x|x\in\mathbb Z,x\ge n\}\to\mathbb Z$ such that $h_n(x)=\sum_{i=n}^x\binom in$. Then $g$ can be restated as follows:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ &\binom{y-1}1\\&+ h_1(y-2)-h_1(y-c-1)+(d-c) \\y^2\le x\le y^3-1\to\ &\binom{y-1}1+\binom{y-1}2\\&+ h_2(y-2)-h_2(y-b-1)\\&+ h_1(y-b-2)-h_1(y-c-1)+(d-c) \\y^3\le x\le y^4-1\to\ &\binom{y-1}1+\binom{y-1}2+\binom{y-1}3\\&+ h_3(y-2)-h_3(y-a-1)\\&+ h_2(y-a-2)-h_2(y-b-1)\\&+ h_1(y-b-2)-h_1(y-c-1)+(d-c) \end{aligned}\right.$

It can be shown that $h_n(x)=\binom xn+\binom {x-1}n+...+\binom nn=\binom{x+1}{n+1}$. Then the function can be restated again as follows:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ &\binom{y-1}1+ \binom{y-1}2-\binom{y-c}2+(d-c) \\y^2\le x\le y^3-1\to\ &\binom{y-1}1+\binom{y-1}2+ \binom{y-1}3-\binom{y-b}3\\&+ \binom{y-b-1}2-\binom{y-c}2+(d-c) \\y^3\le x\le y^4-1\to\ &\binom{y-1}1+\binom{y-1}2+\binom{y-1}3+ \binom{y-1}4-\binom{y-a}4\\&+ \binom{y-a-1}3-\binom{y-b}3+ \binom{y-b-1}2-\binom{y-c}2\\&+(d-c) \end{aligned}\right.$

The following will be turned into polynomial form in order:

1. all instances of $\binom{y-1}1+\binom{y-1}2$, into $\frac{y(y-1)}2$
2. the only instance of $\binom{y-1}3+\binom{y-1}4$, into $\frac{y(y-1)(y-2)(y-3)}{24}$
3. the remaining $\binom{y-1}3$, into $\frac{(y-1)(y-2)(y-3)}6$
4. all instances of $-\binom{y-c}2+(d-c)$, into $\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2$

Then the function description is rearranged as follows:

$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ & \frac{y(y-1)}2+\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2 \\y^2\le x\le y^3-1\to\ & \frac{y(y-1)}2+\frac{(y-1)(y-2)(y-3)}6\\& +\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2\\& +\binom{(y-1)-b}2-\binom{y-b}3 \\y^3\le x\le y^4-1\to\ & \frac{y(y-1)}2+\frac{y(y-1)(y-2)(y-3)}{24}\\& +\frac{c((2y-3)-c)}2+d-\frac{y(y-1)}2\\& +\binom{(y-1)-b}2-\binom{y-b}3\\& +\binom{(y-1)-a}3-\binom {y-a}4 \end{aligned}\right.$

Consider that every instance of $\frac{y(y-1)}2$ and $-\frac{y(y-1)}2$ can be cancelled out, leaving the final function descriptor:

---

$$g(x)=\left\{\begin{aligned} 0\le x\le y-1\to\ &x \\y\le x\le y^2-1\to\ & \frac{c((2y-3)-c)}2+d \\y^2\le x\le y^3-1\to\ & \frac{(y-1)(y-2)(y-3)}6 +\frac{c((2y-3)-c)}2+d\\& +\binom{(y-1)-b}2-\binom{y-b}3 \\y^3\le x\le y^4-1\to\ & \frac{y(y-1)(y-2)(y-3)}{24} +\frac{c((2y-3)-c)}2+d\\& +\binom{(y-1)-b}2-\binom{y-b}3 +\binom{(y-1)-a}3-\binom {y-a}4 \end{aligned}\right.$$

---

For every integer $x\ge0$, let $f(x)$ be the number of skipped numbers up to $x$, and for every integer $x>0$, let $j(x)$ be the highest non-skipped number not larger than $x$. In the special case that $x=0$, the value of $j(x)$ is $0$.

By definition of $g$,

$$f(x)=x+1-g(j(x))\text.$$

---

Notes:
1. $g(x)$ can be stated witout binomials. I left some binomials as they are because the polynomials they turn into are too complex.
2. You can simplify $g(x)$ somewhat by plugging in the value of $y$ yourself and performing some pre-calculation, or you can let it be and make the compiler do the pre-calculation for you.
3. $g(x)$ is only intended to produce the expected result if $x$ is non-skipped. That is why I defined $j$.