Average digit sum – 2

Let us first find a general equation for the average of all the digit sums of all nonnegative integers less than $b^n$ written down in base $b$ .

Including zeroes as leading digits, there are $nb^n$ total digits. Since they all appear equally, each digit from $0$ to $b$ appears $\frac{nb^n}{b}$ times, which makes the sum of all the digits $\frac{nb^n(0 + 1 + 2 + ... + (b - 1))}{b}$ and the average of all the digit sums $\frac{nb^n(0 + 1 + 2 + ... + (b - 1))}{b \cdot b^n}$ or $\frac{n(0 + 1 + 2 + ... + (b - 1))}{b}$ .

The sum $0 + 1 + 2 + ... + (b - 1)$ can be expressed as $\frac{b(b - 1)}{2}$ . Substituting this in, the average of all the digit sums is now $\frac{n(\frac{b(b - 1)}{2})}{b}$ or $\frac{n(b - 1)}{2}$ .

This means that the average of all the digit sums of all the nonnegative integers less than $b^7$ is $\frac{7(b - 1)}{2}$ , and the average of all the digit sums of all the nonnegative integers less than $b^3$ is $\frac{3(b - 1)}{2}$ , for a difference of $\frac{7(b - 1)}{2} - \frac{3(b - 1)}{2} = 2b - 2$ . Equating this to $2018$ , $2b - 2 = 2018$ , which solves to $b = \boxed{1010}$ .

The main idea, that I also used for the harder version, is as bellow. I think, with the hard one, if you take my approach, you eventually need to make some approximation and reaching the actual solution is rather difficult (I am prone to make mistakes though).

In any base $b$ , there are $b$ symbols $\{0,1,\dots , (b-1)\}$ . The number of times a symbol $k$ is used, in numbers from $0$ to $p^t$ , is denoted by $n_{k}(t)$ . It can be shown that $n_{k}(t) \ \forall k=1,\dots, (b-1)$ is the same, when $t$ is fixed, except for $n_{0}(t)=\frac{n_{k}(t)}{2} \ k=1,\dots,p-1$ . So, if we know how many digits have been used in numbers from $0$ to $p^t$ (denoted by $N(t)$ ), then we would know $n_{k}(t) \ \forall \ k$ .

$N(t)=b+\sum_{2}^{t} j(b^j-b^{j-1})=t.b^{t}-\frac{b^t-b}{b-1}$

which should be equal to

$\sum_{j=0}^{b-1}n_{j}(t)=\frac{45}{2}n_{1}(t)$

So, we have a relation between $n_{i}(t) \ \forall i$ and $b$ .

finally, we need to calculate

$\frac{\sum_{j=0}^{b-1} n_{j}(t).j}{p^t}=\frac{\sum_{j=1}^{b-1} n_{j}(t).j}{p^t}=\frac{(b-1)bn_{1}(t)}{2b^t}$

relation between $n_{i}(t) \ \forall i$ and $b$ come useful now. We substitute $n_{1}(t)$ to have a fraction that depends only on $b$ . Then, $t$ is taken to be $3$ and $7$ , because of $b^3, b^7$ , and the difference of their results is supposed to be equal to 2018. The rest was done numerically (the finale equation can be rewritten as a polynomial of order 7). There would be only one solution that can be the final answer and that would be $1009.5$ and I tried both $1009$ and $1010$ .

Here let's take the Average digit sum of all the numbers from 0 to $b^n$ be $A(n)$ Therefore, we must find $A(n)+1$ . The average of first $b^n$ integers is $A(n)$ . The average of the next $b^n$ integers is $A(n)+1$ as $b^(n+1)$ place is 1. Similarly, next average is A(n)+2\ ) and so on until \(b^(n+1) place is $b-1$ . Hence, $A(n+1)=\frac{\sum_{i=0}^(b-1)A(n)+i}{b}$ $=\frac{A(n)*b+\frac{b(b-1)}{2}}{b})$ $=A(n)+\frac{b(b-1)}{2}$

A(0)=0.

Let's try to find a pattern by first considering numbers in base 2:

The average digit sums of all integers less than $2^n$ , denoted by $\varnothing_2(n)$ can now be calculated:

It looks like, $\varnothing_2(n) = \frac 12 n$ . But why exactly is that?

Let's try to average the digit sums in a clever way by grouping them in groups of $2 = 2^1$ and $4 = 2^2$ respectively.

It looks like the average in every group just follows the same pattern as the digit sums. And this pattern will indeed continue. This is because the binary numbers from $2^n$ to $2^{n+1}-1$ are written almost like the numbers from $0$ to $2^n$ , except for another digit 1 in the front, so their digit sum is just one more. Therefore, their average is 1 more than the average of the first half. The average of all numbers is the average of these two (since they both contain $2^n$ numbers ), so $\frac 12$ more than the previous term. We can group the terms again and again until we get to a single number that is the average of all digit sums.

The formula for the average digit sum is indeed

$\varnothing_2(n) = \frac 12 n$

---

Let's try to do the same trick for base 3. This time, we can't group 4 numbers, but rather 3.

Again, the pattern repeats self-similarly, and we can write the formula

$\varnothing_3(n) = n$

---

Now, it's time to generalize. What we've got so far is

$\varnothing_2(n) = \frac 12 n$

$\varnothing_3(n) = n = \frac 22 n$

The self-similar pattern will continue in all bases and the argument as explained for base 2 will also always work, so the general expreasion for $\varnothing_b(n)$ is

$\boxed{\varnothing_b(n) = \frac {b-1}2 n}$ .

---

After all this, we can plug in $n = 3$ and $n=7$ .

$\varnothing_b(3) = \frac {b-1}2 \cdot 3$

$\varnothing_b(7) = \frac {b-1}2 \cdot 7$

We are given that their difference is 2018, so we can set up the equation

$\begin{aligned} \frac {b-1}2 \cdot 7 - \frac {b-1}2 \cdot 3 & = 2018 \\ 4 \left( \frac {b-1}2 \right) & = 2018 \\ 2 (b-1) & = 2018 \\ b & = \boxed{1010} \end{aligned}$

The average for a given power $p$ is $\frac{p(b-1)}{2}$ . This is derived as the lower limit of a digit range is $0$ and the upper limit is $b-1$ and you need the average of those limits as the digits add pairwise from each end of the range. The sum for multiple digit base- $b$ is the power times the single digit average. Solve $\frac{7 (b-1)}{2}-\frac{3 (b-1)}{2}=2018$ for $b$ . $b$ is $1010$ .