Smallest Good Base

Table of Contents

Problem Statement

Suppose we have given an integer n, for all the values of n base k are 1 when a good base k>=2. Suppose we have given a string format-number ‘n’. The problem statement asks to find out the smallest good base of n and to return it in string format.

Example

String n = “15”

Explanation: 15 when written in Base 2 is 1111.

String n = “20”

Explanation: 20 when written in Base 19 is 11.

Algorithm for smallest good base problem

1. Set y to n-1.
2. Add the n-1 into the List.
3. From the i=2 to i< 63,
  1. Find out the val = pow of (y, 1.0 / i).
  2. From j=0 to j > - 3 and val + j > 1.
    1. Set d = val + j.
    2. And check if n % d is equal to 0.
      1. Find out this polynomial 1 + d + d ^ 2 + d ^ 3 + ... + d ^ i for d and up the current value of I and store into the sum.
    3. Check if this polynomial’s sum is equal to the n.
      1. Then add the value of d to the list.
4. Repeat the third process until the loop finishes.
5. Get the last element of the list and return that value.

Explanation

Given a number n in String format. Every number n has a max value of base which is n-1. Since the value can change from 3 to 10^18, which can be accommodated in max 64 digits. The smallest base could be 2 and go up to 63. The maximum base which we can calculate is n-1, for any value of n, and the minimum is 2.

We need to decrease the base consequently to find the most extreme length portrayal of every one of the ones. For each no. of digits, we would attempt to find whether there exists a base that would give esteem equivalent. Given value = m, this problem is to find whole numbers d and n that satisfy,

m = 1 + d + d ^ 2 + d ^ 3 + … + d ^ i.

with ‘i’ is the value that can be changed every time whenever we traversed the array(with the goal that b will be minimized).

As per the equation, we always have answer as a pair Accordingly d1 = m-1. So we will sum up the possible values of answer we inserted into the list. The values (d1, …, dn) are in the list and we will fetch the last value. We need to find the polynomial of 1+b+b^2+b^3 + … + b^base.

We will follow up on a function, from which we are going to find the value of every possible number. The loop which we have taken is up to the 62 because the number can be formed up to 64 digits, but taking a 63 possible will result in an overflow. We will be continuing up this until we found the minimum value and also simultaneously we are going to add it to the list. So we just need to find the smallest base and fetch the last one.

Code

C++ code to find smallest good base

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

long getGetPolynomial(long, int);
string getMinGoodBase(string n)
{
    long x = stoi(n);
    vector<long> listt;
    listt.push_back(x-1);
    long y = x-1;
    for (int i = 2; i < 63; i++)
    {
        double val = pow(y, 1.0 / i);
        long value = (long) val;
        for (int j = 0; j > -3 && value + j > 1; j--)
        {
            long d = value + j;
            if (y % d == 0)
            {
                long poly = getGetPolynomial(d, i);

                if (poly == x)
                {
                    listt.push_back(d);
                }
            }
        }
    }
    long end = listt[listt.size() - 1];
    string out = to_string(end);
    return out;
}
long getGetPolynomial(long d, int n)
{
    long out = 1;
    long k = 1;
    for (int i = 0; i < n; i++)
    {
        k *= d;
        out += k;
    }
    return out;
}
int main()
{
    string num="15";
    cout<<getMinGoodBase(num);
}

Java code to find smallest good base

import java.util.ArrayList;
import java.util.List;

class GoodBase
{
    public static String getMinGoodBase(String n)
    {
        long x = Long.parseLong(n);
        List<Long> listt = new ArrayList<>();
        listt.add(x-1);
        long y = x-1;
        for (int i = 2; i < 63; i++)
        {
            double val = Math.pow(y, 1.0 / i);
            long value = (long) val;
            for (int j = 0; j > -3 && value + j > 1; j--)
            {
                long d = value + j;
                if (y % d == 0)
                {
                    long poly = getPolynomial(d, i);

                    if (poly == x)
                    {
                        listt.add(d);
                    }
                }
            }
        }
        long end = listt.get(listt.size() - 1);
        return end+"";
    }
    public static long getPolynomial(long d, int n)
    {
        long out = 1;
        long k = 1;
        for (int i = 0; i < n; i++)
        {
            k *= d;
            out += k;
        }
        return out;
    }
    public static void main(String args[])
    {
        String num="15";
        System.out.println(getMinGoodBase(num));
    }
}