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 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
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?
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~.
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~.
Output for Sample Input
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~.