Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 1
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 \times 10^2 + 5 \times 10^1 + 7 \times 10^0~. Notice that each digit in base-~10~ is in the range from 
~0 \dots 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 \dots b-1~, with each digit (when read from right to left) being the multiplier of the next larger power of ~b~.
So, for example 
~9~ (in base-~10~) is:
- ~9~ in base-~16~
~11~ in base-~8~ (
~1 \times 8^1 + 1 \times 8^0 = 9~)
~1001~ in base-~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~ 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~, ~11~, and ~1001~ are also palindromes.
Given a particular number 
~X~ (in base-~10~), for what bases ~b~ (
~2 \le b \le X~) is the representation of ~X~ in base-~b~ a palindrome?
Input Specification
There will be one line, containing the integer ~X~ (
~2 \le X \le 10^9~).
For test cases worth 
~80\%~ of the points, you may assume 
~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~ 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
Output for Sample Input
2
8
Explanation of Output for Sample Input
The number ~9~ was shown to be a palindrome in base-~2~ and in 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~.
Comments
How can I express something higher than base 62?
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](https://static.dmoj.ca/mathoid/c5705ca817fd408def3b3acd740dbc61d7456d68/svg)
![[1,61,16] = 1 \times 62^2 + 61 \times 62^1 + 16 \times 62^0](https://static.dmoj.ca/static/blank.b44917055649.gif)
Thanks!