Proof of $\inf\left \{ \frac{\mathrm{d} (n^2)}{\mathrm{d} (n)} \; \bigg| \; n \in \mathbb{N} \right \}=0$, where $d(n)$ is the sum of digits of $n$

Question

So I wanted to find the infimum of the set described in the title, and I'm pretty confident on what the subsequence should be to ensure a 0 infimum.

$[4899,4899899999,4899899999899999999999, \dotsc]$, where the next term in the sequence is the previous + '8' + '9' * $(2s+1)$, where $s$ is the length of the previous set of consecutive nines. In the sequence I provided, it goes 2,5,11... (I'm fairly confident 1,3,7,15... also works).

But a proof of this eludes me. I tried some funky stuff with the multinomial theorem and binomial theorem

$(10^6 4899 + 899999)^2$ and tried to chunk it based on the first section and second but I really couldn't go anywhere due to the $2\cdot 899999 \cdot 10^6 \cdot 4899$ term.

EDIT: 49 is a good starting term to look at.

Answer 1

The claim is true. Here is a solution based on this AoPS thread. Let

$$ n=10^{4k}+2\cdot10^{3k}-10^{2k}+2\cdot10^{k}+1. $$

Then you can check that $$ n=10^{4k}+10^{3k}+9\cdot 10^{3k-1}+9\cdot 10^{3k-2}+\dots+9\cdot 10^{2k}+2\cdot 10^k+1\\ n^2=10^{8k}+4\cdot 10^{7k}+2\cdot 10^{6k}+10^{4k+1}+10^{4k}+2\cdot 10^{2k}+4\cdot 10^{k}+1. $$

Thus $$ \frac{d(n^2)}{d(n)}=\frac{1+4+2+1+1+2+4+1}{1+1+9k+2+1}=\frac{16}{9k+5} \to 0 \text { as } k\to \infty. $$

Answer 2

Using the letters $j$ and $n$ as shown below, it comes out $$ d(n) = 9 \cdot 2^j - j - 4 $$

$$ d(n^2) = j^2 - j +7 $$

Getting there. I see, let us say, the ingredients of a proof allowing an explicit description. Let us call a number $\theta$ in base ten with most digits $0$ but, reading left to right, at positions $1, 3, 7, ..., 2^j - 1.$ That is, $$ \theta = 10^{2^j - 2} + 10^{2^j - 4} + 10^{2^j - 8} + ... + 10^{2^{j-1} } + 1 $$

Compare this brief printout

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Tue 30 May 2023 12:14:39 PM PDT
4899    3     30       9     24000201
 101  theta 
 10201  theta^2 

Tue 30 May 2023 12:14:39 PM PDT
48989999    5     65       13     2400020002020001
 1010001  theta 
 1020102020001  theta^2 

Tue 30 May 2023 12:14:39 PM PDT
4898999899999999    7     136       19     24000200020200000202000200000001
 101000100000001  theta 
 10201020200010202000200000001  theta^2 

Tue 30 May 2023 12:14:39 PM PDT
48989998999999989999999999999999    10     279       27     2400020002020000020200020000000002020002000000020000000000000001
 1010001000000010000000000000001  theta 
 1020102020001020200020000000102020002000000020000000000000001  theta^2 

Tue 30 May 2023 12:14:39 PM PDT
4898999899999998999999999999999899999999999999999999999999999999    15     566       37     24000200020200000202000200000000020200020000000200000000000000000202000200000002000000000000000200000000000000000000000000000001

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

repeat

$$ \theta = 10^{2^j - 2} + 10^{2^j - 4} + 10^{2^j - 8} + ... + 10^{2^{j-1} } + 1 $$

Then the numbers $n$ that optimize your ratio are $$ n = \frac{1}{2} 10^{2^j} - \theta $$
so that

$$ n^2 = \frac{1}{4} 10^{2^{j+1}} - 10^{2^j}\theta + \theta^2 $$

and we can calculate this. It is the top digit of $10^{2^j}\theta$ that provides the decrease from $2.5$ down to $2.4$

with summation signs $ \theta = \sum_{k=1}^j 10^{2^j - 2^k} $ for $$ \theta = 10^{2^j - 2} + \sum_{k=2}^j 10^{2^j - 2^k} $$ so $$ 10^{2^j} \theta = 10^{2^{j+1} - 2} + \sum_{k=2}^j 10^{2^{j+1} - 2^k} $$

Next $$ \frac{1}{4} 10^{2^{j+1}} = 25 \cdot 10^{2^{j+1} - 2} $$

and $$ n^2 = 24 \cdot 10^{2^{j+1} - 2} + \theta^2 - \sum_{k=2}^j 10^{2^{j+1} - 2^k} $$

Time to expand $\theta^2$ carefully.........