This needs to be resolved roughly, but you can avoid brute force searches by applying some logic to your approach by excluding some of the candidates.
For example, you can avoid testing the databases, the number of which is divided, thus preserving the basic conversion process, as well as checking the palindrome. The reason is simple: a view in any database may not start from zero, which means that a number cannot end with zero in this view, otherwise it will not be a palindrome.
A number ending with zero in the base representation of x means that this number is divisible by x without a remainder.
This hint cannot be transferred to other numbers, because the rest can be anything that is presented in this database.
Unfortunately, I cannot come up with any other generalized logic for eliminating candidates. I can, however, come up with another one that will lead to an upper estimate of the bases for checking candidates, after which it is safe to say that the answer is simply the basic (x - 1) for this x.
The base (x - 1) for x produces 11 as a representation, which is a palindrome. As the bases decrease, either the numbers in the view become larger, or we get more numbers.
- The next smallest palindrome in base
2 will be 101 - The next smallest palindrome in any base greater than
2 will be 22
Make a check from the back, start at the top:
for (int base = x - 1; base >= 2; base--)
Imagine this for big x. First, the answer is yes, then we will probably start from scratch. Why is this? Let me demonstrate:
/* base representation x - 1 11 x - 2 12 x - 3 13 x - 4 14 ... x - n 1n ... xx/2 20 or 21 for x even or odd x / 2 20 or 21 for x even or odd
Until x / 2, the second digit (from the last) will remain unchanged, and the first will slowly increase one by one.
Similarly for x / 2 and x / 3, but the difference between the two methods is smaller (x / 6 compared to x / 2), and the first digit will begin to increase two by two; therefore, the application of this logic to the rest is becoming less and less significant.
Well, for this reason, with the exception of numbers less than 6 , if we fail to find any base less than (x / 2), which gives a palindrome representation for the number x, we can reasonably refuse and say that the answer is (x - 1 )
This entire text, explaining only two simple logics that can be implemented to prevent redundant testing:
- Do not check bases that are proper number divisors
- Reduce to (x - 1) if the checks exceed (x / 2) for numbers x greater than or equal to 6
Last discussion: if the subject is a representation in different bases, why be limited to letters in any alphabet? Especially when we work on computers? Just use whole arrays, each element representing the number correctly with numbers, and not with any letter or anything else. As with strings, you can use the final value, which can be -1 . Probably a lot easier for the computer, because in any case, he will not have to convert things back and forth.
And here is the source code that does what I explained above:
#include <stdio.h> #include <malloc.h> int ispalindrome(const int * string) { int length = 0; while (string[length] != -1) length++; for (int i = 0; i < length / 2; i++) { if (string[i] != string[length - 1 - i]) return 0; } return 1; } int * converttobase(int number, int base) { int length = 0; int temp = number; while (temp) { length++; temp /= base; } int * result = calloc(length + 1, sizeof * result); for (int i = length - 1; i >= 0; i--) { result[i] = number % base; number /= base; } result[length] = -1; return result; } int lowestpalindromebase(int number) { int limit = (number < 6) ? (number + 2) : (number / 2); // if number is more than or equal to 6, limit candidates with the half of it // because, reasons... for (int base = 2; base < limit; base++) { if (number % base) // number does have a remainder after division with base { int * converted = converttobase(number, base); if (ispalindrome(converted)) { free(converted); return base; } free(converted); } } return number - 1; } int main( ) { for (int i = 1; i < 60; i++) { printf("%2d is palindromic at base %d\n", i, lowestpalindromebase(i)); } return 0; }