13
$\begingroup$

Plotting Palindromic Numbers

I made a script that checks numbers through number bases and plots a black pixel if the number is a palindrome in the corresponding base.

If we check the first $256$ numbers (width) and first $256$ number bases (height), and draw a picture by starting in the upper left corner, we get the image on the left.

If we also connect all the $2$-digit palindromes with straight lines, we get the image on the right.

$\hspace{1.15cm}$enter image description here $\hspace{1cm}$ enter image description here

  • The black triangle represents one-digit-palindromes.

  • If we look at the $2$-digit-palindromes, they form straight lines.

  • If we look at the $3$-digit-palindromes, they form parabolas. The first parabola is colored in yellow and located above the red lines as it can be seen on picture on the right.

In general, $D$-digit palindromes form a set of polynomials of degrees $D-1$. But it's not clear on which exact points on those curves the palindromes appear, except for the lines.

Counting Palindromes

The thing that I'm interested in, is counting the palindromes outside the black-triangle-region, among $n$ first natural numbers.

If we count the palindromes among first $n$ numbers in all natural bases $b>1$, but ignore the one-digit-palindromes (ones that fill up the black triangle on the picture),

Which base $b$ will contain the most palindromes?


By computation,

Start counting at $n=1$, then the first palindrome occurs at number $3$ in base $2$.
Base $2$ will hold most palindromes until,

Base $3$ has most most palindromes at $n=26$,
Then base $2$ has most palindromes at $n=27$,
Then base $3$ has most palindromes at $n=28$,
Then base $2$ has most palindromes at $n=31$,
Until base $4$ takes the lead at $n=55$.

After that, all bases $b\ge5$ seem to follow an equation and overtake the lead when $n$ reaches:

$$b^3 - 2b^2 + 4b - 2$$

I checked this for bases up to $16$ and confirmed that $n$ follows the equation: (Starting at $b=5$)

$$ 93,166,271,414,601,838,1131,1486,1909,2406,2983,3646 \dots$$

With my computations so far, I would conjecture that this equation holds for all $b\ge5$

But this requires a proof.

It would be even better if someone can show how to arrive at this formula without relying on computation.

So far, Mastrem showed why the overtake happens at $b^3 - 2b^2 + 4b - 2$, which makes sense. But it is still not shown that it is the only, and the first, overtake that happens.

Deeper analysis of the plot can be found here.

$\endgroup$
8
  • 1
    $\begingroup$ I guess if you only check numbers up to $n$ then the best you can do is just take base $n+1$, since then all numbers are single-digit and thus a palindrome. $\endgroup$
    – user304329
    Commented Apr 13, 2017 at 20:38
  • $\begingroup$ @vrugtehagel I'm not counting the single-digit palindromes as stated in the problem, since the task is trivial then. $\endgroup$
    – Vepir
    Commented Apr 13, 2017 at 20:39
  • 1
    $\begingroup$ Without thinking too much about it I would guess that a larger base implies more palindromes. Because a number $x$ that's a palindrome in base $b$ will also be a palindrome $y$ in base $b+1$, even though the values of $x$ and $y$ are different. For example, every possible palindromic string of zeros and ones in base 2 is also a palindromic string in base 3, even though they represent different numbers. Like $101$. $101$ in base 2 is 5 and $101$ in base 3 is 4. Different values but still a palindromic presentation. And a larger base means more digits to use means more palindromes to construct. $\endgroup$
    – user307169
    Commented Apr 13, 2017 at 21:18
  • 1
    $\begingroup$ @tilper: But the same palindromic string in a higher base may already be above the limit $n$. For example, if $n=6$, then $101$ is a valid palindrome in base $2$, but not in base $3$, as $10>6$. Also note that due to exclusion of single-digit palindromes, as bases $\ge n$ will automatically get the count $0$. $\endgroup$
    – celtschk
    Commented Apr 14, 2017 at 11:08
  • 1
    $\begingroup$ We can rewrite $b^3-2b^2+4b-2$ as $b.b^2-2b^2+3b+b-2=(b-2)b^2+3b+(b-2)$. This shows more clearly that the overtakes happen at $333_5, 434_6, 535_7$ etc. $\endgroup$
    – nickgard
    Commented Apr 14, 2017 at 12:03

1 Answer 1

Reset to default
1
$\begingroup$

We have: $$b^3-2b^2+4b-2=(b-2)b^2+3b+(b-2)$$ and: $$b^3-2b^2+4b-2=(b-1)^3+(b-1)^2+3(b-1)+1$$ For all $b\in\mathbb{N}_{\ge 5}$, let $f(b)$ be the amount of palindromes in base $b$ up to and including $b^3-2b^2+4b-2$ and let $g(b)$ be the amount of palindromes in base $b-1$ up to and including $b^3-2b^2+4b-2$. Now, from the very first 'factorization', we see that: $$f(b)=(b-3)b+4+(b-1)=b^2-2b+3$$ Because, if a palindrome starts with a digit $1\le k\le b-3$, we can choose whatever digit we want for the middele one and when the palindrom starts with $b-2$, we have $4$ options for the middle digit. Also, we can choose a total of $b-1$ two digit palindromes.

Now for $g(b)$. We split this case up into $4$ digits and $3$ digits. If we have a $4$ digit number, the first digit is a $1$ and the second one is $1$ or $0$, so the only two options option are $1111_{b-1}$ and $1001_{b-1}$. All $3$ digit numbers are possible, a total amount of $(b-2)(b-1)$ numbers (because we can't choose $0$ as the leading digit). So when we also include the two digit palindromes: $$g(b)=2+(b-2)(b-1)+(b-2)=b^2-2b+2=f(b)-1$$ And since $b^3-2b^2+4b-2$ is a palindrome in base $b$, but not in base $b-1$, the base $b$ 'takes' over at $b^3-2b^2+4b-2$.

The thing I'm still trying to prove is that this is the first time $b$ 'takes over'. As soon as I know, I'll edit it in

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .