### 2013 Canadian Computing Competition, Stage 2

## Day 1, Problem 1: All your base are belong to palindromes

Most of the time, humans have 10 fingers. This fact is the main reason that
our numbering system is base-10: the number 257 really means
2 × 10^{2} + 5 × 10^{1} +
7 × 10^{0}. Notice that each digit in base-10 is in the
range from 0...9.

Of course, there are other bases we can use: binary (base-2), octal (base-8)
and hexadecimal (base-16) are common bases that really cool people use when
trying to impress others. In base-`b`, the digits are in the range
from 0...`b`-1, with each digit (when read from right to left) being
the multiplier of next larger power of `b`.

So, for example 9 (in base-10) is:

- 9 in base-16
- 11 in base-8 (1 × 8
^{1}+ 1 × 8^{0}= 9) - 1001 in base-2 (1 × 2
^{3}+ 0 × 2^{2}+ 0 × 2^{1}+ 1 × 2^{0}= 9)

Noticing the above, you can see that 9 is a palindrome in these 3 different
bases. A *palindrome* is a sequence which is the same even if it is
written in reverse order: English words such as dad

, mom

and
racecar

are palindromes, and numbers like 9, 11, 1001 are also
palindromes.

Given a particular number `X` (in base-10), what bases `b`
(2 ≤ `b` < `X`) cause the
representation of `X` in base-`b` to be a palindrome?.

### Input

There will be one line, containing the integer `X`
(2 ≤ `X` ≤ 10^{9}).

For test cases worth 80% of the points, you may assume
`X` ≤ 10000.

### Output

The output should consist of a sequence of increasing integers, each on its
own line, indicating which bases have the property that `X` written in
that base is a palindrome. Note that we will only concern ourselves with bases
which are less than `X`, and that the first possible valid base is
2.

### Sample Input

9

### Sample Output

2 8

### Explanation

The number 9 was shown to be a palindrome in base-2 and base-8 in the problem description. The other bases do not lead to palindromes: for example, in base-3, 9 is expressed as 100, and in base-5, 9 is expressed as 14.

All Submissions

Best Solutions

**Point Value:** 10 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** May 19, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

SourSpinachon May 20, 2013 - 2:51:01 pm UTC Correction