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$.
2 | No.2 Revision |
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$.
3 | No.3 Revision |
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$.
4 | No.4 Revision |
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$.