3
\$\begingroup\$

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) -> 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.

\$\endgroup\$
2
\$\begingroup\$
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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.