# 1 bit, 2 bits, 3 bits, …

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 , 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

• ...red bits, blue bits? :P Dec 21, 2021 at 23:36
• Seems like a good sequence to add to OEIS Dec 22, 2021 at 9:42
• @isaacg Better late than never, this is now A367680. Nov 27, 2023 at 19:55

# 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?


# 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!

• 74, using newer Python version ato.pxeger.com/… Dec 22, 2021 at 4:55

# Vyxal, 10 bytes

ṄƛbṠs:ż⁼;∑


Try it Online!

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

• Instead of doing "all permutations", how about sorting the counts, then comparing to 1...length? Dec 21, 2021 at 23:44
• @cairdcoinheringaahing Just thought of that, thanks Dec 21, 2021 at 23:44

# 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.

# Wolfram Language (Mathematica), 99 bytes

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


Try it online!

# 05AB1E, 11 bytes

Åœʒ2вO{āQ}g


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)

• Rare to have {} matching... Dec 23, 2021 at 5:04

# Charcoal, 48 bytes

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


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

Ｎθ


Input n.

≔⁰η


⊞υ⁰


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.

# 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.

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

def f(n,i=1,c=0):