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

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


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