Expressing positive integers as the sum of different charming numbers 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
  3i5j 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) -&gt; 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) -&gt; 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) -&gt; 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 &gt; 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.