No, the expression is unbounded. I managed to produce the following counterexample after a lot of computer work. I have no idea how one could get such an idea without a computer in a couplle of hours time lemma if $ a,b,c,d$ are natural numbers than we can conclude $ \max(a,b) = \max(c,d)$ and $ \min(a,b) = \min(c,d)$ from $ 2^a + 2^b = 2^c + 2^d$. this lemma will be used later on. it's proof is trivial. proof consider numbers of the form $ a_n = 5\cdot 10^{2^n - 1} - (10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}} + 1)$. It's a number with $ 2^n$ digits that are mostly $ 9$'s. We can calculat the exact value of $ s(a_n)$ the following way: we have the number equal to $ 499....99 - (10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}})$ where each of $ n - 1$ "summands" of the form $ - 10^k$ turns one $ 9$ in the decimal representation into an $ 8$. therefore $ s(a_n) = 1\cdot 4 + (n - 1)\cdot 8 + (2^n - 1 - (n - 1))\cdot 9 = 9\cdot 2^n - 4 - n$ Now we need to calculate $ a_n^2$. We have: $ a_n^2 = 25\cdot 10^{2^{n + 1} - 2} - 2\cdot 5\cdot 10^{2^n - 1}(10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}} + 1) + (10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}} + 1)^2 = 25\cdot 10^{2^{n + 1} - 2} - 10^{2^n}(10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}} + 1) + (10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}} + 1)^2$ On this point note that $ 10^{2^{n + 1} - 2} = 10^{2^n}\cdot 10^{2^n - 2}$ and that for each $ i$, $ 1\leq i\leq n$ we have $ 10^{2^n}\cdot 10^{2^n - 2^i} = (10^{2^n - 2^{i - 1}})^2$ therefore we can simplify $ a_n^2$ to: \[ 24\cdot 10^{2^{n + 1} - 2} + 1 + 2\cdot \prod_{1\leq j < k\leq n}(10^{2^n - 2^j}\cdot 10^{2^n - 2^k})\] Now due to the lemma we now that $ 10^{2^n - 2^a}\cdot 10^{2^n - 2^b}\neq 10^{2^n - 2^c}\cdot 10^{2^n - 2^d}$ or otherwise that would contradict the lemma. Therefore $ a_n^2$ in a decimal representation can be seen as $ 24...1$ where between $ 4$ and $ 1$ there are some $ 2$s and all other zeroes. The number of $ 2$s is exactly the number of choices of $ 2$ elements out of $ n$. Therefore $ s(a_n^2) = 2 + 4 + 1 + \binom{n}{2}\cdot 2 = n^2 - n + 7$ meaning that: \[ \frac {s(a_n)}{s(a_n^2)} = \frac {9\cdot 2^n - 4 - n}{n^2 - n + 7}\] so $ \lim_{n \to \infty}\frac {s(a_n)}{s(a_n^2)} = \infty$ and the expression is unbounded

Jure the frEEEk wrote: No, the expression is unbounded. I managed to produce the following counterexample after a lot of computer work. I have no idea how one could get such an idea without a computer in a couplle of hours time $ a_n = 5\cdot 10^{2^n - 1} - (10^{2^n - 2} + 10^{2^n - 4} + \cdots + 10^{2^n - 2^{n - 1}} + 1)$. \[ \frac {s(a_n)}{s(a_n^2)} = \frac {9\cdot 2^n - 4 - n}{n^2 - n + 7}\] so $ \lim_{n \to \infty}\frac {s(a_n)}{s(a_n^2)} = \infty$ and the expression is unbounded Very very nice demo! (and I carefully checked it) I tried some numbers in this direction but did not see any solution. Great congrats Jure!

Thanks Has anyone taught about how many generalisations this problem has. Just some ideas (not sure all are true:D) $ \frac{s(n^2)}{s(n)}$ being unbounded changing the base from $ 10$ to something else (i think the same argument work for bases $ 2k$ where $ k>1$). Is it true for base $ 2$? $ \frac{s(n)}{s(n^3)}$ unbounded? $ \frac{s(n)}{s(p(n))}$ unbounded? for any non-constant polinomial $ p$

Jure the frEEEk wrote: $ \frac {s(n)}{s(p(n))}$ unbounded? for any non-constant polinomial $ p$ For this one, it's not true for all non-constant $ P(n)$ : Choose $ P(n)=10n$, for example

I've done for over 8 hours but still can't solve it. I can just give some examples:\ $49^2=2401,149^2=22201,14499^2=210221001,...$ it's hopeless,I think_

if one requires a similar problem tested earlier,see here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1222814&sid=3e12baf39d7ba34dcb3b3eb4565fc3ea#p1222814

Can't something close to $ n \approx 10^k \sqrt{10}$ be done? (I'm not sure)

edited ( fakesolved )

WizardMath wrote: It is a known result that a non zero digit appears infinitely many times in the decimal expansion of $\sqrt{10}$ so we are done. (For eg see Sierpinski's paper). I think it's generally not true. Can you fully explain it?

WizardMath wrote: Let $n=[10^k\sqrt{10}]$ where$[.]$ is the floor function. It is a known result that a non zero digit appears infinitely many times in the decimal expansion of $\sqrt{10}$ so we are done. (For eg see Sierpinski's paper). No your proof is wrong. taking that $ n^2<10^{2k+1} $ and $ s(n^2) $ is really big. probably upper will be more suitable and we don't even know how $ n^2 $s decimal expression will be. Whatever you have in mind, I think it might be wrong. (Because if it was right, the proof would be at least 5 times longer than that. )

@above, edited.

There does not exist such $c$. Select $n = 10^{4k} + 2 \cdot 10^{3k} - 10^{2k} + 2 \cdot 10^k + 1$ for some large positive integer $k$. Then it is easy to see that we may make $s(n)$ as large as we wish while \[s(n^2) = s(10^{8k} + 4 \cdot 10^{7k} + 2 \cdot 10^{6k} + 11 \cdot 10^{4k} + 2 \cdot 10^{2k} + 4 \cdot 10^k + 1) \le 16\]when $k$ is large. This implies the conclusion.