Задача 13: Сумма кубов

Условие задачи:

Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.

Выяснилось, что почти все чиcла, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов.

Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.

Входные данные:

Вводится натуральное число \(N <= 2*10^9\).

Выходные данные:

Требуется вывести не более восьми натуральных чисел, кубы которых в сумме дают \(N\). Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.

Решение:

n = int(input())

rez = [0 for _ in range(8)]
sqr = int(n ** (1/3)) + 2


def f(i, s, m):
    global rez
    if s == n:
        print(*rez[:i])
        exit(0)
    if i == 8:
        return
    for j in range(min(n - s, m), 0, -1):
        t = j * j * j
        if s + t * (8-i) < n:
            rez[i] = j
            return
        rez[i] = j
        f(i + 1, s + t, rez[i])
    rez[i] = 0


f(0, 0, sqr)
print("IMPOSSIBLE")

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик