CCO '13 P1 - All Your Base Belong to Palindromes

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 1G

Problem type

Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 1

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

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

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

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

Noticing the above, you can see that $9$ $9$ is a palindrome in these three 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$ $9$ , $11$ $11$ , and $1001$ $1001$ are also palindromes.

Given a particular number $X$ $X$ (in base- $10$ $10$ ), for what bases $b$ $b$ ( $2 \le b \le X$ $2 \leq b \leq X$ ) is the representation of $X$ $X$ in base- $b$ $b$ a palindrome?

Input Specification

There will be one line, containing the integer $X$ $X$ ( $2 \le X \le 10^9$ $2 \leq X \leq 10^{9}$ ).

For test cases worth $80\%$ $80 %$ of the points, you may assume $X \le 10^4$ $X \leq 10^{4}$ .

Output Specification

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

Sample Input

Copy

Output for Sample Input

Copy

2
8

Explanation of Output for Sample Input

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

Comments

1

Walt28 commented on March 16, 2015, 1:17 a.m.

How can I express something higher than base 62?

8

fifiman commented on March 16, 2015, 1:53 a.m.

Instead of representing the digits with numbers and/or letters, you can use just a vector of numbers.

Base 62 : $[1,61,16] = 1 \times 62^2 + 61 \times 62^1 + 16 \times 62^0$ $[1, 61, 16] = 1 \times 62^{2} + 61 \times 62^{1} + 16 \times 62^{0}$

2

Walt28 commented on March 16, 2015, 3:17 a.m.

Thanks!