ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 28 Sep 2022 06:47:52 +0200Partition n into perfect kth powershttps://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/Hello! I need help writing something that partitions $n$ into perfect $k$th powers (only perfect squares or only perfect cubes, etc.). I read the documentation on Partitions, but I couldn't figure out how to get partitions of $n$ restricted to perfect $k$th powers.
Please help! Thank you! Tue, 27 Sep 2022 12:14:06 +0200https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/Comment by tmonteil for <p>Hello! I need help writing something that partitions $n$ into perfect $k$th powers (only perfect squares or only perfect cubes, etc.). I read the documentation on Partitions, but I couldn't figure out how to get partitions of $n$ restricted to perfect $k$th powers. </p>
<p>Please help! Thank you! </p>
https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/?comment=64199#post-id-64199How large is `n` ? Could you please provide a tuple `(n,k)` that you would like to be solved ?Tue, 27 Sep 2022 12:27:07 +0200https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/?comment=64199#post-id-64199Answer by John Palmieri for <p>Hello! I need help writing something that partitions $n$ into perfect $k$th powers (only perfect squares or only perfect cubes, etc.). I read the documentation on Partitions, but I couldn't figure out how to get partitions of $n$ restricted to perfect $k$th powers. </p>
<p>Please help! Thank you! </p>
https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/?answer=64216#post-id-64216You can use Sage's `Partitions` constructor together with `parts_in`. First construct the `k`th powers which are at most `n`:
def powers_list(n,k):
"""
list of kth powers which are at most n
"""
# borrowed from Max Alekseyev's answer:
return [m**k for m in range(1, 1 + n.nth_root(k,truncate_mode=1)[0])]
Then you can do
Partitions(300, parts_in=powers_list(300, 3))
to get the partitions of 300 made up of perfect cubes.
In a few timing tests, this is about the same speed as the other answer. For example:
sage: %time len(list(Partitions(300, parts_in=powers_list(300, 2))))
CPU times: user 2.47 s, sys: 58 ms, total: 2.52 s
Wall time: 2.53 s
284316
sage: %time len(list(partitions_into_kth_powers(300, 2)))
CPU times: user 2.25 s, sys: 45.9 ms, total: 2.29 s
Wall time: 2.3 s
284316Wed, 28 Sep 2022 06:47:52 +0200https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/?answer=64216#post-id-64216Answer by Max Alekseyev for <p>Hello! I need help writing something that partitions $n$ into perfect $k$th powers (only perfect squares or only perfect cubes, etc.). I read the documentation on Partitions, but I couldn't figure out how to get partitions of $n$ restricted to perfect $k$th powers. </p>
<p>Please help! Thank you! </p>
https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/?answer=64204#post-id-64204I 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 (0..n//m**k):
yield from ((m,)*t + p for p in 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:
(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)
(3, 1, 1, 1)
Here `(3, 1, 1, 1)` means $30 = 3^3 + 1^3 + 1^3 + 1^3$.Tue, 27 Sep 2022 16:47:29 +0200https://ask.sagemath.org/question/64198/partition-n-into-perfect-kth-powers/?answer=64204#post-id-64204