Ask Your Question
0

Partition n into perfect kth powers

asked 2022-09-27 12:14:06 +0100

brennan gravatar image

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!

edit retag flag offensive close merge delete

Comments

How large is n ? Could you please provide a tuple (n,k) that you would like to be solved ?

tmonteil gravatar imagetmonteil ( 2022-09-27 12:27:07 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
0

answered 2022-09-28 06:47:52 +0100

You can use Sage's Partitions constructor together with parts_in. First construct the kth 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
284316
edit flag offensive delete link more
0

answered 2022-09-27 16:47:29 +0100

Max Alekseyev gravatar image

updated 2022-09-28 03:49:50 +0100

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 (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$.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-09-27 12:14:06 +0100

Seen: 124 times

Last updated: Sep 28 '22