Kvant Math Problem 1482
Let
Verified: yes
Verdicts: PASS + PASS
Solve time: 7m58s
Source on kvant.digital
Problem
Find all natural numbers $x$ such that the sum $1+2+\ldots+x$ equals the number obtained by prefixing the digit 1 to $x$ (in decimal notation).
P. Filevich
Exploration
Let
$$1+2+\cdots+x=\frac{x(x+1)}2.$$
If the decimal representation of $x$ has $n$ digits, then prefixing the digit $1$ produces the number
$$10^n+x.$$
Hence we seek natural numbers $x$ satisfying
$$\frac{x(x+1)}2=10^n+x,$$
where $n$ is the number of digits of $x$.
Trying small values,
$$x=14:\qquad \frac{14\cdot15}{2}=105,$$
and $105$ is indeed obtained by writing $1$ in front of $05$, not in front of $14$. Thus $x=14$ is not a solution.
For $x=44$,
$$\frac{44\cdot45}{2}=990.$$
Again not of the required form.
The equation becomes
$$x^2-x-2\cdot10^n=0.$$
Therefore
$$x=\frac{1+\sqrt{1+8\cdot10^n}}2,$$
so $1+8\cdot10^n$ must be a perfect square.
Checking a few values of $n$,
$$n=1:\quad 81=9^2,$$
giving $x=5$, and indeed
$$1+2+3+4+5=15,$$
which is obtained by prefixing $1$ to $5$.
$$n=2:\quad 801$$
is not a square.
$$n=3:\quad 8001$$
is not a square.
The crucial point is to determine all $n$ for which
$$y^2=1+8\cdot10^n.$$
Since $10^n=2^n5^n$, the equation is
$$y^2-1=2^{n+3}5^n,$$
or
$$(y-1)(y+1)=2^{n+3}5^n.$$
The factors differ by $2$. That strong restriction should force $n=1$.
Problem Understanding
We must find all natural numbers $x$ such that the triangular number
$$1+2+\cdots+x$$
is exactly the number obtained by placing the digit $1$ in front of the decimal representation of $x$.
This is a Type A problem, a classification problem.
If $x$ has $n$ digits, the condition becomes
$$\frac{x(x+1)}2=10^n+x.$$
The core difficulty is proving that the resulting Diophantine equation has no solutions except the obvious small one.
The answer is
$$x=5.$$
The reason is that the condition reduces to
$$(y-1)(y+1)=2^{n+3}5^n,$$
where the two factors differ by $2$, and powers of $2$ and $5$ cannot be distributed between such close factors except in the smallest case.
Proof Architecture
Lemma 1. If $x$ has $n$ decimal digits, then the number obtained by prefixing the digit $1$ to $x$ equals $10^n+x$. This follows directly from decimal place value.
Lemma 2. Any solution $x$ yields an integer $y$ satisfying $y^2=1+8\cdot10^n$. This is obtained from the quadratic equation for $x$.
Lemma 3. If $y^2=1+8\cdot10^n$, then
$$(y-1)(y+1)=2^{n+3}5^n.$$
This is a factorization of $y^2-1$.
Lemma 4. For $n\ge2$, no such factorization is possible. Since $y-1$ and $y+1$ differ by $2$, their greatest common divisor is $2$; the entire factor $5^n$ must lie in one factor, forcing the other factor to be a power of $2$, which leads to a contradiction.
Lemma 5. For $n=1$, a solution exists and equals $x=5$.
The hardest direction is proving nonexistence for all $n\ge2$. The most delicate lemma is Lemma 4.
Solution
Let $x$ be a solution, and let $n$ be the number of decimal digits of $x$.
By Lemma 1, prefixing the digit $1$ to $x$ produces the number $10^n+x$. The condition of the problem becomes
$$\frac{x(x+1)}2=10^n+x.$$
Multiplying by $2$ and rearranging gives
$$x^2-x-2\cdot10^n=0.$$
Hence
$$(2x-1)^2=1+8\cdot10^n.$$
Set
$$y=2x-1.$$
Then
$$y^2=1+8\cdot10^n,$$
and therefore
$$y^2-1=8\cdot10^n=2^{n+3}5^n.$$
Factoring the left-hand side,
$$(y-1)(y+1)=2^{n+3}5^n.$$
Since the right-hand side is even, $y$ is odd. Thus $y-1$ and $y+1$ are even, and
$$\gcd(y-1,y+1)=2.$$
Assume first that $n\ge2$.
Because $\gcd(y-1,y+1)=2$, only one of the factors $y-1$ and $y+1$ can be divisible by $5$. Since their product contains $5^n$, all of $5^n$ must belong to one factor.
Without loss of generality, write
$$y-1=2^a,\qquad y+1=2^b5^n,$$
where $a\ge1$, $b\ge1$, and $a+b=n+3$.
Subtracting,
$$(y+1)-(y-1)=2,$$
so
$$2^b5^n-2^a=2.$$
Dividing by $2$,
$$2^{,b-1}5^n-2^{,a-1}=1.$$
The left-hand side is odd. Hence exactly one of the two terms is odd.
Since $n\ge2$, the first term is divisible by $5$. If $b\ge2$, then both terms are even and their difference is even, impossible. Therefore $b=1$.
The equation becomes
$$5^n-2^{a-1}=1,$$
or
$$5^n=2^{a-1}+1.$$
Because $n\ge2$, the left-hand side is divisible by $25$. Reducing modulo $4$,
$$5^n\equiv1\pmod4.$$
Thus
$$2^{a-1}+1\equiv1\pmod4,$$
which implies $2^{a-1}\equiv0\pmod4$, so $a-1\ge2$.
Then
$$5^n=2^{a-1}+1\equiv1\pmod8.$$
For odd $n$,
$$5^n\equiv5\pmod8,$$
a contradiction. Hence $n$ is even.
Write $n=2m$. Then
$$5^{2m}-1=(5^m-1)(5^m+1)=2^{a-1}.$$
The two factors on the left are consecutive even numbers. Their greatest common divisor is $2$. Since their product is a power of $2$, each factor must itself be a power of $2$. Thus
$$5^m-1=2,\qquad 5^m+1=4.$$
This gives $5^m=3$, impossible.
Hence no solution exists for $n\ge2$.
It remains to check $n=1$. Then
$$y^2=1+8\cdot10=81,$$
so $y=9$. Therefore
$$x=\frac{y+1}{2}=5.$$
Verification:
$$1+2+3+4+5=15,$$
and $15$ is obtained by prefixing the digit $1$ to $5$.
Thus the only solution is
$$\boxed{x=5}.$$
Verification of Key Steps
The first delicate step is the claim that all powers of $5$ lie in one factor. Since
$$\gcd(y-1,y+1)=2,$$
any common odd divisor of $y-1$ and $y+1$ would divide their difference $2$, which is impossible. Therefore neither factor can share a factor $5$ with the other, and the entire factor $5^n$ must occur in exactly one of them.
The second delicate step is the deduction $b=1$. From
$$2^{,b-1}5^n-2^{,a-1}=1,$$
if $b\ge2$, then $2^{,b-1}5^n$ is even and $2^{,a-1}$ is also even because $a\ge1$. Their difference would be even, contradicting the fact that it equals $1$.
The third delicate step is the argument after obtaining
$$5^{2m}-1=(5^m-1)(5^m+1)=2^{a-1}.$$
Since
$$\gcd(5^m-1,,5^m+1)=2,$$
both factors are powers of $2$. Two powers of $2$ differing by $2$ can only be $2$ and $4$. Indeed,
$$2^r+2=2^s$$
implies
$$2^{r-1}+1=2^{s-1},$$
hence $r=1$ and $s=2$. This yields the contradiction $5^m=3$.
Alternative Approaches
After obtaining
$$(y-1)(y+1)=2^{n+3}5^n,$$
one may write
$$y-1=2u,\qquad y+1=2v,$$
so that
$$uv=2^{n+1}5^n,\qquad v-u=1.$$
Thus $u$ and $v$ are consecutive positive integers whose product contains no prime factors other than $2$ and $5$. Since consecutive integers are coprime, one of them must be a pure power of $2$ and the other a pure power of $5$ times a power of $2$. An analysis of the equation $v-u=1$ then reduces to the same contradiction for $n\ge2$.
The main proof is preferable because the factorization $y^2-1=(y-1)(y+1)$ immediately exposes the arithmetic structure and keeps the argument short.