package Others;
import java.util.InputMismatchException;
import java.util.Scanner;
/**
* Class for finding the lowest base in which a given integer is a palindrome. Includes auxiliary
* methods for converting between bases and reversing strings.
*
* <p>NOTE: There is potential for error, see note at line 63.
*
* @author RollandMichael
* @version 2017.09.28
*/
public class LowestBasePalindrome {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = 0;
while (true) {
try {
System.out.print("Enter number: ");
n = in.nextInt();
break;
} catch (InputMismatchException e) {
System.out.println("Invalid input!");
in.next();
}
}
System.out.println(n + " is a palindrome in base " + lowestBasePalindrome(n));
System.out.println(base2base(Integer.toString(n), 10, lowestBasePalindrome(n)));
in.close();
}
/**
* Given a number in base 10, returns the lowest base in which the number is represented by a
* palindrome (read the same left-to-right and right-to-left).
*
* @param num A number in base 10.
* @return The lowest base in which num is a palindrome.
*/
public static int lowestBasePalindrome(int num) {
int base, num2 = num;
int digit;
char digitC;
boolean foundBase = false;
String newNum = "";
String digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
while (!foundBase) {
// Try from bases 2 to num-1
for (base = 2; base < num2; base++) {
newNum = "";
while (num > 0) {
// Obtain the first digit of n in the current base,
// which is equivalent to the integer remainder of (n/base).
// The next digit is obtained by dividing n by the base and
// continuing the process of getting the remainder. This is done
// until n is <=0 and the number in the new base is obtained.
digit = (num % base);
num /= base;
// If the digit isn't in the set of [0-9][A-Z] (beyond base 36), its character
// form is just its value in ASCII.
// NOTE: This may cause problems, as the capital letters are ASCII values
// 65-90. It may cause false positives when one digit is, for instance 10 and assigned
// 'A' from the character array and the other is 65 and also assigned 'A'.
// Regardless, the character is added to the representation of n
// in the current base.
if (digit >= digits.length()) {
digitC = (char) (digit);
newNum += digitC;
continue;
}
newNum += digits.charAt(digit);
}
// Num is assigned back its original value for the next iteration.
num = num2;
// Auxiliary method reverses the number.
String reverse = reverse(newNum);
// If the number is read the same as its reverse, then it is a palindrome.
// The current base is returned.
if (reverse.equals(newNum)) {
foundBase = true;
return base;
}
}
}
// If all else fails, n is always a palindrome in base n-1. ("11")
return num - 1;
}
private static String reverse(String str) {
String reverse = "";
for (int i = str.length() - 1; i >= 0; i--) {
reverse += str.charAt(i);
}
return reverse;
}
private static String base2base(String n, int b1, int b2) {
// Declare variables: decimal value of n,
// character of base b1, character of base b2,
// and the string that will be returned.
int decimalValue = 0, charB2;
char charB1;
String output = "";
// Go through every character of n
for (int i = 0; i < n.length(); i++) {
// store the character in charB1
charB1 = n.charAt(i);
// if it is a non-number, convert it to a decimal value >9 and store it in charB2
if (charB1 >= 'A' && charB1 <= 'Z') charB2 = 10 + (charB1 - 'A');
// Else, store the integer value in charB2
else charB2 = charB1 - '0';
// Convert the digit to decimal and add it to the
// decimalValue of n
decimalValue = decimalValue * b1 + charB2;
}
// Converting the decimal value to base b2:
// A number is converted from decimal to another base
// by continuously dividing by the base and recording
// the remainder until the quotient is zero. The number in the
// new base is the remainders, with the last remainder
// being the left-most digit.
// While the quotient is NOT zero:
while (decimalValue != 0) {
// If the remainder is a digit < 10, simply add it to
// the left side of the new number.
if (decimalValue % b2 < 10) output = Integer.toString(decimalValue % b2) + output;
// If the remainder is >= 10, add a character with the
// corresponding value to the new number. (A = 10, B = 11, C = 12, ...)
else output = (char) ((decimalValue % b2) + 55) + output;
// Divide by the new base again
decimalValue /= b2;
}
return output;
}
}