Number of binary partitions

Question

We all know that any positive integer can be represented as the sum of powers of two. This is how binary representations work. However there's not just one way to do this. The canonical method, used in binary representations represents it as the sum of unique powers of two. For example \$5=2^0+2^2\$. However since \$2^0=1\$ we can write any number just adding \$2^0\$. For example \$5=2^0+2^0+2^0+2^0+2^0\$.

How many ways are there to write a given number as the sum of powers of two? Let's write a program to see. We don't want to double count methods that are equivalent under associativity or commutativity, so \$2^0+2^2\$ and \$2^2+2^0\$ count as the same way because we've just changed the order.

Since this is sequence you may use any of the following IO formats where \$f(n)\$ is the number of ways to write \$n\$ :

• Take \$n\$ as input and output \$f(n)\$.
• Take \$n\$ as input and output \$f(x)\$ for \$x\$ up to \$n\$ in order.
• Output all \$f(x)\$ for every positive integer \$x\$ in order.

You may optionally choose to also include \$f(0)\$.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

Here are the first 60 values:

1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294, 1460

More can be found at OEIS A018819

Answer 1

Haskell, 22 bytes

l=scanl(+)1$(:[0])=<<l

Try it online!

Defines the infinite list l of [f(1),f(2),...].

The OEIS says the generating function satisfies \$A(x^2)=(1-x)A(x)\$, which rearranges to \$A(x) = \frac{1}{1-x}A(x^2) \$. Starting with \$A(x)\$, we can interpret \$A(x^2)\$ as interspersing a zero after each element, (:[0])=<< in Haskell. Then, multiplying by \$\frac{1}{1-x}\$ is taking the cumulative sum scanl1(+).

A small adjustment to omit the first initial 1 from the OEIS sequence is to do scanl(+)1 instead. This also removes a circular dependency in defining that initial element, fixing the issue that \$A(x) = \frac{1}{1-x}A(x^2) \$ only defined \$A\$ up to a constant multiplier.

Now we put these together as l=scanl(+)1$(:[0])=<<l, which defines the elements of the infinite list l. Haskell's lazy evaluation allows this infinite list to be defined in terms of itself, as long as each element depends only on earlier elements, which is the case here.

Answer 2

Python, 31 bytes

f=lambda n:n<2or f(n-2)+f(n//2)

Attempt This Online!

This can be derived from the recursion below by taking the difference between f(n) and f(n-2) which cancels most of the terms in the sum.

Old Python, 42 bytes

f=lambda n:n<2or sum(map(f,range(n//2+1)))

Attempt This Online!

The "obvious" recursion.

How?

First decide how many 1s. The remainder must be even and we can halve it and any partition of it. This can be done for any even remainder <=n. The recurrence follows.

Full program

Python, 40 bytes

t,*a=1,1
for i in a:print(i);t+=i;a+=t,t

Attempt This Online!

EDIT: Just seeing that @xnor posted the exact same program a bit earlier.

In theory produces the entire sequence (from term #1).

This can be either viewed as unrolling the recursion at the top of this post or --- as far as I understand --- as a port of the generating function approach a few answers have used. I can't know for sure because these languages are all esoteric to me.

Answer 3

Perl, 83 75 73 59 58 bytes

-14 bytes thanks to a recursive regex I discovered while working on Sum of Powers of 2

sub{my$i;1x pop~~/^((\1|^.)(\2((?3))\4|))*$(??{++$i})/;$i}

Try it online!

This is definitely not the shortest possible Perl function by any means. But the idea here was to make a partition counter with all the logic in a regex, like my previous Fibonacci and Padovan answers.

This counts all the different ways the regex can make a complete match from start to finish, where the input number is provided to the regex in unary, as the length of a string of identical characters.

^                  # Anchor to the beginning of the string.
(                  # \1
    # Match \1 multiplied by any power of 2; this will be captured in \1 for use
    # by the next iteration. As such, the value of \1 can only increase to a
    # higher power of 2, or stay the same, but can never go down. In this way we
    # ensure against double counting methods that are equivalent under
    # associativity or commutativity.
    (\1|^.)        # \2 = the power of 2 used by the previous iteration, or 1 if
                   #      this is the first iteration
    (\2((?3))\4|)  # Match \2 * ({any power of 2} - 1)
)*
$                  # Assert we are at the end of the string. If we aren't, the
                   # regex will backtrack and try different power(s) of two to
                   # get here, and this failed attempt won't be counted.
(?{++$i})          # Perl embedded code to increment the partition counter.
\1                 # Attempt to match something that can never match, to force
                   # the regex engine to backtrack. A backreference is used
                   # because if we tried to use "^" or "z", the regex engine
                   # would do smart optimization, which we don't want.

The power of 2 logic is based on the regex x(x((?1))\2|) (Try it online!), except that the xs are replaced with \2, to ensure that it never matches a powers of 2 less than those matched on previous iterations of the main loop.

Regex 🐇 (Perl / PCRE2 _^v10.34+), 47 39 25 bytes

^((\1|^x)(\2((?3))\4|))*$

Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method. It can yield outputs bigger than the input, and is really good at multiplying.)

Try it online! - Perl v5.28.2
Attempt This Online! - Perl v5.36+
Attempt This Online! - PCRE2 v10.40+

Regex 🐇 (_{^{Perl /}} PCRE2), 41 bytes

^((?=(?(3)(\3)))((\2|^x)(\4((?5))\6|)))*$

Try it online! - Perl
Try it online! - PCRE2 v10.33
Attempt This Online! - PCRE2 v10.40+

This is a port of the 25 byte regex. PCRE v10.33 and earlier automatically makes any group containing a nested backreference atomic, so this port works around that by enclosing the main group in a top level group, and copying backreference \3 into \2 inside a lookahead before entering group 3. The copy is done inside a conditional, because there isn't necessarily even going to be enough space to match \3 in a lookahead, and if there isn't, the match on that iteration needs to fail.

Regex 🐇 (_{^{Perl /}} PCRE), 55 bytes

^((?=(?(3)(\3)))((\2|^x)(?=(.*))((?(?=\5)\4|\6\6))*))*$

Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2

PCRE1 complains recursive call could loop indefinitely on the 41 byte regex, and that can be worked around, as ^((?=(?(3)(\3)))((\2|^)(x\4((?5))\6|))x)*$ (42 bytes) which works on PCRE2, but the recursive method of matching arbitrary powers of 2 doesn't work on PCRE1 anyway, since it only has atomic subroutine calling. So this 55 byte regex is a port of the earlier 39 byte non-recursive regex, ^((\1|^x)(?=(.*))((?(?=\3)\2|\4\4))*)*$.

Answer 4

Jelly, 5 bytes

H߀S‘

A recursive, monadic Link that accepts a non-negative integer and yields the number of binary partitions.

Try it online! Or see the test-suite.

How?

H߀S‘ - Link: integer, n
H     - halve -> n/2
  €   - for each i in [1..floor(n/2)]:
 ß    -   call this Link with argument n=i
   S  - sum
    ‘ - increment

Answer 5

Python, 40 bytes

f=lambda n:sum(map(f,range(1,n//2+1)))+1

Attempt This Online!

Answer 6

C (gcc), 27 bytes

f(n){n=n<2?:f(n/2)+f(n-2);}

Try it online!

Port of loopy walt's Python answer

Answer 7

HOPS, 17 bytes

A=1+x*(A+A@(x^2))

Attempt This Online!

Based on this formula on OEIS:

G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - Michael Somos, Aug 25 2003

Answer 8

Python 3, 40 bytes

t,=l=[1]
for x in l:print(x);t+=x;l+=t,t

Try it online!

A program that prints the sequence forever. While longer than loopy walt's recursive function, I think this shows off an interesting method of generating the sequence on the fly by running an infinite loop by appending new elements to the list being iterated over, specifically, two copies of the current running sum starting at 1.

Answer 9

Retina, 22 bytes

.+
*
+%Lw`^(_*)(?=\1)

Try it online! Link includes test cases. Explanation:

.+
*

Convert to unary.

Lw`^(_*)(?=\1)

Replace the input n with a list 0..n/2 inclusive.

+%`

Repeat the above expansion on every value in the list until it turns into a list of all zeros.

Output the length of the final list.

Answer 10

APL, 19 bytes

{2≥⍵:⍵⋄1++/∇¨⍳⌊⍵÷2}

Answer 11

Charcoal, 15 bytes

ＦＮ⊞υ∨¬ιΣ…υ⊕⊘ιＩυ

Try it online! Link is to verbose version of code. Outputs the first n values (0-indexed). Explanation:

ＦＮ

Repeat n times.

⊞υ∨¬ιΣ…υ⊕⊘ι

On the first iteration, just push 1 to the predefined empty list, otherwise push the sum of the first half of the list (inclusive).

Ｉυ

Output the resulting list.

Answer 12

Ruby, 25 bytes

f=->n{1+(1..n/2).sum(&f)}

Try it online!

The "original" recursion in Ruby is 1 byte shorter than the optimized function by loopy walt.

Answer 13

05AB1E, 7 bytes

λN;ï₅₂+

Outputs the infinite sequence.
(Should have been 6 bytes without the ï, but apparently there is a bug in 05AB1E with decimal values and ₅.)

Try it online.

Explanation:

λ        # Start a recursive environment,
         # to output the infinite sequence
         # (which is output implicitly at the end)
         # Implicitly starting at a(0)=1
         # Where every following a(n) is calculated as:
 N;      #  Push n/2
   ï     #  (bug workaround: truncate it to an integer)
    ₅    #  Pop and push a(n//2)
     ₂   #  Push a(n-2)
      +  #  Add them together: a(n//2)+a(n-2)

Answer 14

Vyxal, 6 bytes

λ½vx∑›

Try it Online!

λ½vx∑›
λ      # Open a lambda for recursion: f(n)
 ½     #  Halve to n/2
  vx   #  For each x in [1..floor(n/2)], call f(x)
    ∑  #  Sum
     › #  Increment