1 bit, 2 bits, 3 bits, …

Question

Given a positive integer \$n\$, your task is to find out the number of partitions \$a_1+a_2+\dots+a_k=n\$ where each \$a_j\$ has exactly \$j\$ bits set.

For instance, there are \$6\$ such partitions for \$n=14\$:

$$\begin{align}&14 = 1_2+110_2+111_2&(1+6+7)\\ &14 = 10_2+101_2+111_2&(2+5+7)\\ &14 = 10_2+1100_2&(2+12)\\ &14 = 100_2+11_2+111_2&(4+3+7)\\ &14 = 100_2+1010_2&(4+10)\\ &14 = 1000_2+110_2&(8+6)\end{align}$$

This is code-golf, so the shortest answer wins.

Test cases

n  f(n)
-------
1  1
2  1
3  0
4  2
5  1
10 2
14 6
19 7
20 10
25 14
33 32
41 47
44 55
50 84
54 102
59 132

Answer 1

Jelly, 10 bytes

ŒṗB§Ṣ⁼JƲ€S

Try it online!

Brute force approach, we generate all partitions then count those that satisfy \$\operatorname{bitsum}(a_j) = j\$. Times out for the \$n = 59\$ test case on TIO, and can handle a test suite going up to the \$n = 50\$ test cases

How it works

ŒṗB§Ṣ⁼JƲ€S - Main link. Takes n on the left
Œṗ         - Integer partitions of n
  B        - Convert everything to binary
       Ʋ€S - Count for how many the following is true:
   §       -   Sum of bits for each
    Ṣ      -   Sorted
     ⁼J    -   Is equal to [1, 2, ..., n] for some n?

Answer 2

Python 3, 74 bytes

f=lambda n,m=1:sum(f(n-i,m+1)for i in range(n+1)if i.bit_count()==m)+(n<1)

Attempt This Online!

-4 bytes suggested by loopy walt.

---

Python 3, 78 bytes

f=lambda n,m=1:sum(f(n-i,m+1)for i in range(n+1)if bin(i).count('1')==m)+(n<1)

Try it online!

Answer 3

Vyxal, 10 bytes

ṄƛbṠs:ż⁼;∑

Try it Online!

Ṅ          # Integer partitions
 ƛ      ;  # Map...
  bṠ       # Sums of binary
    s      # Sorted
       ⁼   # Equal to
     :ż    # 1..length?
         ∑ # Sum (count valid)

Answer 4

Pari/GP, 56 bytes

f(n,m=1)=!n+sum(i=1,n,if(sumdigits(i,2)-m,0,f(n-i,m+1)))

Try it online!

A port of tsh's Python answer.

Answer 5

Wolfram Language (Mathematica), 99 bytes

(l=Length)@Select[Flatten[Permutations/@IntegerPartitions@#,1],Tr/@IntegerDigits[#,2]==Range@l@#&]&

Try it online!

Answer 6

05AB1E, 11 bytes

Åœʒ2вO{āQ}g

Try it online or verify all test cases.

Explanation:

Ŝ         # Get all lists of positive integers that sum to the (implicit) input
  ʒ        # Filter this list of lists by:
   2в      #  Convert it to a binary-list
     O     #  Sum each inner list together
      {    #  Sort it
       ā   #  Push a list in the range [1,length] (without popping)
        Q  #  Check if the two lists are the same
  }        # After the filter:
   g       # Pop and push the length to get the amount of remaining lists
           # (which is output implicitly as result)

Answer 7

Charcoal, 48 bytes

Ｎθ≔⁰η⊞υ⁰ＦＬ↨貫≔υζ≔⟦⟧υＦΦ⊕θ⁼ι⊖Σ↨κ²Ｆζ⊞υ⁺κλ≧⁺№υθη»Ｉη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input n.

≔⁰η

Start with no partitions found.

⊞υ⁰

Start with 1 partition of 0 integers whose sum is therefore 0.

ＦＬ↨貫

Loop over the potential lengths of the partitions.

≔υζ

Save the partitions found so far.

≔⟦⟧υ

Start collecting partitions of this length.

ＦΦ⊕θ⁼ι⊖Σ↨κ²

Loop over all integers up to n with the right number of bits set.

Ｆζ⊞υ⁺κλ

Add these integers to all of the previously found partitions.

≧⁺№υθη

Count how many equal n.

»Ｉη

Output the final total.

Answer 8

JavaScript (Node.js), 68 bytes

f=(n,m,i=1,w)=>n<i?!n:!(w^m)*f(n-i,-~m)+f(n,m,i-~i,-~w)+f(n,m,i+i,w)

Try it online!

Very slow for n>25. Change !(w^m)*f(...) to (w^m?0:f(...)) may be faster but cost +1 byte.

Answer 9

Haskell, 77 74 bytes

import Data.Bits
m!0=1
m!n=sum[(m+1)!(n-i)|i<-[1..n],popCount i==m]
g=(1!)

Try it Online!

-3 bytes thanks to Wheat Wizard

Port of tsh's Python answer.

Answer 10

Python3, 156 bytes:

def f(n,i=1,c=0):
 if c==n:yield
 elif c<n:
  for k in range(1,n-c+1):
   if bin(k).count('1')==i and c+k<=n:yield from f(n,i+1,c+k)
g=lambda x:len([*f(x)])

Try it online!