Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 1
Most of the time, humans have fingers. This fact is the main reason that our numbering system is base-: the number really means . Notice that each digit in base- is in the range from .
Of course, there are other bases we can use: binary (base-), octal (base-) and hexadecimal (base-) are common bases that really cool people use when trying to impress others. In base-, the digits are in the range from , with each digit (when read from right to left) being the multiplier of the next larger power of .
So, for example (in base-) is:
- in base-
- in base- ()
- in base- ()
Noticing the above, you can see that 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 , , and are also palindromes.
Given a particular number (in base-), for what bases () is the representation of in base- a palindrome?
There will be one line, containing the integer ().
For test cases worth of the points, you may assume .
The output should consist of a sequence of increasing integers, each on its own line, indicating which bases have the property that written in that base is a palindrome. Note that we will only concern ourselves with bases which are less than , and that the first possible valid base is .
Output for Sample Input
Explanation of Output for Sample Input
The number was shown to be a palindrome in base- and in base- in the problem description. The other bases do not lead to palindromes. For example, in base-, is expressed as , and in base-, is expressed as .