Menu
Given an Integer x, I have to find a minimum baseb(b > 1) such that x base b is a palindrome.
Eg: 5 base 2 is a palindrome i.e. 5 in base 2 : 101 is a palindrome. How to solve it in a better way other than solving it brute-force?
353
Fair warning: this is not a complete answer, but some notes which may be useful. Hopefully given the unorthodox nature of the question and comments so far, no one will be too upset by this. :)
I marked the difference from previous as (+n) and on the end added some notes:
Some structural observations:
And finally, some less-developed ideas:
147
This has to be solved in a brute manner, but you can avoid making it a brute-force search by applying some logic to your approach, eliminating some of the candidates.
For example, you can avoid testing for bases which the number is divisible with, thus save a base conversion process as well as a palindrome test. The reason is simple: Representation in any base may not start with a zero, and this means that a number may not end with a zero in that representation as well, otherwise would not be a palindrome.
A number ending with a zero in a base x representation means that that number is divisible with x without a remainder.
This hint cannot be carried over to other digits, because rest could be anything that is representable in that base.
Unfortunately, I cannot come up with any other generalized logic to eliminate candidates. I can, however, come up with another one that will bring down the upper bound for bases to check for candidates, after which it can be surely said that the answer is simply base (x - 1) for that x.
Base (x - 1) for x produces 11 as the representation, which is a palindrome. As the bases decrease, either the digits in the representation become larger, or we get more digits.
2 would be 101
2 would be 22
Let's do the checking from reverse, start from top:
for (int base = x - 1; base >= 2; base--)
// is x represented palindromic at base (base)
Imagine this for a large x. The answer will be yes initially, then we will start having a no for a long while for sure. Why is that? Let me demonstrate:
/*
base representation
x - 1 11
x - 2 12
x - 3 13
x - 4 14
...
x - n 1n
...
x-x/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 last) will stay the same and the first one will increase slowly one by one.
It is similar for between x / 2 and x / 3, but the difference in between those two is way smaller (x / 6 compared to x / 2), as well as the first digit will start increasing two by two; therefore applying this logic to the rest becomes less and less significant.
Okay, for this reason, with the exception of numbers that are less than 6, if we happen to fail to find any base less than (x / 2) that yields a palindromic representation for a number x, we can safely give up and say that the answer is (x - 1).
All this text, explaining only two simple logics that can be implemented to prevent superfluous testing:
One last discussion: If the subject is representation in different bases, why get limited by the letters in any alphabet? Especially when we're working on computers? Just use integer arrays, each element representing a digit properly with numbers and not with any letter or anything else. Just like in strings, a terminating value can be used and that could be -1. Probably a lot easier for a computer, since it won't have to convert things back and forth into letters anyway.
And here's a source code that does what I've 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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
