12
$\begingroup$

The sequence of numbers 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 11, 22,... (A056964 in the OEIS), in which the nth term equals n+reversal of digits of n, poses a number of intriguing puzzles. Here just four:

  1. Does it contain infinitely many square numbers?
  2. Infinitely many cubes?
  3. Infinitely many pairs of consecutive numbers (like 887 and 888, both in the sequence)?
  4. Arbitrarily long sets of consecutive numbers?
$\endgroup$
  • 2
    $\begingroup$ Did you miss one, or did you write "four" when you meant "three"? And do you know the answers to all three (four?) of your questions? $\endgroup$ – Gareth McCaughan Jun 23 at 23:03
  • $\begingroup$ @GarethMcCaughan I meant three, but, come to think of it, I might as well add a fourth question. I know the answer to three of the four. $\endgroup$ – Bernardo Recamán Santos Jun 23 at 23:09
  • $\begingroup$ Questions 1 to 3 have been answered satisfactorily by Gareth, but answer to question 4 is not convincing. $\endgroup$ – Bernardo Recamán Santos Jun 30 at 1:36
12
$\begingroup$

Partial answer (resolves three of the four questions, probably the three to which OP knows the answer :-) )

Infinitely many squares:

Yes. Let $Z$ be any sequence of $0$s; then $2Z4Z2$ reverses to itself and adding yields $4Z8Z4$ which is the square of $2Z2$.

Infinitely many cubes:

Yes. Let $Z$ be any sequence of $0$s; then $1Z3ZZ00$ reverses to $3Z1$ and adding yields $1Z3Z3Z1$ which is the cube of $1Z1$.

Infinitely many pairs of consecutive numbers:

Yes. The reverse of $9^n51^n$ is $1^n59^n$ and adding these yields $1^{2n+1}0$. One more than this is $1^{2n+2}$ which you get by reverse-and-add on $1^{n+1}0^{n+1}$.

Arbitrarily long sequences of consecutive numbers:

I don't know. I suspect not. Reversing-and-adding numbers up to $10^7$ the only length-3 sequences I find are 10,11,12 and 1331,1332,1333, and neither of those extends to length 4. Going up to $10^8$ we find a few more length-3 sequences, all involving 8-digit numbers beginning $13$, and again nothing of length 4. So I conjecture not very confidently that there are no length-4 sequences; I conjecture even less confidently that the length-3 sequences can be characterized nicely, just because they seem to be few in number and have some common features. However, for the first of the 8-digit ones I've looked at (13210131+{0,1,2}) there are quite a lot of ways to make each of the three numbers in the sequence. The second and third numbers in the sequence seem like they might be quite restrictive, but the possibilities for the first appear to be all over the place. The more I look at this the less optimistic I am that there's an elegant proof to be had. (And the less confident I am that there aren't longer sequences: it may just be that a bunch of coincidences need to happen, and up to $10^8$ there isn't enough time for many of them all at once.)

$\endgroup$
  • 1
    $\begingroup$ hope you dont mind me editing the mathjax ;) $\endgroup$ – Omega Krypton Jun 23 at 23:33
  • 1
    $\begingroup$ I don't mind, but I also don't see any particular reason for those bits to be MathJax rather than plain text: they aren't using any of its features. $\endgroup$ – Gareth McCaughan Jun 23 at 23:45
  • $\begingroup$ @OmegaKrypton Keep in mind that introducing MathJax to a page causes it to require longer load, processing and rendering time to display. If this doesn't really add readability to the content, it's not worth the extra cost. (Tiny, trivial edits are discouraged as well; if MathJax isn't actually materially improving readability or comprehension, adding it probably qualifies as a trivial edit.) $\endgroup$ – Rubio Jun 30 at 0:23
3
$\begingroup$

EDIT: Added more stepwise explanation, hopefully it is clear enough to be reproduced
EDIT 2: It was brought to my attention that the proof does not work for single digits (shown by a clear example). That is solved not, and the conclusion is the same.
EDIT 3: Changed the example for the regular case, because the example actually wasn't a regular case
EDIT 4: Added a lot of MathJax. Hope I didn't miss anything

Gareth McCaughan answers questions 1-3 beautifully, here is my proof for q4 (is there an arbitrarily long sequence of number that can be written as M+rev(M)?):

The maximum length of a sequence we can find is 3

Proof:

Let us start with number $N_0$ which fulfills our rule, namely $N_0=M_0+rev(M_0)$
Where $rev(M)$ is the digit reverse of M: $rev(123)=321$ Let $N_0$ be an even number
Let $M_0$ be a number of $L_0$ digits
Let $p_0$ and $r_0$ be the first and last digit of $M_0$, such that:
$p_0$ and $r_0$ are digits, that is in the range ${0..9}$ $p00...00r <= M_0 <= p99...99r$
Let $N_{-2}$ equal $N - 2$, where also $N_{-2}$ can be written as $M_0+rev(M_0)$
Let the first and last digits of $M_{-2}$ be $p_{-2}$ and $r_{-2}$

If $N_0$ is an even number, so must be $N_{-2}$
Therefore, $p_{-2}+r_{-2}$ must be even, because that is the only way the last digit of $M_{-2}+rev(M_{-2})$ can be even and therefore $N_{-2}$ can be even
The last digit of $N_{-2}$ is the last digit of $p_{-2}+r_{-2}$. Which can be written as $p_{-2}+r_{-2} mod 10$
The same is true for $p_0$ and $r_0$ regarding the last digit of $N_0$

Since $N_{-2}$ is $2$ less than $N_0$, so must the last digit of $N_{-2}$ be $2$ less than $N_0$, and therefore must '$p_{-2}+r_{-2} mod 10$' be $2$ less than '$p_0+r_0 mod 10$'
An exception [case 1] occurs is when $p_0+r_0 mod 10 = 8$ and $p_{-2}+r_{-2} mod 10 = 0$
Special cases [case 2] occur when: $p_0+r_0 = 10 + p_{-2}+r_{-2} - 2$ or $10 + p_0+r_0 = p_{-2}+r_{-2} - 2$
Exception [case 3] is when number of digits $L_0$ is not equal to $L_{-2}$
Exception [case 4] is when $M$ and $rev(M)$ are single digits
I will cover these expections later.

For the regular case, where $p_0+r_0 = p_{-2}+r_{-2} + 2$ and [case 1, 2 and 3] do not apply, we can state:
$N_{-2}$ can be at most $p_{-2}99...99r_{-2} + r_{-2}99...99p_{-2}$
So $N_{-2}$ is at most $(p_{-2}+1)*10^L + (r_{-2}+1)*10^{L-1} - 20 + p_{-2} + r_{-2}$
Which can be written as: $(p_{-2} + r_{-2} + 2)*10^{L-1}$ We know that $p_0+r_0 = p_{-2}+r_{-2}+2$, so:
$N_{-2}$ is as most $(p_0 + r_0)*10^{L-1} + p_0 + r_0 - 2 - 20$
$N_0$ is at least $(p_0 + r_0)*10^{L-1} + p_0 + r_0$
For the more visual-minded, an example:
Given $L=4$: $N_{-2} <= 2994 + 4992$ [$p_{-2}=2,r_{-2}=4,p_0+r_0=6$]
Given $L=4$: $N_0 >= 2006 + 6002$ [$p_{-2}=2,r_{-2}=6,p_{-2}+r_{-2}=8$]
$N_{-2} <= (2+1 + 4+1)*10^{4-1} - 20 + 2 + 4$
$N_{-2} <= 8000 - 20 + 6$
$N_{-2} <= 7986$
$N_0 >= (2 + 6)*10^{4-1} + 2 + 6$
$N_0 >= 8008$
Whatever $p$ and $r$ we choose, $N_{-2}$ can never be more that $N_0-22$, so it cannot be $N_0-2$, which is a condradiction. Therefore, our initial statement that an even number $N_{-2}$ exists which equals $N_0 - 2$, where $N_0=M_0+rev(M_0)$ is false.

However, we didn't look at our exceptions yet.
What if $L_0$ does not equal $L_{-2}$ [case 3], which is the case in for example odd number $1300 + 0031 = 1331$ and $617 + 716 = 1333$
This can only occur if the number with smallest $L$ overflows to add an additional digit. This must be a leading $1$
Therefore, the number with the largest $L$ must not overflow
If that number does not overflow, its $p+r$ must equal $1$, since the leading digit equals $1$
If that is the case, then the last digit must be a $1$
This is an odd number. Therefore, this exception does not apply to our proof of the regular case and our proof holds

This same argument goes for [case 2].
The statement $p_0+r_0 = 10 + p_{-2}+r_{-2} - 2$ or $10 + p_0+r_0 = p_{-2}+r_{-2} - 2$
Has the same meaning as saying either $N_0$ or $N_{-2}$ is the result of digit overflow
This means that also the first digit will overflow
Therefore, this can only happen is the length of $L_0$ does not equal $L_{-2}$
As mentioned for [case 3], this can only results in odd numbers given our conditions
Therefore, the proof of our regular case still holds

And again, the same argument goes for [case 1] The case where $p_0+r_0 mod 10 = 8$ and $p_{-2}+r_{-2} mod 10 = 0$ is just a special case of $p_0+r_0 = 10 + p_{-2}+r_{-2} - 2$
This only happens if the last digit overflows
Therefore, the first digit must overflow too and $L_0$ must not have the same length as $L_{-2}$
We already showed that if that is the case, not valid even number exists given our conditions

For [case 4], this does not work, so we have to do something different
Let's start by showing that this will work for any 2-digit number or larger, before going into the single digits.
For this, we go in from a different angle, but the proof is the same Again, let $N_0$ and $N_{-2}$ be two even nubmers, $N_0=N_{-2}+2$, written as $N_0=M_0+rev(M_0)$ and $N_{-2}=M_{-2}+rev(M_{-2})$
If $M_{-2}=p_{-2}r_{-2}$, then $N_{-2}=p_{-2}r_{-2}+r_{-2}p_{-2}$
$N_{-2} = 10*(p_{-2}+r_{-2}) + p_{-2} + r_{-2}$
$N_{-2} = 11*p_{-2} + 11*r_{-2}$
And since we know $p_0 + r_0$ must equal $p_{-2} + r_{-2} + 2$:
$N_0 = 10*(p_{-2}+r_{-2}+2) + p_{-2} + r_{-2} + 2$ $N_0 = 11*(p-2) + 11*(r-2) + 22$ So $N_0$ is $22$ greater than $N_{-2}$, and can therefore not be $2$ greater than $N_{-2}$. This pair cannot exist.
It's not surprising, because there is no wiggle-room for additional $9$'s in the middle of the number.

For a 3-digit number this also holds:
The maximum value of $N_{-2}$ is $p_{-2}9r_{-2} + r_{-2}9p_{-2}$
$N_{-2} = 100*(p_{-2}+r_{-2}) + 2*90 + p_{-2} + r_{-2}$
$N_{-2} = 101*p_{-2} + 101*r_{-2} + 180$
$N_0 = p_00r_0 + r_00p_0$
$N_0 = 100*(p_0+r_0) + 0 + p_0 + r_0$
$N_0 = 100*(p_{-2}+r_{-2}+2) + p_{-2} + r_{-2} + 2$
$N_0 = 101*p_{-2} + 101*r_{-2} + 202$
So $N_0$ is at least $22$ greater than $N_{-2}$ and can therefore not be $2$ greater than $N_{-2}$

For single digits this does not hold. This is shown by $M_0=6$ and $M_{-2}=5$, leaving $N_0=12$ and $N_{-2}=10$
Any $N$ below $10$ cannot be odd as it must be constructed by adding 2 single digits, where $M=rev(M)$, so $N$ must be even
This means the in the range $10<=N<=21$ we have potential for more than 3 consecutive numbers
(Note than $N=20$ must be constructed from multi-digit numbers, so if it can be written as $M+rev(m)$, then $22$ cannot)
We know the even numbers in this range up to and including $18$ are possible $(10,12,14,16,18)$
We know that $11=10+01$
We know all odd number in this range must be constructed of multi-digit numbers
For numbers $13,15,17$ to be constructed of multi-digit numbers we cannot use digit overflow (because single digits required)
For number $19$ we cannot use digit overflow (has all $9$'s behing leading $1$)
For any number in the 10's constructed from multi-digit numbers, we need an $M$ with lagging/leading $0$ to leave a $1$ as first digit
the only 2-digit number that fulfills these rules is $10$
So in this range only odd number $10+01 = 11$ can be written as $M+rev(M)$
This gives us a nive bonus trio of $10, 11, 12$. But that's everything

Of course, we could have just checked every case op to $21$, but where's the fun in that!

To sum up, there are no pairs of even numbers greater than $20$ separated by $2$ that can both be written as $M+rev(M)$, because:
If $N_0$ exists that is an even number and can be written as $M+rev(M)$, the number $N_{-2}$ which is $2$ smaller than $N_0$ cannot be written as $M+rev(M)$.
This means that also $N_{+2}$ which is $2$ bigger than $N_0$ cannot be written as $M+rev(M)$, because if it were, then $N_0$ could not be written that way.
In the range below $20$, this proof does not work. However, we found out that the only odd number in this range that works is $11$. Therefore by similar argument no $N_0 = N_{+2}$ exists for odd numbers below $20$
Therefore, the largest sequence of consecutive numbers that can be written as $M+rev(M)$ is three, where the first and last are odd, and the middle one is even.
Their existence is shown by many examples.

$\endgroup$
  • $\begingroup$ I don't understand this proof. What does "The number N-2 is always smaller than the number N minus 2"? Either "N-2" or "N minus 2" must mean something very different from what I think it does. And how do you get from there to "N-2 cannot be M+rev(M)"? Something to do with the first and last digits, but the actual argument seems to be missing. $\endgroup$ – Gareth McCaughan Jun 30 at 2:30
  • $\begingroup$ Thanks for the feedback. I'll get back with a cleaner proof and definitions of terms used $\endgroup$ – MKBakker Jul 1 at 10:50
  • 1
    $\begingroup$ You say "there are no pairs of even number separated by 2 that can both be written a M+rev(M)" . What about 10 and 12? $\endgroup$ – hexomino Jul 2 at 13:42
  • 1
    $\begingroup$ For completeness, you ought to prove the case with single digits also satisfies your conclusion, as @hexomino raises a good point. $\endgroup$ – El-Guest Jul 2 at 14:06
  • $\begingroup$ Ah yes, of course. There is a lower bound for which this works. I'm guessing it's only the case for single digits but I'll give it some more thought to be sure. It will be low for sure. Since we can check every number below the lower bound, we know the limit of 3 consecutive numbers still holds. And because 2xany single digit is always even, we will not find arbitrarily long sequences there either. $\endgroup$ – MKBakker Jul 3 at 6:58

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.