Binary partition function

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 close merge delete

Sort by » oldest newest most voted

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

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!

( 2023-02-08 06:04:57 +0200 )edit
1

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]


compare https://oeis.org/A003107

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

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

( 2023-02-08 14:36:09 +0200 )edit

A naive attempt of obtaining some numbers from https://oeis.org/A000837 :

[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()

( 2023-02-08 17:28:13 +0200 )edit