10
$\begingroup$

I noticed when listing out palindromes in bases $2$ and $3$ that they seem not to share any palindromes (other than trivial single-digit palindromes). However, when I tried to prove this, I couldn't solve it. I proved it for numbers with an even number of digits in base $3$ by using the fact that a number ending with the digit $0$ is trivially a non-palindrome since leading zeroes don't count as digits, but I can't get it for numbers with an odd number of digits in base $3$.

I also used the fact that $$n\equiv \operatorname{sdig}_b(n) \mod{(b+1)}$$ where $\operatorname{sdig}_b(n)$ is the sum of the digits of $n$ in base $b$.

Can somebody help me prove this?

$\endgroup$
  • $\begingroup$ I assume you mean palindromes other than $0$ and $1$. $\endgroup$ – aschepler Sep 26 '17 at 23:35
  • $\begingroup$ @aschepler Yeah, palindromes with more than one digit. I'll clarify in the question. $\endgroup$ – Franklin Pezzuti Dyer Sep 26 '17 at 23:36
  • $\begingroup$ maybe a pigoenhole principle argument may get you somewhere $\endgroup$ – user451844 Sep 26 '17 at 23:40
  • $\begingroup$ I believe that it is better the tag (numeral-systems), and I don't know if your question is related to combinatory. $\endgroup$ – user243301 Sep 26 '17 at 23:45
  • 2
    $\begingroup$ An idea, if you want to explore further. For a ternary palindrome to not be divisible by 2, it must be of odd length and have 1 as a middle digit. The numbers around the middle of the ternary representation mostly fully determine the numbers around the middle of the binary representation and both need to be symmetric. Maybe that could be a starting point for finding some rules on which ternary palindromes can have a binary counterpart. $\endgroup$ – JollyJoker Sep 27 '17 at 8:38
4
$\begingroup$

Having "magically" found counterexamples, let us explore how we could find at least the first one. Do we really face the specter of having to run thousands of trials? Not if we apply a little ingenuity.

A base 2 palindrome must be odd or else the reverse base 2 representation has an initial zero, not allowed. Then the base 3 representation, being odd, must have an odd sum of digits (c.f. the base 10 test for a multiple of 3). The only base-3 palindromic representations matching this condition have the form $a1a*$ where $a$ is a base 3 representation with no initial zeroes and $a*$ is obtained by reversing the digits of $a$ ($a*$ keeps any initial zeroes corresponding to the terminal zeroes of $a$). Note that not allowing any initial zeroes in $a$ automatically enables us to dodge multiples of 3.

Let us select $a=110_3$ as an example. Keeping the terminal zero as an initial zero of $a*$ gives $a*=011_3$ and thus the odd base 3 palindrome $1101011_3$.

Now we check whether this is palindromic in base 2. A convenient way to do this is to first convert to base 4. Treat the base 3 representation as a polynomial in which the digits, including zeroes, are successive coefficients of decreasing powers of $x$ and evaluate at $x=3$ using synthetic division. In base 4 you use the "multiplication facts" $3×2=12$ and $3×3=21$ to carry out the arithmetic. Applying this technique to $1101011_3$:

$$1=1$$ $$1×3+1=10$$ $$10×3+0=30$$ $$30×3+1=211$$ $$211×3+0=1233$$ $$1233×3+1=11032$$ $$11032×3+1=33223$$

So $1101011_3=33223_4$, and converting each base 4 digit to the appropriate pair of bits then gives $1111101011_2$.

This fails to be a palindrome. A systematic trial would start with $a=1$ and proceed to $a=2, a=10_3$, etc. The first 26 trials fail, on trial 27 the reader can verify that $a=1000_3$ gives, properly, $100010001_3=1213303_4=1100111110011_2$. This is $6643_{10}$.

$\endgroup$
  • 1
    $\begingroup$ I appreciate the explanation, rather than just a bald answer. Thanks! (+1) $\endgroup$ – Franklin Pezzuti Dyer Sep 28 '17 at 23:09
11
$\begingroup$

You were not able to prove it because it's not true. The OEIS has the first 17 of them as sequence A060792, and it is not known whether any more exist.

$\endgroup$
  • $\begingroup$ The referenced sequence has only 11 terms greater than 1. Still +1. $\endgroup$ – Oscar Lanzi Sep 27 '17 at 2:13
  • 2
    $\begingroup$ @OscarLanzi Click on the first entry under "Links" to see the "B-File" for 4 more. $\endgroup$ – aschepler Sep 27 '17 at 4:32
  • $\begingroup$ The fact that it's not known whether any more exist suggest that OP's quest for a proof was pretty hard. The lower bound for the first unknown one is 3^93, or a bit over 3x10^44, suggesting any current search techniques need (almost) sqrt(n) steps, which is trivial as half the digits of a palindromic number mirror the other half. $\endgroup$ – JollyJoker Sep 27 '17 at 7:37
  • $\begingroup$ How is the lower bound "only" $3^{93}$? Candidates must have an odd number of base-3 digits, so any that are at least $3^{93}$ must also be at least $3^{94}$. $\endgroup$ – Oscar Lanzi Sep 28 '17 at 23:54
8
$\begingroup$

Sadly, $6643_{10}=1100111110011_2=100010001_3$ is a palindrome in bases $2$ and $3$. $1422773$ and $5415589$ also satisfy the property.

$\endgroup$
  • 2
    $\begingroup$ Aww, what a tragedy... $\endgroup$ – Franklin Pezzuti Dyer Sep 26 '17 at 23:58
  • $\begingroup$ @Nilknarf Yeah, it's disappointing. $\endgroup$ – Carl Schildkraut Sep 26 '17 at 23:59
  • 5
    $\begingroup$ So if I'm sharing a taxicab from Baltimore Washington Airport to the Capital and it's numbered 6643, we'll have something to talk about. Think Ramanujan would have known this property? $\endgroup$ – Oscar Lanzi Sep 27 '17 at 2:05

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.