8
$\begingroup$

Consider a number formed by concatenating all the natural numbers from $1$ to $n$, for some $n>1$.

(E.g. with $n=13$ this number would be $12345678910111213$.)

Is it possible for such a number to be a palindrome?

Please provide either an example or a proof of impossibility.

I found this puzzle in the 1996 All-Russian Mathematical Olympiad.

$\endgroup$
9
  • 1
    $\begingroup$ Well, I know of one example... $\endgroup$ Sep 15, 2016 at 0:01
  • 1
    $\begingroup$ @A.Mirabeau Edited to exclude the trivial case :-) $\endgroup$ Sep 15, 2016 at 0:02
  • 1
    $\begingroup$ Hm, this puzzle seems familiar... :P $\endgroup$
    – Deusovi
    Sep 15, 2016 at 0:11
  • 2
    $\begingroup$ Note that a palindromic concatenation of numbers is not necessarily impossible in all bases; for instance, in binary, n = 3 quite happily produces the palindrome 0b11011. $\endgroup$ Sep 15, 2016 at 0:20
  • 1
    $\begingroup$ Have a look at math.stackexchange.com/questions/266124 $\endgroup$
    – Watson
    Sep 15, 2016 at 9:58

3 Answers 3

4
$\begingroup$

(I'm sure I saw almost exactly this question somewhere in the last week or thereabouts. Maybe my brain's playing tricks. I don't think I read the 1996 All-Russian Mathematical Olympiad recently. Perhaps there was another question about concatenated consecutive numbers.)

The answer is that

it is not possible.

Why?

Suppose $n$ has $k$ digits. By inspection $k>1$. Let $m$ consist of the last $k-1$ digits of $n$; then the end of our monstrous number looks like $k-1$ 9s, then the first digit of $n$, then $k-1$ 0s, then another $km$ digits. Therefore its start looks like the reverse of that: $km$ digits, then $k-1$ 0s, then the first digit of $n$, then $k-1$ 9s.

But

this can't happen. That string of $k-1$ zeros after the first $km$ digits can't include the first digit of any of the constituent numbers making up the monstrous number, so they are in fact the final $k-1$ digits of a $k$-digit number. But then they cannot possibly be followed by a single digit and then $k-1$ 9s; rather, they must be followed by a single digit, $k-2$ 0s, and a single 1. Contradiction.

$\endgroup$
6
  • $\begingroup$ Sniped! Was working on it this whole time! $\endgroup$ Sep 15, 2016 at 0:13
  • $\begingroup$ Sorry! I think I happened to see it very soon after it was posted. $\endgroup$
    – Gareth McCaughan
    Sep 15, 2016 at 0:14
  • $\begingroup$ Out of curiosity (I know this wasn't part of the question), for which bases other than 10 would this proof work? @A.Mirabeau noticed that palindromic concatentaion is possible in binary, for example; is it possible in ternary or any higher bases? $\endgroup$ Sep 15, 2016 at 0:24
  • $\begingroup$ I think it works in any base higher than binary. $\endgroup$
    – Gareth McCaughan
    Sep 15, 2016 at 0:38
  • $\begingroup$ The last three digits have to be $321$, not what you say. The approach is good. The largest block of zeros cannot be mirrored earlier $\endgroup$ Sep 15, 2016 at 3:33
4
$\begingroup$

I have checked your question, and you do not say it must be in base 10. Maybe my assumtion is wrong.

Yes it always happen in base 1
1,2 base 10 = 1,11 base 1
Concatenate it will become 111

$\endgroup$
1
  • $\begingroup$ OK, you found an unintended loophole :-) Base 10 was supposed to be an unspoken assumption, but I have to admit this is a kinda-sorta valid answer. $\endgroup$ Sep 15, 2016 at 12:50
1
$\begingroup$

My answer is:

No, except for maybe a few small base examples, e.g. $b=2,n=3:\;11011_2$

Because:

Consider the final integer in such a number. Let's assume $b=10$. Let's say it is $4131211101987654321$. The number that precedes this is $4131211101987654320$, which ends in a $20$ making continuity impossible as the theoretical last number would have to start with a number needing a $0$, then a $2$, then a $3$, and so on. The next number would have to end in a number needing a $19$, but the most significant digits of the number won't have changed. For an example, the last few digits are now $41312111019876543204131211101987654321$.

$\endgroup$
1
  • $\begingroup$ "making continuity impossible as the next number would have to start with a 0" - I don't understand this bit. What if the final integer $n$ is something like 1987654321? Then $n-1$ ending in a $0$ is perfectly valid from the point of view of palindromicity. (Unless I'm misunderstanding what you mean?) $\endgroup$ Sep 15, 2016 at 13:06

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.