Binary partition function

edit

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!

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

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.

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.

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