CCO '13 P1 - All Your Base Belong to Palindromes

View as PDF

Submit solution

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 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


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.


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

    How can I express something higher than base 62?

    • 7
      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.