Base Jumping

Computer Science Level 4

Consider a positive integer $N$ written in base $b$ . A sequence is generated from this number by finding the largest digit $d$ in the expansion of $N$ and writing $N$ in base $d+1,$ repeating until the base the number is written in can be decreased no further. For example, the sequence generated by $346_{10}$ in base $16$ has length $6$ : $15A_{16} = 295_{11} = 346_{10} = 1003_7 = 11122_4 = 110211_3$ . Note that the next term in the sequence would be in base $3$ again, which is invalid since the base does not decrease.

There exists a single $N<10000$ and $b<100$ that generates a sequence with maximal length. Find $N+b.$

The answer is 7654.

2 solutions

Jeremy Rixon
Jan 10, 2020

Brute force python:

def max_digit(n, b):
    m = 0
    while n > 0:
        d = n % b
        if d == b-1:
            return d
        if d > m:
            m = d
        n //= b
    return m


def sequence_len(n, b):
    l = 1
    current_base = b
    next_base = max_digit(n, current_base) + 1
    while next_base < current_base and next_base > 1:
        l += 1
        current_base = next_base
        next_base = max_digit(n, current_base) + 1
    return l


best_len = 0
best_n = 0
best_b = 0

for n in range(2, 10000):
    for b in range(2, 100):
        l = sequence_len(n, b)
        if l >= best_len:
            best_len = l
            best_n = n
            best_b = b

print("Best length is ", best_len)
print("N for best length is ", best_n)
print("b for best length is ", best_b)
print("N+b for best length is ", best_n + best_b)

Piotr Idzik
May 15, 2020

Below you will find my C++ code. I used dynamic programming.

#include <iostream>
#include <list>
#include <map>
#include <algorithm>
#include <chrono>
template<typename InputValueType, typename DigitValueType>
std::list<DigitValueType> toDigitList(const InputValueType& inVal, const DigitValueType& inBase)
{
    std::list<DigitValueType> res;
    if(inVal == 0)
    {
        res.push_back(0);
    }
    else
    {
        auto curVal = inVal;
        while(curVal > 0)
        {
            const auto curDigit = curVal%inBase;
            curVal /= inBase;
            res.push_back(curDigit);
        }
    }
    return res;
}

template<typename OutputValueType, typename DigitValueType>
OutputValueType toNumber(const std::list<DigitValueType>& inDigitList, const DigitValueType& inBase)
{
    OutputValueType res = 0;
    OutputValueType curMultip = 1;
    for(const auto& curDigit : inDigitList)
    {
        res += curDigit*curMultip;
        curMultip *= inBase;
    }
    return res;
}

template<template <typename...> class MapType, typename ValueType, typename DigitValueType>
class BaseJump
{
    private:
        MapType<ValueType, MapType<DigitValueType, ValueType> > valueData;
    public:
        BaseJump() :
            valueData()
        {}
        ValueType getLength(const ValueType& inVal, const DigitValueType& inBase)
        {
            ValueType lengthVal = 1;
            if(!this->isStored(inVal, inBase, lengthVal))
            {
                const auto curDigitList = toDigitList(inVal, inBase);
                const auto maxDigit = *std::max_element(curDigitList.begin(), curDigitList.end());
                if(maxDigit+1 < inBase)
                {
                    lengthVal += this->getLength(inVal, maxDigit+1);
                }
                this->addValue(inVal, inBase, lengthVal);
            }
            return lengthVal;
        }
    private:
        bool isStored(const ValueType& inVal, const DigitValueType& inBase, ValueType &lengthVal)
        {
            bool isStoredRes = false;
            const auto inValIter = this->valueData.find(inVal);
            if(inValIter != this->valueData.end())
            {
                const auto inBaseIter = inValIter->second.find(inBase);
                if(inBaseIter != inValIter->second.end())
                {
                    isStoredRes = true;
                    lengthVal = inBaseIter->second;
                }
            }
            return isStoredRes;
        }
        void addValue(const ValueType& inVal, const DigitValueType& inBase, const ValueType& lengthVal)
        {
            this->valueData[inVal][inBase] = lengthVal;
        }
};

template<template <typename...> class MapType, typename ValueType, typename DigitValueType>
ValueType getSolution(const ValueType& numberLimit, const DigitValueType& baseLimit)
{
    ValueType curMax = 0;
    ValueType optN = 0;
    DigitValueType optB = 0;
    BaseJump<MapType, ValueType, DigitValueType> baseJump;
    for(ValueType curN = 1; curN < numberLimit; ++curN)
    {
        for(unsigned char curB = 2; curB < baseLimit; ++curB)
        {
            const auto curVal = baseJump.getLength(curN, curB);
            if(curVal > curMax)
            {
                curMax = curVal;
                optN = curN;
                optB = curB;
            }
        }
    }
    return optN+optB;
}
int main()
{
    const auto startTime = std::chrono::steady_clock::now();
    const auto solVal = getSolution<std::unordered_map, unsigned, unsigned char>(10000, 100);
    const auto endTime = std::chrono::steady_clock::now();
    std::chrono::duration<double> runTime = endTime-startTime;
    std::cout<<"Result: "<<solVal<<std::endl;
    std::cout<<"runtime: "<<runTime.count()<<" [s]\n";
    return 0;
}

Base Jumping

The answer is 7654.

2 solutions

0 pending reports