Ask Your Question

Binary partition function

asked 2023-02-07 14:13:34 +0200

brennan gravatar image

Hello, I am trying to figure out how to return the number of partitions of n as powers of 2 (sometimes called the binary partition function $b(n)$). For example, $4 = 2^2 = 2^1+2^0+2^0 = 2^0+2^0+2^0+2^0$, then $b(4)=3$.

I just can't get anything to work. I would really appreciate some help. Thank you so much! This community is always so helpful!

If the code can be written so that it gives the number of partitions of $n$ as powers of $k$ that would be unbelievably helpful.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2023-02-07 15:55:49 +0200

Max Alekseyev gravatar image

updated 2023-02-07 16:22:23 +0200

This should do the job for given n and k:

def b(n, k=2):
    return Partitions(n,parts_in=[k**i for i in range(n.ndigits(k))]).cardinality()

Btw, you missed $4 = 2^1 + 2^1$ and so $b(4)=4$.

edit flag offensive delete link more


Thank you so much! And yes, I missed that, good catch!

Do you think it would be possible to modify this code slightly to return partitions of $n$ among the Fibonacci numbers?

I tried using:

def f(n): return partitions(n,parts_in=[fibonacci(n) for i in range(n.ndigits(k))]).cardinality()

But that didn't work. I tried some variations as well but I am getting the error that "Error, Integer Operations: <divisor> bust be nonzero"

Sorry if I am asking too much, I really appreciate your help!

brennan gravatar imagebrennan ( 2023-02-08 06:04:57 +0200 )edit

Using @Max Alekseyev remarks below:

def b(n):
    import itertools
    fibs = itertools.takewhile(lambda x: x<=n,fibonacci_sequence(2, n+1))
    return Partitions(n,parts_in=fibs).cardinality()

[`b(x) for x in range(4,21)]`
[4, 6, 8, 10, 14, 17, 22, 27, 33, 41, 49, 59, 71, 83, 99, 115, 134]


achrzesz gravatar imageachrzesz ( 2023-02-08 08:55:00 +0200 )edit

This is perfect, thank you so much! I cannot tell you how helpful this is! I have one more if that is ok. I am trying to find the aperiodic partition function, partitions of $n$ into relatively prime parts. OEIS A000837. I don't even know where to start here.

brennan gravatar imagebrennan ( 2023-02-08 13:53:05 +0200 )edit

Converting fibonacci_sequence(1, n+1) into a list is an overkill. More efficient is to use module itertools:

import itertools
fibs = itertools.takewhile(lambda x: x<=n, fibonacci_sequence(1, n+1))

Alternatively, one can compute the largest index of Fiboinacci number via logarithm of $n\sqrt{5}$ base the golden ratio.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-02-08 14:36:09 +0200 )edit

A naive attempt of obtaining some numbers from :

[len([x for x in Partitions(n) if gcd(x)==1]) for n in range(2,20)]

[1, 2, 3, 6, 7, 14, 17, 27, 34, 55, 63, 100, 119, 167, 209, 296, 347, 489]

For palindromes:

def pal(n):
    return Partitions(n,parts_in=[1]+srange(2,n+1,2)).cardinality()
achrzesz gravatar imageachrzesz ( 2023-02-08 17:28:13 +0200 )edit

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


Asked: 2023-02-07 14:13:34 +0200

Seen: 138 times

Last updated: Feb 07