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.