1
$\begingroup$

For positive integers $x$, let $s(x)$ denote the sum of the digits of $x$, and $l(x)$ denote the number of digits of $x$. It seems that other than $n=1$ and $n=20$, there always exist $x$ such that $n=x+s(x)$ or $n=x+s(x)+l(x)$. Note that a number not expressible as $x+s(x)$ is also known as a self number. In this previous question on the topic, Mario has given some more examples of such numbers: $n=10^{10}+\{98,109,122,133,144,155\}$. It seems that for natural numbers with the number of digits corresponding to gaps between successive self numbers, that condition is often satisfied. My question: Are there infinitely many natural numbers cannot be expressed as $x+s(x)$ nor $x+s(x)+l(x)$?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

For convenience, I'm going to call a number not of the form $x+s(x)$ or $x+s(x)+\ell(x)$ a "strong self number". In order to show the existence of arbitrarily large strong self numbers, we need to gather detailed information on the behavior of the function $f(x)=x+s(x)$. Now usually this function increases by $2$, but it occasionally drops down by an amount proportional to $\ell(x)$ (note that $1\le s(x)\le9\ell(x)$ and it touches both bounds infinitely often), and we want to avoid these drops so that we can be sure that once $f(x)$ has passed a given candidate self number, it will never return to that number later, thus proving that we actually have a self number.

To be precise, $f(x)-f(x-1)=2-9k_x$ where $k_x$ is the largest integer satisfying $10^{k_x}\mid x$. Since this is usually $k_x=0$, we have $f(x)-f(x-1)=2$ most of the time, with occasional drops of $-7$, $-16$, etc. In order to avoid these drops we want to be sure we are sufficiently far from large powers of $10$ (we will handle the $10^1$ drops as a special case).

Suppose that $k_x\ge 2$. Then there is a drop of size $9k_x-2$ at $x$, and to the left and right of $x$ $f(x)$ covers its range twice. We argue that the range where this occurs is no larger than $18k_x$. Suppose that $y\le x-18k_x$. Then $$f(x)-f(y)=\sum_{i=y+1}^x2-9k_i=2(x-y)-9k_x-9\sum_{i=y+1}^{x-1}k_i\ge 27k_x-9\sum_{i=y+1}^{x-1}k_i,$$ and since the next number that has a power of $10$ as large as $x$ is $10^{k_x}>18k_x$ away, the terms in the sum are bounded by $k_x-1$. Furthermore, at most one in $10$ terms (rounded up) contribute $1$ to the sum, at most one in $100$ terms contribute an extra $1$ to the sum, and so on, yielding the decomposition $$\sum_{i=y+1}^{x-1}k_i\le\sum_{n=1}^{k_x-1}\left\lceil\frac{x-y}{10^n}\right\rceil\le k_x-1+\sum_{n=1}^\infty\frac{18k_x}{10^n}=k_x-1+2k_x=3k_x-1$$

so $f(x)-f(y)\ge 27k_x-9(3k_x-1)=9>0$. By symmetry under $y\mapsto 2x-y-1$ (under which $f(y)\mapsto (2f(x)+2-9k_x)-f(y)$), we also have $f(y)\ge f(x-1)$ for $y\ge x-1+18k_x$. (For $k_x=2$, this is rather an overestimate, and one can verify that $|y-x|\ge 14$ is sufficient.)

And now we have a means for generating a large number of self numbers, which are needed for the original claim. Let $x=100n$, where $n$ has no $9$ or $0$ in its decimal expansion. Then if $10^k\mid y$ for some $k\ge 3$, we have $|x-y|\ge 10^{k-1}\ge18k$, so any number outside the block of $1000$ containing $x$ has $f(y)\le f(x)$ or $f(y)\ge f(x+99)$, and so any number greater than $f(x-1)$ and less than $f(x+100)$ and not equal to $f(y)$ for any $x\le y<x+100$ is a self number. Now since $f(x)$ is self-similar in blocks of $100$ (or any power of $10$, for that matter) with varying offsets, we can explicitly find these numbers, and so we get that $f(x)+\{20, 31, 42, 53, 64, 75, 86, 97\}$ are all self numbers.

Now we just proved that there are infinitely many self numbers, but there is enough structure in this set that we can also ensure the existence of pairs of self numbers, which is what we need for the original claim. Consider the pair $m=\sum_{i=2}^{10^k}10^i=\frac{10}9(10^{10^k}-10),n=m+10^k$ for $k\ge2$. This gives numbers of the form $m=11\dots100,n=1\dots 121\dots100$ where the digit string is of length $10^k+1$ and $n$ has a single $2$ at the $k$-th position. These numbers clearly satisfy the condition above, so $f(m)+20,f(n)+20$ are self numbers. We can also calculate $f(m)=m+10^k-1,f(n)=n+10^k$, so this pair is separated by $10^k+1$. But for any number close enough to satisfy $x+s(x)+\ell(x)=f(n)+20$, we have $\ell(x)=10^k+1$, so $x+s(x)=f(m)+20$, contradicting selfness of $f(m)+20$. Thus $f(n)+20$ is a strong self number, which since $k$ is infinite implies that there are infinitely many. To sum up:

For any $k\ge2$, $\frac{10}9(10^{10^k}-10)+2\cdot 10^k+20$ is a strong self number, so there are infinitely many.

$\endgroup$
16
  • $\begingroup$ @GaryB Yes, if you have two self numbers you can translate these two to a digit block such that the numbers themselves have the same length as the gap, and then the larger one is a strong self number. The reason for the construction was because you need the gap to get arbitrarily large, since there are not infinitely many 11-digit numbers and past 77 digit you have to use adjacent blocks and so on. $\endgroup$ Commented Jan 29, 2015 at 18:39
  • $\begingroup$ Unless you are very close to a power of $10$, for every strong self number $x$ both $x$ and $x-\ell(x)$ are self numbers, so $\ell(x)$ is a self number gap. $\endgroup$ Commented Jan 29, 2015 at 18:41
  • $\begingroup$ You mean this kind of numbers,doesn't contain any natural number with non self-gap digit length ? $\endgroup$
    – Gary B
    Commented Jan 29, 2015 at 18:43
  • $\begingroup$ That's right. $20$ is an exception, from what I can tell, because the numbers $x$ with $x+s(x)+\ell(x)$ near $20$ are actually between $1$ and $2$ digits (also the assumption $s(x)\ll x$ doesn't really hold here). $\endgroup$ Commented Jan 29, 2015 at 18:51
  • $\begingroup$ Mario,of course that formula doesn't cover all strong self numbers $\endgroup$
    – Gary B
    Commented Jan 29, 2015 at 19:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .