A Little Discrete Math

Recently I ran across a fun little problem about numbers at Ben Orlin’s blog https://mathwithbaddrawings.com/2019/11/18/the-anti-calculator-puzzle/. My rephrasing of it is as follows:

Consider every positive integer n which can be represented in base k as a d-digit number. In other terms, we have

\displaystyle n=[a_{n-1}a_{n-2}...a_{0}]_k=\sum\limits_{m=0}^{n-1} a_m k^m, (1)

where 1 \leq a_{n-1} < k and 0 \leq a_{m} < k for m < n-1. We can then define the function f(n) over all d-digit numbers as

\displaystyle f(n)=\frac{\sum\limits_{m=0}^{n-1} a_m k^m}{\sum\limits_{m=0}^{n-1} a_m}, (2)

i.e. the original number n divided by the sum of its digits. The goal of the problem is to find the maxima and minima of this function over all d-digit numbers.

Finding the maximum value of f(n) is relatively simple; a little numerical experimentation and thinking shows that the sum of digits is always larger than or equal to the first digit, and thus heuristically we can say that the denominator can drag the whole sum down to be less than or equal to k^{n-1}. More rigorously, we can rearrange the expression k^{n-1}-f(n) into the form

\displaystyle k^{n-1} - f(n)=\frac{\sum\limits_{m=0}^{n-2} a_m (k^{n-1}-k^m)}{\sum\limits_{m=0}^{n-1} a_m}. (3)

(Note that in the numerator of expression 3, the value of a_{n-1} fell out of the sum. This is going to be a recurring theme of this discussion later on.)

Because every term a_m (k^{n-1}-k^m) in expression 3 is either positive or zero for m < n-1, and only zero if a_m is zero, we can see that the maximum value of f(n) is in fact k^{n-1}, which is only realized when all digits of n but the first are zero.

That was the easy part. Finding the minimum (and there is only one, as it turns out) is rather more subtle. While it is tempting to assume that the correct answer will be numbers of the form [1ee...e]_{k} where e=k-1, this can quickly be proven false using four-digit numbers in base ten. In base ten, f(1009)=100.9, f(1099)\approx 57.84, and f(1999)\approx 71.39. Clearly we must look more deeply.

First, I will describe the solution: over all d-digit natural numbers, function f(n) as defined in expression (2) has a minimum only when n's base-k representation is of the form

\displaystyle n=[100...0ee...e]_k, (4)

where the number of digits that are equal to e is given by the smallest integer c such that

\displaystyle c k^c > \sum\limits_{m=0}^{d-2} k^m. (5)

Note that for small n, despite my representation in expression (4), there may actually be no or one zeros present in the true minimum. By the same token, there may be only one or two digits of e. However, inspection of expression (5) shown that the number of zeros present is non-decreasing in the number of digits and eventually you will get an arbitrarily large number of zeros, albeit with a far vaster number of e‘s.

To prove (4) and (5), we will focus all of our attention on what I mentally label “the components of the discrete gradient” of f(n). That is, we consider the change induced in f(n) by either increasing or decreasing a single digit. Obviously this would produce problems if we step outside of the valid range of digits (i.e. 1 \leq a_{n-1} < k and 0 \leq a_{m} < k for m < n-1), so we simply forbid taking such steps. All this said, the change in f(n) given a single-digit change at position l of sign s=\pm 1 can be calculated to be

\displaystyle f(n+s k^l)-f(n)=s\frac{\sum\limits_{m=0, m\neq l}^{n-1} a_m (k^{l}-k^m)}{(\sum\limits_{m=0}^{n-1} a_m)(s + \sum\limits_{m=0}^{n-1} a_m)}. (6)

The most important thing to notice about the numerator on the right side of expression (6) is that it does not depend on the value of a_l, which means that the sign of f(n+s k^l)-f(n) is constant as we range a_l from 0 to e. Thus either f(n) is constant as we change a_l (if f(n+s k^l)-f(n)=0) or the extremes values occur at the boundary points: 1 or e for the first digit or 0 or 0 or e for the rest of the digits.

We can go a step further and notice that in the special case l=n-1 and s=1, the right side of (5) must be negative or zero, because then all k^m < k^{n-1}. From expression 3, we know that the true minimum must have at least one non-zero digit after the first (because all n which end in anything besides n-1 zeros produce a f(n) that is less than k^{n-1}). Thus the first digit of the true minimum must be one, because if it were greater than one, we could simply decrease the first digit and thus decrease f(n). Put another way, f(n) is slanted towards smaller a_{n-1}, and so all minima must slide there.

I then claim that

\sum\limits_{m=0, m\neq l}^{n-1} a_m (k^{l}-k^m) \neq 0 for any l < n-1. (7)

I prove this below, but first observe that expression (7) combined with expression (6) gets us to the form described in equation (4), although not yet expression (5). As noted above, if f(n+s k^l)-f(n) is not 0 for a particular digit (given the rest of the number), then f(n) will change monotonically in that digit, thus producing extrema only at the boundaries. Thus besides the first digit, any minimum can only contain the digits 0 or e. We can get further by noting that exchanging digits with different values changes the numerator of f(n) in expression 2 but does not change the denominator (the sum of digits) at all. Thus for numbers represented by the same sets of digits, the smaller ones will have the smaller values for f(n). Thus we need consider only numbers of the form of expression (4) as candidates for the true minimum. Finding the correct number of zeros will be the bulk of the solution once I have proved (7).

Expression (7) can be proved true by contradiction. If we assume there is a zero solution to (7), we can rearrange it to get the expression

\sum\limits_{m=0}^{n-1} a_m k^m = k^{l}\sum\limits_{m=0}^{n-1} a_m for any l < n-1. (8)

But the right-hand side of (8) is an integer which, in base k ends in l zeros. This proves that for any solution to formula 8, a_m = 0 for m < l. But this in turn implies that we can subtract coefficients of a_m on the right size of (8) from the coefficients of a_m on the left, resulting in

\sum\limits_{m=l+1}^{n-1} a_m (k^m-k^l)=0 for any l < n-1. (9)

But the left-hand side of formula 9 is positive (because a_{n-1}>0 and k^m > k^l for every term). Thus there is no valid solution for equation (8) and equation (7) is proved.

The number of zeros and e‘s in the true global minimum can again fortunately be found from a detailed inspection of the consequences of expression (6). In particular, we consider all d-digit numbers of the form shown in expression (4). In particular we will look at how f(n) changes as you change n from [100...00ee...e]_k (with r e‘s) into [100...0eee...e]_k (with r+1 e‘s). We will find that for this case, the numerator of expression (6), whose sign is the sign of the change in f(n) for this transition, starts out as negative when all the digits are zero, but increases monotonically as the number of e‘s are increased. The digit for which the numerator of expression (6) becomes positive is the last digit for which you can add another e and expect f(n) to decrease, and is thus the number of digits of e which produces a minimum in f(n), now known to be unique.

To calculate the sign of the change in f(n) when transitioning between having r digits set to e and having r+1 digits set to e, we extract the numerator from expression (6) and rewrite it in our case as

\displaystyle \sum\limits_{m=0, m\neq r}^{n-1} a_m (k^{r}-k^m)=-(k^{n-1}-k^r) + r(k-1)k^r - (k-1)\sum\limits_{m=0}^{r-1} k^m. (10)

But (k-1)\sum_{m=0}^{r-1} can be expanded, and most of the terms cancelled, to get $k^r-1$, and so we can transform expression (10) into

\displaystyle \sum\limits_{m=0, m\neq r}^{n-1} a_m (k^{r}-k^m)=-(k^{n-1}-1) + r(k-1)k^r. (11)

From this, we can see that the right side of expression (11) starts at negative numbers for r=0 and increases monotonically in r. If we then use polynomial factorization to factorize (k-1) out of both terms on the right side of expression (11), we then see that f(n) does indeed start increasing and continues increasing once expression (5) is satisfied. q.e.d.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s