Кубоидные слои

Задача 126
Минимальное количество кубов, чтобы покрыть каждую видимую грань на кубоиде размером 3 x 2 x 1, составляет двадцать два.


Если затем мы добавим второй слой к этому телу, для покрытия каждой видимой грани потребуется сорок шесть кубов, для третьего слоя потребуется семьдесят восемь кубов, а для четвертого слоя потребуется сто восемнадцать кубов для покрытия каждой видимой грани. ,

Однако первый слой на кубоиде размером 5 x 1 x 1 также требует двадцать два куба; аналогично первый слой на кубоидах размером 5 x 3 x 1, 7 x 2 x 1 и 11 x 1 x 1 содержит сорок шесть кубов.

Мы определим C ( n ) для представления числа кубоидов, которые содержат n кубов в одном из своих слоев. Итак, C (22) = 2, C (46) = 4, C (78) = 5 и C (118) = 8.

Оказывается, что 154 является наименьшим значением n, для которого C ( n ) = 10.

Найдите наименьшее значение n, для которого C ( n ) = 1000.
from time import time; t=time()


# 4(k-1)(a+b+c)+2(ab+bc+ca)+8(k-1)(k-2)/2

N = 1000
M = 20000

cache = [0] * M
for a in range(1, M):
    for b in range(1, a+1):
        ab = a * b
        if ab * 2 >= M: break
        a_b = a + b
        for c in range(1, b+1):
            s =(a_b * c + ab) * 2
            if s >= M: break
            cache[s] += 1
            ss = 4 * (a_b + c)
            for k in range(0, M, 8):
                s += ss + k
                if s >= M: break
                cache[s] += 1

for i, v in enumerate(cache):
    if v == N:
        break

print(i, time()-t)
