4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jun 4 at 15:43
  • $\begingroup$ @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). $\endgroup$ – Tapi Jun 4 at 15:50
  • 2
    $\begingroup$ $1111111111^2=1234567900987654321$ and the sum of digits is 82, not 100. $\endgroup$ – Julian Mejia Jun 4 at 16:48
  • 1
    $\begingroup$ $n^2$ can't exceed 11 nines. $\endgroup$ – Roddy MacPhee Jun 4 at 20:35
  • 1
    $\begingroup$ 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$ ? $\endgroup$ – Mirko Jun 7 at 2:37
3
+25
$\begingroup$

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<j_2<j_3$ 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<j_2<j_3$, 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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Roddy MacPhee Jun 7 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.