"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".

The author began the fascinating story with the most trivial solution with search and check of all

**numbers from 1 to N**and computing complexity

**of O(N * log(N))**where

**N**— the maximum checked number. The multiplier

**of log (N)**is necessary since it for each checked number is made several actions depending on quantity of its discharges.

The first working optimization, namely replacement of search of all numbers by search only of decimal palindromes, cardinally improved computing complexity to

**since the quantity of the checked numbers decreased to**

^{O(N1/2}* log(N))**. And despite some losses because of complication of algorithm, on enough big**

^{O(N1/2)}**N**runtime predictably improved on orders.

Having made some more small optimization, the author improved runtime by

**3**times, and on this quite good result decided to stop.

Without having read up up to the end yet, I thought that I at the same computing complexity

**for certain will work much quicker not with lines, and directly with numbers. That is to generate sequence of palindromes, using not operations with lines, but arithmetic actions.**

^{of O(N1/2}* log(N))And it appeared absolutely not difficult, the sequence of numbers palindromes of identical length reminds an arithmetic progression with a permanent step which it is necessary to adjust each

**BASE, BASE2, BASE3**

^{}**,… elements.**

^{}For example, for decimal

**palindromes 5 wide**the main step will be ravn

**+100**:

` 10001, 10101, 10201, 10301, 10401, 10501, 10601, 10701, 10801, 10901, 11001 `

The last sequence unit is not a palindrome and demands correction

**+10**, to

`11011`

` 11011, 11111, 11211, 11311, 11411, 11511, 11611, 11711, 11811, 11911, 12011 `

The last element a sequence unit demands correction

**+10**, again to

`12021`

So we reach that

**the 99th and 100th**elements:

`19991, 20091`

Necessary correction for

**the 100th**

**element +10-99**=

**-89**, as a result, we receive

**also we continue until we reach to**

`20002`

**.**

`99999`

As arithmetic generation of palindromes became very fast (on average only several commands of the assembler), I decided that generation of palindromes in one basis + check in another will work for a palindrome more slowly, than parallel generation of palindromes in both bases and comparison.

As a result, the following code on C ++ turned out:

Auxiliary structure with necessary degrees of the basis:

```
#undef POWER
#define POWER(exp) m_powers[exp]
template<typename IntT>
struct BaseData
{
static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;
BaseData(
size_t base,
IntT maxValue)
: m_base(base)
{
POWER(0) = IntT(1);
for (size_t i = 1; i < MAX_WIDTH; ++i) {
POWER(i) = POWER(i - 1) * IntT(base);
if (POWER(i) >= maxValue) {
m_maxWidth = i - 1;
break;
}
}
}
size_t m_base;
size_t m_maxWidth;
IntT m_powers[MAX_WIDTH];
};
```

Iterator of palindromes:

```
template<typename IntT>
class Iterator
{
static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;
private:
struct IncrementData
{
size_t m_counter; // current counter value
size_t m_counterLimit; // number of iterations, usually B, but B - 1 for last increment
IntT m_increment; // increment value
};
public:
inline Iterator(
const size_t base,
const IntT * powers)
: m_base(base)
, m_powers(powers)
{
m_value = POWER(0);
SetWidth(1);
}
inline void operator ++()
{
// always increment by basic
m_value += m_basicIncrement;
size_t i = 0;
do {
if (--m_counters[i].m_counter)
return;
// reset counter
m_counters[i].m_counter = m_counters[i].m_counterLimit;
// correct value on digit overflow
m_value += m_counters[i].m_increment;
} while (++i < m_countersSize);
// prepare to next width
SetWidth(m_width + 1);
}
inline const IntT &operator *() const
{
return m_value;
}
private:
void SetWidth(
size_t width)
{
m_width = width;
m_countersSize = (m_width + 1) / 2;
m_basicIncrement = POWER(m_countersSize - 1);
size_t i;
for (i = 0; i < m_countersSize - 1; ++i) {
m_counters[i].m_counter = m_counters[i].m_counterLimit = m_base;
m_counters[i].m_increment = POWER(m_countersSize - i - 2) - POWER(m_countersSize - i - 2) * m_base * m_base;
}
m_counters[i].m_counter = m_counters[i].m_counterLimit = m_base - 1;
m_counters[i].m_increment = POWER(0) - POWER(1);
if (m_width &1)
m_counters[0].m_increment += POWER(m_countersSize);
else
m_basicIncrement += POWER(m_countersSize);
}
IntT m_value; // current value
IntT m_basicIncrement; // basic increment (100... for odd width, 1100... for even width
size_t m_countersSize; // just greater half of width: (width + 1) / 2
IncrementData m_counters[MAX_WIDTH];
size_t m_width; // current width = number of digits
size_t m_base;
const IntT * m_powers;
};
```

And, at last main:

```
int _tmain(int argc, _TCHAR* argv[])
{
int64 limit = 18279440804497281;
BaseData<int64> base0(2, limit);
BaseData<int64> base1(10, limit);
Iterator<int64> it0(base0.m_base, base0.m_powers);
Iterator<int64> it1(base1.m_base, base1.m_powers);
while (*it0 <= limit) {
if (*it0 < *it1)
++it0;
else if (*it0 > *it1)
++it1;
else {
std::cout << *it0 << std::endl;
++it0;
++it1;
}
}
return 0;
}
```

**The 56th**palindrome equal

**18279440804497281**was received in

**1.85**seconds that

**is about 150 times faster**than the previous result (assuming that the grey_wolfs computer had the computational capability similar to my Intel Core i7-3770 CPU @ 3.40GHz). Certainly, the noticeable part of my benefit was called by transition from PHP for C ++, but all the same I with satisfaction rubbed hands: the algorithm already touched

**nearly 300 000 000**palindromes per second, and I in a stock had two more trumps: to generate only odd decimal palindromes (

**-20-25**%) and to use a multithreading (

**-70-85**% at 8 flows) …

And here I saw the comment which just "killed" me:

@hellman

Not so long ago on one of contests of codechef there was the same problem. Only bases of systems of calculation any from 2 to 16, it was also necessary the first 1000 palindromes smaller 2^60. Time limit — 8 sec. (the truth on an input can be 5 tests). Editorial is in the same place.

My algorithm found all palindromes to

**in**

^{260}**15**seconds, i.e. at worst would not keep within time limit even using a multithreading. And in Editorial there was also a humiliating comment "why does the time limit for this question is so high 8 sec I have not seen such high limit in any questions...?".

The satisfaction was quickly replaced by disappointment: my implementation of search

*** log(N))**though was close to computing complexity

**with the minimum theoretical limit, but it all the same there was insufficiently. I tried to understand the theoretical solution described in Editorial, even looked at their code, but from the first understood only that they managed to solve a problem with computing complexity about**

^{of O(N1/2}**.**

^{O(N1/4}* log(N))At this moment I stopped work on a problem, but it did not go at me out of the mind. And in several days I returned to it again.

Be continued.

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

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.