ZerocooL95's blog

Question about palindromic numbers in other bases .
By ZerocooL95, history, 8 years ago, In English

I was doing a problem on codechef and couldnt get to the solution . If anyone can help , it would be appreciated . Given a number N, write a program to compute the smallest base B such that N is palindromic when written in base B. 1<=N<=10**10. Link: https://www.codechef.com/problems/K2

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Suppose our palindrome has 3 or more digits, then B will be smaller than 1e5, so we can simply enumerate B and check if N is a palindrome.

When our palindrome has 2 digits, these 2 digits should be same, so there should be a x smaller than B, that x * B + x = N, x * (B + 1) = N. B + 1 should be a divisor of N. Then we can enumerate all divisors of N and update the answer.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, as an extension, what would be the solution for this similar problem from the Canadian national olympiad? Essentially, the base can go up to 109 and all bases where the starting number X (in base-10) are a palindrome should be outputted?

    → Reply