Krdytkyu

In a practice academic interview of mine, we discussed question six, round one, of the United Kingdom Mathematics Trust's 2015 British Mathematical Olympiad. Which states:

A positive integer is called charming if it is equal to 2 or is of the form
3ⁱ5^j where i and j are non-negative integers. Prove that every positive integer can be written as a sum of different charming integers.

Having been able to successfully prove this, afterwards I then went on to implement, in Python, a program which can express any positive integer in terms of the sum of different charming numbers.

To do this I start by converting the integer into base 3 so that it is easier to find a charming number that is more than half the value of the original integer, but less than it. This value is then appended to a list, and the process is then repeated with the difference until left with either 1, 2, or 3. A list of charming numbers is then returned, which all sum to the original number.

I know this method works, simply as I used it somewhat in my proof.

I apologise in advance for the lack of comments.

def to_base_3(base_10: int) -> str:

    working_number = int(base_10)

    output = ''



    while True:

        next_digit = working_number % 3

        output = str(next_digit) + output

        working_number = working_number // 3



        if working_number == 0:

            return output





def to_base_10(base_3: str) -> int:

    output = 0



    for i, char in enumerate(base_3[::-1]):

        output += int(char) * (3 ** i)



    return output





def find_charming_components(number: int, charming_components: list = None) -> list:

    if charming_components is None:

        charming_components = 



    base_3_value = to_base_3(number)

    digit = base_3_value[0]

    component = 0



    if len(base_3_value) == 1:

        if digit != '0':

            charming_components.append(int(digit))



        return charming_components



    if digit == '1':

        component = to_base_10('1' + '0' * (len(base_3_value) - 1))

        # Find the largest power of three that is lower than the current value. I.e: 3**4

        charming_components.append(component)

        # Append this charming number to the list of components



    elif digit == '2':

        component = to_base_10('12' + '0' * (len(base_3_value) - 2))

        # Find the largest power of three times five that is lower than the current value. I.e: 3**4 * 5

        charming_components.append(component)

        # Append this charming number to the list of components



    number -= component

    # Repeat process with the difference

    return find_charming_components(number, charming_components)





print(find_charming_components(int(input('Number: '))))

I just feel like doing a full base 3 conversion and back again isn't the most efficient method of doing this, and would appreciate some help on generally improving the algorithm.

Your to_base_10(x) function may be easily rewritten as:

def to_base_10(base_3):

    return int(base_3, 3)

However, you are only using the function to convert base 3 numbers of the forms '1' followed by n zeros, and '12' followed by n zeros. These can be directly computed as:

• 
  to_base_10('1' + '0'*n) --> 3 ** n
  


• 
  to_base_10('12' + '0'*n) --> 5 * 3**n
  

The output of the to_base_3(x) function is only used to produce 2 values: len(base_3_value) and digit = base_3_value[0]. These can also be directly computed.

if number > 0:

    len_base_3_value = int(math.log(number, 3)) + 1

    digit = number // (3 ** (len_base_3_value - 1))

else:

    len_base_3_value = 1

    digit = 0

Note: digit is now an int (0, 1, or 2), not a str ('0', '1', or '2')

You recursively call and then return the value of find_charming_components(number, charming_components). Python does not do tail recursion optimization, so this should be replaced with a simple loop, instead of recursion.

def to_base_3(base_10: int) -> str:

Why str? I think it's simpler to use lists of digits.

base_10 is a misleading name. It's an integer. It's actually in base 2 in just about every CPU this code will ever be run on.

def to_base_10(base_3: str) -> int:

Similarly: this is from_base_3 to integer.

    output = 0



    for i, char in enumerate(base_3[::-1]):

        output += int(char) * (3 ** i)



    return output

It's simpler to convert from a list of digits to an integer in big-endian order:

def to_base_10(base_3: str) -> int:

    output = 0



    for char in base_3:

        output = 3 * output + int(char)



    return output

def find_charming_components(number: int, charming_components: list = None) -> list:

    if charming_components is None:

        charming_components = 

Frankly this is ugly. I understand that you want to use append for efficiency, but it would be cleaner with an inner recursive method.

    if digit == '1':

        component = to_base_10('1' + '0' * (len(base_3_value) - 1))

        # Find the largest power of three that is lower than the current value. I.e: 3**4

        charming_components.append(component)

        # Append this charming number to the list of components

I don't think I've ever seen comments after the code before, and it took me a while to work out what was going on.

If you have closed form expressions, why call to_base_10?

Also, surely it's "no greater than" rather than "lower than"?

    elif digit == '2':

Why not just else:?

        charming_components.append(component)

If the same code ends all the cases, it can be pulled out.

At this point I have

def find_charming_components(number: int) -> list:

    charming_components = 



    def helper(n):

        base_3_value = to_base_3(n)

        digit = base_3_value[0]



        if len(base_3_value) == 1:

            if digit != 0:

                charming_components.append(digit)

            return



        component = 0

        if digit == 1:

            # Find the largest power of three that is no greater than the current value. E.g: 3**4

            component = 3 ** (len(base_3_value) - 1)

        else:

            # Find the largest power of three times five that is no greater than the current value. E.g: 3**4 * 5

            component = 5 * 3 ** (len(base_3_value) - 2)



        charming_components.append(component)

        # Repeat process with the difference

        helper(n - component)



    helper(number)

    return charming_components

Now, helper is clearly tail-recursive, so is easy to replace with a loop:

def find_charming_components(number: int) -> list:

    charming_components = 



    while number > 0:

        base_3_value = to_base_3(number)

        digit = base_3_value[0]



        if len(base_3_value) == 1:

            if digit != 0:

                charming_components.append(digit)

            break



        component = 0

        if digit == 1:

            # Find the largest power of three that is lower than the current value. E.g: 3**4

            component = 3 ** (len(base_3_value) - 1)

        else:

            # Find the largest power of three times five that is lower than the current value. E.g: 3**4 * 5

            component = 5 * 3 ** (len(base_3_value) - 2)



        charming_components.append(component)

        # Repeat process with the difference

        number -= component



    return charming_components

At this point, the remaining issue is the cost of the conversion to base 3. Observing the sequence of numbers, we can easily generate them and then filter:

def find_charming_components(number: int) -> list:

    candidates = [1, 2, 3]

    current = 3

    while current < number:

        candidates.extend([current // 3 * 5, current * 3])

        current *= 3



    charming_components = 

    for candidate in reversed(candidates):

        if number >= candidate:

            charming_components.append(candidate)

            number -= candidate



    return charming_components