Find the smallest positive integer such that $S(n)=10, S(n^2)=100$.

Consider the numbers: $$1, 11, 111, 1111, 11111$$ and so on. $$S(1)^2=S(1^2)$$ and, in fact, $$(S(n))^2=S(n^2)$$ for all the numbers where $$S(n)$$ is the sum of the digits of the number $$n$$.

Edit 1: $$S(n^2)$$ is the sum of the digits of the number $$n^2$$. For instance,

let $$n=11, S(11)=1+1=2$$ and $$S(n^2)=S(11^2)=S(121)=1+2+1=4=({S(11))}^2=2^2=(S(n))^2$$

$$S(n)$$ is the sum of digits of $$n$$ whatever be $$n$$. $$n$$ does not always need to be of the form: $$1$$ followed by only $$1$$'s.

Find the smallest positive integer such that $$S(n)=10, S(n^2)=100$$.

The immediate hint that comes to my mind is that it has to be less than $$1111111111$$ (ten 1's) from the context given. But I've no clue as to how I'll proceed further.

The answer given is $$1101111211$$.

I am not allowed to use the calculator. I know that $$S(n)$$ is equivalent to $$n (\mod 9)$$ and both $$S(n)$$ and $$S(n^2)$$ are equivalent to $$1(\mod 9)$$ but I don't know how to use this here. Am I missing something?

Can anyone suggest a shorter, simpler method?

Edit 2: The answer along with the problem was published in Mathematical Excalibur in volume $$22$$, number $$3$$, page $$2$$ as Remark $$2$$. Here's the link of the PDF version.

• Why does there have to be a 0 and a 2? I see no innate reason why a nine-digit number with all digits positive couldn't in principle satisfy the condition. Even if the minimal number is ten digits, it could easily have two 0s and a 3 in it, or etc. Where did you come across this problem? That might help inform what techniques are expected to be used in solving it. – Steven Stadnicki Jun 4 at 15:43
• @StevenStadnicki Yes, that's a mistake. A nine-digit number or maybe lesser would also hold. I was initially trying to find the least possible 10-digit number, but that's incorrect. I came across this problem while solving an assignment on Sum of Digits of Positive Integers given by my prof (I'm a high school student). – Tapi Jun 4 at 15:50
• $1111111111^2=1234567900987654321$ and the sum of digits is 82, not 100. – Julian Mejia Jun 4 at 16:48
• $n^2$ can't exceed 11 nines. – Roddy MacPhee Jun 4 at 20:35
• Could you please: (1) Define $S(n)$ before you use it, and (2) clarify what you mean by ${S(n)}^2=S(n^2)$. You do not mean that $S(4)=4$, and $S(4)^2=4^4=16$ and$S(4^2)=S(16)=1+6=7$, and thus $16=7$, so what do you mean? Do you mean $S(n)=10^{n-1}+10^{n-2}+\cdots+10^0$ ? Do you mean: (a) $S(n)$ is the sum of the digits of the number $n$, but (b) we only consider numbers $n$ of the form $11\dots1$ ? So $S(111)^2=(1+1+1)^2=3^2=9$ and $S(111^2)=S(12321)=1+2+3+2+1=9$. Do you mean $S(n)^2=S(n^2)$ for all $n$ of the form $10^k+10^{k-1}+\cdots+10^0$, for some $k\ge0$ ? – Mirko Jun 7 at 2:37

For any natural number $$n=\sum_{i=0}^k a_i 10^i$$ with $$0\le a_i\le 9$$, define $$S(n)=\sum_{i=0}^k a_i$$. Then $$n^2=\left(\sum_{i=0}^k a_i 10^i\right)^2=\sum_{j=0}^{2k}\left(\sum_{i=0}^j a_i a_{j-i} \right)10^j,$$ where $$a_i=0$$ if $$i>k$$. Then $$S(n^2)\le \sum_{j=0}^{2k}\sum_{i=0}^j a_i a_{j-i} = \left(\sum_{i=0}^k a_i\right)^2=S(n)^2$$ and we have equality if and only if $$c_j:=\sum_{i=0}^j a_i a_{j-i}<10$$ for all $$j$$.

It follows that if $$S(n^2)=S(n)^2$$, then $$a_i<4$$. In fact, if $$a_j\ge 4$$, then $$c_{2j}=a_j^2+\sum_{i=0}^{j-1}a_i a_{2j-i}\ge 16,$$ which is impossible.

It also follows that if $$S(n^2)=S(n)^2$$, and some $$a_j=3$$, then $$a_i\le 1$$ for all $$i\ne j$$. In fact, if $$a_j=3$$ and $$a_i\ge 2$$ for some $$i\ne j$$, then $$c_{j+i}=2a_j a_i+\sum_{\underset{l\ne i,j} {l=0} }^{j+i}a_l a_{j+i-l}\ge 12,$$ which is impossible.

If we now set $$L(j)=\# \{a_i,\ a_i=j\}$$ (which depends on $$n$$), then, if $$S(n)^2=S(n^2)=100$$, by the previous results necessarily we have $$(L(1),L(2),L(3))\in\{(10,0,0),(8,1,0),(6,2,0),(4,3,0),(2,4,0),(0,5,0),(7,0,1)\}.$$
In principle you now can try these combinations in order to see which satisfies $$c_j<10$$ for all $$j$$. For example, the smallest example with $$(L(1),L(2),L(3))=(10,0,0)$$ is $$n=10\ 111\ 111\ 111$$. Using an exhaustive search with Mathematica, one finds the smallest example with $$(L(1),L(2),L(3))=(8,1,0)$$ is $$n=1101111211$$ (which is the example you mentioned and the absolute smallest example), and the smallest example with $$(L(1),L(2),L(3))=(4,3,0)$$ is $$n=1121102002$$. Higher examples require too much time using Mathematica, but I think that one can prove that the smallest example with $$(L(1),L(2),L(3))=(0,5,0)$$ is $$n=2000020002022$$. For this one can use that if $$S(n^2)=S(n)^2$$, and for some $$j_1 we have $$a_{j_1}=a_{j_2}=a_{j_3}=2$$, then $$j_2-j_1\ne j_3-j_2$$. In fact, if $$a_{j_1}=a_{j_2}=a_{j_3}=2$$ and $$j_2-j_1= j_3-j_2$$ for some $$j_1, then $$c_{2j_2}=(a_{j_2})^2+2a_{j_1} a_{j_3}+\sum_{\overset {l=0}{l\ne j_1,j_2,j_3} }^{2j_2}a_l a_{2j_2-l}\ge 12,$$ which is impossible.

I am also pretty sure that the smallest example with $$(L(1),L(2),L(3))=(7,0,1)$$ is $$n=10101111013$$ and that the smallest example with $$(L(1),L(2),L(3))=(6,2,0)$$ is $$n=10101011122$$. For $$(L(1),L(2),L(3))=(2,4,0)$$ I didn't found (nor searched with purpose) a smallest example.

May be there are some other features than trying all possibilities by hand (or by computer).

$${\bf{Edit:}}$$ If you set $$L(k)=\min\{n: S(n)^2=S(n^2)=k^2\}$$ then

$$L(1)=1$$,

$$L(2)=2$$,

$$L(3)=3$$,

$$L(4)=13$$,

$$L(5)=113$$,

$$L(6)=1113$$,

$$L(7)=11113$$,

$$L(8)=1011113$$,

$$L(9)=101011113$$,

$$L(10)=1101111211$$,

$$L(11)\le 1001101111211$$.

• since $3\mid 9$, we have the sum of digits of a number in base 10, tells us the remainder on division by 3. This means $n$ and $n^2$ are both remainder 1. Similarly the sums being even tells us that both have an even number of odd digits. – Roddy MacPhee Jun 7 at 17:28