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$ . 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$ )

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 \le b \le 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 \le X \le 10^9~).

For test cases worth $80\%$ ~80\%~ of the points, you may assume $X \le 10^4$ ~X \le 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

Output for Sample Input

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$

2

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

Thanks!