"The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number". Or, in Russian: "The decimal number 585 in binary numeral system looks as 1001001001. It is a palindrome in both numeration systems. Find n-y a similar palindrome".

But existence is considerable faster, with essentially other computing complexity, algorithm haunted me, and eventually I returned to its analysis.

Eventually, the algorithm was not such and difficult, but, in my opinion, very beautiful.

The original explanation and implementation use a prefix tree, but in my opinion, deeper understanding of mathematics of algorithm allows to manage simpler and fast structures. I think that it is the best of all to sort algorithm on an example.

We will look for binary palindromes among decimal

**palindromes 8 wide**. Initial palindromes

**exactly 9000**: from 10000001 to 99999999.

Now we will take 2 sets of numbers:

- And
**[90]**= {**10000001, 11000011, 12000021**__...,__**98000089, 99000099**__}__ **B[100]**= {__00000000____, 00011000, 00022000____...,____00988900, 00999900____}__

If to describe these sets formally, then the set And is a subset of decimal

**palindromes 8 wide**which have average

**4**discharges — zero, and the set of B consists from

**0**, sets of the decimal

**palindromes 2 wide**increased on

**and sets of the decimal**

^{103}**palindromes 4 wide**increased on

**.**

^{102}And if it is informal, then a set And — all this possible "edges", and a set of B — all possible "cores" of decimal

**palindromes 8 wide**. It is obvious that the set of all decimal

**palindromes 8 wide**is a set of all paired sums of elements of sets of A and B.

```
for each (a in A) {
for each (b in B) {
palindrome = a + b;
}
}
```

Further, for brevity I will use "a" instead of "A set member", and "b" instead of "B set member".

Now we will transfer elements of both sets to binary numeral system:

A

10000001 100110001001011010000001

11000011 101001111101100011001011

12000021 101101110001101100010101

…

98000089 101110101110101110011011001

99000099 101111001101001111100100011

B

00000000000000

00011000 10101011111000

00022000 101010111110000

…

00988900 11110001011011100100

00999900 11110100000111011100

I selected

**6**upper and lower discharges at all a, and

**6**lower discharges at all b. Width

**6**is selected not accidentally - it is the maximum degree

**2**which is not exceeding width of "edges" of A =

**.**

^{102}Now we will take each a, and we will look that the general at all palindromes formed from it by addition of b. And the general at them, the fact that all of them are in an interval between an and the element A following it.

For example, for a = 10000001, all decimal palindromes formed from it { 10000001, 10011001, 10022001..., 10988901, 10999901 } are in an interval [10000001, 11000011).

It means that all decimal palindromes formed from a = 10000001 can begin only with the following

**6**binary figures:

100110 — the first binary figures of a = 10000001

100111

101000

101001 — the first binary figures of a = 11000011

Therefore, to be binary palindromes, all these decimal palindromes can come to an end only on the return shift of initial binary figures:

100110-> 011001

100111-> 111001

101000-> 000101

101001-> 100101

And considering what and = 10000001 comes to an end on binary figures 000001, from all possible b we are interested only those which come to an end on binary figures:

011001 — 000001 = 011000

111001 — 000001 = 111000

000101 — 000001 = 000100

100101 — 000001 = 100100

Only for such b it is necessary to check whether b a binary palindrome is 10000001 +.

Using this approach, the algorithm for finding of palindromes in the bases

_{of BASE0, BASE1}

_{}in the range of [1, N] can be described as follows:

For each width of W from [1, quantity of discharges N in_{BASE0}]

To generate sets of A and B, using_{BASE0}. Width of "edges"_{of A WA}=_{O(W/4), WA}≥_{WB}

To transfer the A and B elements to_{BASE1}

To sort elements B on baskets on the last digits in_{BASE1}

For each a from a set of A

For every X of a set of possible initial digits of a + b

For each b which is coming to an end on (X — final digits of a)

To check whether a + is b a palindrome in_{BASE1}

Unfortunately, I already forgot to prove strictly computing complexity of algorithms, I will give some reasons:

- Sets of A and B contain
of elements.^{O(N1/4)} - For each an on average there is no more
of options X._{BASE0}

(We initially select width of the initial digits interesting us in_{BASE1}so that the number which turned out from them was no more, and max(A) is more than min (A) in_{BASE0WA}^{}of times.)_{BASE0} - For every X
of different b is on average checked no more, than._{BASE1}

(X it is distributed evenly and almost does not correlate with final digits of an in. Each basket with b means it is selected evenly, and such baskets no more than_{BASE1}of everything, than b.)_{it is BASE1 times less} - Check on a palindrome all the same occupies
**O(log(N))**.

Generally, I assume that computing complexity of algorithm

**.**

^{of O(N1/4}* log(N) *_{BASE0}*_{BASE1})The first implementation of this algorithm was quite predictably couple orders faster, and having spent a little more time for optimization I finished computation time about

**a little more than 0.01**seconds,

**is more than 1000 times faster**than predydyshchy algorithm. This result at last satisfied me, but quite naturally there was a desire to check it on numbers, big, than

**. By this time I already found the sequence interesting me in "The encyclopedia of integer sequences". In the list of double palindromes there were**

^{260}**122**members, the biggest of whom consisted of

**131**bits. It was impressively, but also indirectly indicated that nobody thought up algorithm of logarithmic complexity yet.

The challenge was serious — it was possible not to doubt that the people who received such result put many forces in development of algorithm and besides were for certain ready to spend days and weeks of machine time for the subsequent search. Therefore, I decided to evaluate at least approximately, time which is necessary for my algorithm on repetition:

^{2131 /}

^{260 =}

^{271}**<**

^{271 * 1/4 218}**=**

^{}**262144**

Considering

**0.01**seconds necessary for a limit in

**, left that my algorithm had to cope with this task approximately in**

^{260}**1**hour! I felt some dirty trick, but the challenge was already accepted.

Be continued.

This article is a translation of the original post at habrahabr.ru/post/272659/

If you have any questions regarding the material covered in the article above, please, contact the original author of the post.

If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.

Shared knowledge makes the world better.

Best wishes.