PE 890 (Spoilers)

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

The goal post

The binary partition function is denoted as $p(n)$ and is the number of ways to split $n$ into a sum of powers of two where order of summands does not matter. We want to find $p(a ^ b)$ modulo some prime where $b \approx 1000$.

Aimless Wandering


  1. If $n$ is odd, then $p(n) = p(n-1)$.
  2. $p(n)$ is the $\lfloor \frac{n}{2} \rfloor$-th prefix sum of the sequence $p(0), p(1), p(2), ...$
  3. From (2) and (1), if we take the prefix sum of the sequence, we now get every even (or odd) term.
  4. $p(n+2) = p(n) + p(\lfloor \frac{n}{2} \rfloor)$ 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).

$p_0: 1\text{ }1\text{ }2\text{ }2\text{ }4\text{ }4\text{ }6\text{ }6\text{ }10\text{ }10\text{ }14\text{ }14\text{ }20\text{ }20\text{ }26\text{ }26\text{ }36\text{ }36\text{ }46\text{ }46\text{ }60\text{ }$

$p_1: 1\text{ }2\text{ }4\text{ }6\text{ }10\text{ }14\text{ }20\text{ }26\text{ }36\text{ }46\text{ }60\text{ }74\text{ }94\text{ }114\text{ }140\text{ }166\text{ }202\text{ }238\text{ }284\text{ }330\text{ }390\text{ }$

$p_2: 1\text{ }3\text{ }7\text{ }13\text{ }23\text{ }37\text{ }57\text{ }83\text{ }119\text{ }165\text{ }225\text{ }299\text{ }393\text{ }507\text{ }647\text{ }813\text{ }1015\text{ }1253\text{ }1537\text{ }1867\text{ }2257\text{ }$

These are the terms and their respective prefix sums. We denote then $p_0, p_1, p_2,...$ In general, we refer to the sequence obtained by taking prefix sums $k$ times as $p_k$. What I mean above, is notice that in $p_2$, we have $7 = 3 + (3 + 1), 13 = 7 + (3 + 3), 23 = 13 + (7 + 3), 37 = 23 + (7 + 7)$. Which is not exactly (4), but it has the same flavor as (4).

So maybe, this pattern continues?

$1\text{ }1\text{ }2\text{ }2\text{ }4\text{ }4\text{ }6\text{ }6\text{ }10\text{ }10\text{ }14\text{ }\\ 1\text{ }2\text{ }4\text{ }6\text{ }10\text{ }14\text{ }20\text{ }26\text{ }36\text{ }46\text{ }60\text{ }\\ 1\text{ }3\text{ }7\text{ }13\text{ }23\text{ }37\text{ }57\text{ }83\text{ }119\text{ }165\text{ }225\text{ }\\ 1\text{ }4\text{ }11\text{ }24\text{ }47\text{ }84\text{ }141\text{ }224\text{ }343\text{ }508\text{ }733\text{ }\\ 1\text{ }5\text{ }16\text{ }40\text{ }87\text{ }171\text{ }312\text{ }536\text{ }879\text{ }1387\text{ }2120\text{ }\\ 1\text{ }6\text{ }22\text{ }62\text{ }149\text{ }320\text{ }632\text{ }1168\text{ }2047\text{ }3434\text{ }5554\text{ }\\ 1\text{ }7\text{ }29\text{ }91\text{ }240\text{ }560\text{ }1192\text{ }2360\text{ }4407\text{ }7841\text{ }13395\text{ }\\ 1\text{ }8\text{ }37\text{ }128\text{ }368\text{ }928\text{ }2120\text{ }4480\text{ }8887\text{ }16728\text{ }30123\text{ }\\ 1\text{ }9\text{ }46\text{ }174\text{ }542\text{ }1470\text{ }3590\text{ }8070\text{ }16957\text{ }33685\text{ }63808\text{ }\\ 1\text{ }10\text{ }56\text{ }230\text{ }772\text{ }2242\text{ }5832\text{ }13902\text{ }30859\text{ }64544\text{ }128352\text{ }\\$

Indeed it does! $11 = 4 + (3 \time 1 + 4), 24 = 11 + (3 \time 4 + 1), 47 = 24 + (3 \time 4 + 11), 84 = 47 + (3 \time 11 + 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 $p_0$ and $p_1$ 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 $p_1$ and $p_2$ except all the terms are doubled. This seems to fail for $p2$ and $p_3$, but if we wish hard enough, we find $p_2(2n) = 3 p_3(n) + p_3(n-1)$.

Writing a program to figure out this linear relation…

$1\text{ }\\ 2\text{ }\\ 3\text{ }1\text{ }\\ 4\text{ }4\text{ }\\ 5\text{ }10\text{ }1\text{ }\\ 6\text{ }20\text{ }6\text{ }\\ 7\text{ }35\text{ }21\text{ }1\text{ }\\ 8\text{ }56\text{ }56\text{ }8\text{ }\\ 9\text{ }84\text{ }126\text{ }36\text{ }1\text{ }\\$

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

No comment found.

Add a comment

You must login to add a comment.

Site Maintenance

Our platform is currently undergoing maintenance. We apologize for any inconvenience. Please check back later.