5
$\begingroup$

Edit: Decided to add visual previews of patterns instead of extracting all the polynomials.
Perhaps you have seen something that behaves similarly somewhere else?



For a given $b,d\in\mathbb N$, how can we effectively find all numbers that are $(2d+1)$ digit palindromes in number bases $b+1$ and $b+3$ ?

For example, solutions for case $(d,b)=(1,9)$ are $\{181, 555, 616, 676, 737, 797\} $ since they are palindromic in number bases $10$ and $12$ and have three digits in those number bases.

For arbitrary $b$ and $d$, I generate palindromes computationally. But this does not scale well and gets very inefficient for $(d=3,b\ge200),(d\ge4,b\ge100)$ cases, because there are too many palindromic candidates that need to be checked.

I'm hoping that one could exclude a significant amount of palindromes from the search to make generating these examples for such cases, efficiently plausible.



But more importantly, instead of relying on computations,

Can we solve this problem mathematically for arbitrary $(d,b)$ cases? Because I believe managed to solve it for $(d\in\{1,2\},b\in\mathbb N)$ cases, but I'm not sure how to extend the generating patterns to $d\ge3$, nor how to prove them as they were obtained from computed data only.

It seems that for very small $b$, it is not clear how to predict solutions, but for every $d$ there seems to exist some number base $B_d$ such that for all $b\ge B_d$ the pattern can be used to predict solutions exactly. ($B_d$ is negligible for small $d$)

The best way to visualize patterns is to observe $P_n(d,b)$ which stands for $n^{\text{th}}$ $2d+1$ digit palindrome in number base $b$. Now, every solution $\{x_1,x_2,\dots,x_i\}$ for some $(d,b)$ case can be expressed as $P_n(d,b+1)=x_j=P_m(d,b+3)$, so we can assign corresponding palindrome index $n$ to every $x_j$ and observe $n$s instead of decimal values $x_j$s.

I filled the excel sheets with differences $\{n_1,n_2-n_1,n_3-n_2,\dots,n_i-n_{i-1}\}$ of solution indexes $\{n_1,\dots,n_i\}$ for cases $(d,b)$ where different columns represent different bases $b$ in order, filled with solutions in order, where $d$ is fixed per excel sheet. Then within each column, color the same values with the same color.

Case $d=1$ sheet can be seen below:

enter image description here

Where we can pick every second column, and sort the data (number bases) in two cases:

enter image description here

Notice that the first case has fixed amount of solutions per base, and alternates between "red" and "green" types of solutions. These are easy to calculate/predict for the $n^{\text{th}}$ column. The second case is also easy to predict for the arbitrary column/base as all red values follow one polynomial equation, all greens the second, all blue solutions a third, and all yellows a fourth.

Now we see that we do not need to check every palindrome for $d=1$ cases, but can directly obtain desired solutions following these simple patterns.

Similarly, for $d=2$ we have established a pattern (more detailed than previous case) that can be split up in four cases by taking every fourth number base:

enter image description here

Again, same colored values can be described by same polynomials, which can be extracted from the data. As you can see, we have one finite-column pattern, two patterns similar to the previous case of $d$, and one very long pattern - which are all fully predictable at this point.

It seems that patterns for every next cases of $d$ are more detailed cases of the previous case. But I have no idea how to generalize this to all $d$, thus I'm trying to compute more data for $d=3$ and $d=4$ at the moment, where $d\ge5$ is simply unreachable because of the absurd number of palindromes and cases that would need to be computed.

Here is a part of $d=3$ data so far, visualized:

enter image description here

This case can be split in six separate pattern cases (by taking every sixth column), if I'm not mistaken so far as I've observed only one of the predicted six clearly, so far. I expect these will become fully clear after some more data is computed. But I do not see how to extend these so far to next $d$ cases.

Full patterns for $d\ge5$ are computationally out of reach by my current methods, and for $d=4$ will take time and patience at best, if I'm not underestimating them.


The mentioned $P_n(d,b)$ can be defined as:

$$1 + b^{2 d} + b^dn + b^{d - 1}\left\lfloor \frac{n}{b} \right\rfloor - \sum_{i=1}^{d - 1} \left((b^{i + 1} - b^{i - 1})\left\lfloor \frac{n}{b^{d - i + 1}} \right\rfloor \right), 0\le n\lt b^{d+1}-b^d$$

Problem becomes: find all $n$ for which there exists $m$ such that $P_n(d,b+1)=P_m(d,b+3)$.

I believe I could so far generate all solutions for $d\in\{1,2,3\}$ and chosen $b$s if I were to extract all the polynomials from the patterns - but this won't help solve more cases of $d$. What is needed, is a mathematical approach that could lead to a way of generating these patterns for some arbitrary $d$.

$\endgroup$
  • 1
    $\begingroup$ Generating palindromes in one base and checking if they are also palindromes in a second base should not be "extremely slow". How do you check whether an integer is a palindrome in some base? Anyway, since you want the number to have the same number of digits in both bases, you can save some work by only generating palindromes in the smaller base that have the right number of digits in the larger base. The larger $d$ is (for fixed $b$), the more work that saves. $\endgroup$ – Daniel Fischer Mar 29 '18 at 20:10
  • $\begingroup$ @DanielFischer It is fast indeed to check individual examples for being palindromic in selected bases, but as the $d,b$ grow, the total amount to be checked grows so much. If you could compute examples faster, that'll be very helpful. Essentially, I'm generating palindromes in one base and converting to another. I uploaded something to repl.it if you want to check out the python code. - for example, finding all examples for $(4,b>100)$ takes days. Similar code was posted to codereview.SE for optimization, but nothing significant was found. $\endgroup$ – Vepir Mar 29 '18 at 21:09
  • $\begingroup$ Working with numbers instead of string-like representations of numbers should be faster. But I'll need to write some code to check. $\endgroup$ – Daniel Fischer Mar 29 '18 at 21:23
  • 2
    $\begingroup$ This becomes a Diophantine problem over positive integers if we fix three consecutive bases and it seems to be hard. $\endgroup$ – Shalom Mar 29 '18 at 21:50
  • 1
    $\begingroup$ Here's Haskell, and Python 2. I've only implemented the creation of palindromes with an odd number of digits, but doing even numbers if wanted is no problem. Converting to a list/vector of digits to check for palindromicity is slow and unnecessary. Avoid that. It's fine to do that for the handful of multi-base palindromes one finds, but not for all candidates. $\endgroup$ – Daniel Fischer Mar 31 '18 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.