An ongoing exploration into the binary function (and possibly some generalisations)

The goal post

The binary partition function is denoted as and is the number of ways to split into a sum of powers of two where order of summands does not matter. We want to find modulo some prime where .

Aimless Wandering

Observations:

1. If is odd, then .
2. is the -th prefix sum of the sequence
3. From (2) and (1), if we take the prefix sum of the sequence, we now get every even (or odd) term.
4. or something like that.

At this point, I’m highly suspicious about (4) because if we take the prefix sum of the prefix sum, we get a sequence which behaves almost like (4).

These are the terms and their respective prefix sums. We denote then In general, we refer to the sequence obtained by taking prefix sums times as . What I mean above, is notice that in , we have . Which is not exactly (4), but it has the same flavor as (4).

So maybe, this pattern continues?

Indeed it does! $11 = 4 + (3 + 4), 24 = 11 + (3 + 1), 47 = 24 + (3 + 11), 84 = 47 + (3 + 4), … $ Okay, but this seems completely random and out of this world and also, it doesn’t give us any information on our original sequence.

If we study, the relation between sequence, we can see that between and we have that there is a one to one correspondence between even terms of the former and terms of the latter. The relation holds for and except all the terms are doubled. This seems to fail for and , but if we wish hard enough, we find .

Writing a program to figure out this linear relation…

These are the coefficients of the linear relations. Damn, they are the binomial coefficients. We’re still missing half the terms if we want to work backwards. But miracuously they also follow some linear relation with binomial coefficients.

Maybe it isn’t that miraculous? There is definitely a way to proceed via generating functions. I retire to sleep for now. Proof coming soon TM