5

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.

xrfxlp
  • 1,505
Tapi
  • 1,688
  • 1
    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 04 '19 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 04 '19 at 15:50
  • 2
    $1111111111^2=1234567900987654321$ and the sum of digits is 82, not 100. – Julian Mejia Jun 04 '19 at 16:48
  • @JulianMejia Yes, that's right. It's not $100$ but $82$ since $1111111111^2 = 1234567900987654321$. I just noticed that it works fine till nine 1's because the squares of the numbers retain the symmetry until the number $1111111111$. – Tapi Jun 04 '19 at 17:00
  • 1
    $n^2$ can't exceed 11 nines. –  Jun 04 '19 at 20:35
  • 1
    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 07 '19 at 02:37
  • As @JulianMejia also observed, we can forget about repunits. We have a simple formula for the sum of digits of the square of a repunit. – Jyrki Lahtonen Jun 07 '19 at 07:08
  • @Mirko I've edited my answer in response to your comment. – Tapi Jun 07 '19 at 14:08

1 Answers1

4

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$.

san
  • 13,692
  • 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. –  Jun 07 '19 at 17:28