16
1
Given a number n
, write a function that finds the smallest base b ≥ 2
such that n
is a palindrome in base b
. For example, an input of 28
should return the base 3
since the ternary representation of 28 is 1001. Although 93
is a palindrome in both base 2 and base 5, the output should be 2
since 2<5.
Input
A positive integer n < 2^31
.
Output
Return the smallest base b ≥ 2
such that the base b
representation of n
is a palindrome. Do not assume any leading zeros.
Samples (input => output):
11 => 10
32 => 7
59 => 4
111 => 6
Rules
The shortest code wins.
This is OEIS A016026.
– Engineer Toast – 7 years ago1I think base should be limited. – Snack – 11 years ago
No, I mean the base to check. For example, I can check up to base 10, or I can check up to base 36, which uses 0-9a-z. And I can even check up to base 127 which uses ASCII characters. You should limit base to check up. – Snack – 11 years ago
3@Snack: What's the problem with higher bases? Independently of the choice of symbols, a base 1000 number will either be a palindrome or not. – Dennis – 11 years ago
Oh, I got it. Sorry. – Snack – 11 years ago
Are you asking for a function, or a full program?, And does it have to take command-line input or can I hardcode it?, Is the output printed or returned? – Οurous – 11 years ago
@Ourous: A function. Hardcoding is fine. Output is returned. – ntomlin1996 – 11 years ago
3Interesting anecdote: n in base n-1 is always 11 for n >= 2 and thus a palindrome is always possible. – Cruncher – 11 years ago
1@Cruncher:
n
can be 1 and 2 is not a base 1 palindrome. However, every positiven
is a basen + 1
palindrome. – Dennis – 11 years agopossible duplicate of Determine if an integer is a palindrome in a given radix (base)
– Digital Trauma – 11 years ago1@Dennis How is 2 not a base 1 palindrome? It's 11. Or II, or 2 of whatever symbol you use. Actually all base 1 numbers are palindromes. And I said n >= 2, because I don't know what on earth base 0 would be. – Cruncher – 11 years ago
@DigitalTrauma definitely related. Shaky whether it's a dupe or not – Cruncher – 11 years ago
@Cruncher: I didn't consider 1 a valid base. OK, there's apparently a unary number system, but the question rules base 1 out. – Dennis – 11 years ago
@Dennis Everyone knows unary! You've been doing it with your fingers since you learned to count! Anyway, my comment was more of an aside. I was going to say n >= 3, but since it was mathematically true for n=2, I decided to strengthen it a bit. – Cruncher – 11 years ago
@Cruncher: Exactly! That's why I did not provide an upper bound for the base. – ntomlin1996 – 11 years ago