Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

I believe there is not build-in function, but we can easily design a generator for all partitions of $n$ into $k$th powers:

def partitions_into_kth_powers(n,k,m=+oo):
    if n < 2**k or m == 1:
        yield (1,)*n
        return
    for t in range(min(m,n.nth_root(k,truncate_mode=1)[0]),0,-1):
        for p in partitions_into_kth_powers(n-t**k,k,t):
            yield (t,)+p

For example, running

for p in partitions_into_kth_powers(30,3):
    print(p)

prints all partitions of 30 into cubes:

(3, 1, 1, 1)
(2, 2, 2, 1, 1, 1, 1, 1, 1)
(2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Here (3, 1, 1, 1) means $30 = 3^3 + 1^3 + 1^3 + 1^3$.

I believe there is not no a build-in function, but we can easily design a generator for all partitions of $n$ into $k$th powers:

def partitions_into_kth_powers(n,k,m=+oo):
    if n < 2**k or m == 1:
        yield (1,)*n
        return
    for t in range(min(m,n.nth_root(k,truncate_mode=1)[0]),0,-1):
        for p in partitions_into_kth_powers(n-t**k,k,t):
            yield (t,)+p

For example, running

for p in partitions_into_kth_powers(30,3):
    print(p)

prints all partitions of 30 into cubes:

(3, 1, 1, 1)
(2, 2, 2, 1, 1, 1, 1, 1, 1)
(2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Here (3, 1, 1, 1) means $30 = 3^3 + 1^3 + 1^3 + 1^3$.

I believe there is no a build-in function, but we can easily design a generator for all partitions of $n$ into $k$th powers:

def partitions_into_kth_powers(n,k,m=+oo):
    if n < 2**k or m == 1:
        yield (1,)*n
        return
else:
        for t in range(min(m,n.nth_root(k,truncate_mode=1)[0]),0,-1):
            yield from ((t,)+p for p in partitions_into_kth_powers(n-t**k,k,t):
            yield (t,)+p
partitions_into_kth_powers(n-t**k,k,t))

For example, running

for p in partitions_into_kth_powers(30,3):
    print(p)

prints all partitions of 30 into cubes:

(3, 1, 1, 1)
(2, 2, 2, 1, 1, 1, 1, 1, 1)
(2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Here (3, 1, 1, 1) means $30 = 3^3 + 1^3 + 1^3 + 1^3$.

I believe there is no a build-in function, but we can easily design a generator for all partitions of $n$ into $k$th powers:

def partitions_into_kth_powers(n,k,m=+oo):
    if n < 2**k or m == 1:
        yield (1,)*n
    else:
        m = min(m, n.nth_root(k,truncate_mode=1)[0])
        for t in range(min(m,n.nth_root(k,truncate_mode=1)[0]),0,-1):
(0..n//m**k):
            yield from ((t,)+p ((m,)*t + p for p in partitions_into_kth_powers(n-t**k,k,t))
partitions_into_kth_powers(n-t*m**k,k,m-1))

For example, running

for p in partitions_into_kth_powers(30,3):
    print(p)

prints all partitions of 30 into cubes:

(3, (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 2, 2, 1, 1, 1, 1, 1, 1)
(2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, (3, 1, 1, 1)

Here (3, 1, 1, 1) means $30 = 3^3 + 1^3 + 1^3 + 1^3$.