## CCO '13 P1 - All Your Base Belong to Palindromes

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### 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 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 dad, mom, and 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?

#### Input Specification

There will be one line, containing the integer ().

For test cases worth of the points, you may assume .

#### Output Specification

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 .

#### Sample Input

9

#### Output for Sample Input

2
8

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

• commented on Nov. 2, 2017, 8:09 a.m. edit 3

(fixed by Kirito)

• commented on Nov. 2, 2017, 12:56 p.m.

Fixed. Thanks for pointing that out!

• commented on March 15, 2015, 9:17 p.m.

How can I express something higher than base 62?

• commented on March 15, 2015, 9:53 p.m.

Instead of representing the digits with numbers and/or letters, you can use just a vector of numbers.

Base 62 :

• commented on March 15, 2015, 11:17 p.m.

Thanks!