19
\$\begingroup\$

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
\$\endgroup\$
2
  • 5
    \$\begingroup\$ ...red bits, blue bits? :P \$\endgroup\$ Dec 21, 2021 at 23:36
  • 5
    \$\begingroup\$ Seems like a good sequence to add to OEIS \$\endgroup\$
    – isaacg
    Dec 22, 2021 at 9:42

10 Answers 10

6
\$\begingroup\$

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?
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
1
4
\$\begingroup\$

Vyxal, 10 bytes

ṄƛbṠs:ż⁼;∑

Try it Online!

Ṅ          # Integer partitions
 ƛ      ;  # Map...
  bṠ       # Sums of binary
    s      # Sorted
       ⁼   # Equal to
     :ż    # 1..length?
         ∑ # Sum (count valid)
\$\endgroup\$
2
  • \$\begingroup\$ Instead of doing "all permutations", how about sorting the counts, then comparing to 1...length? \$\endgroup\$ Dec 21, 2021 at 23:44
  • \$\begingroup\$ @cairdcoinheringaahing Just thought of that, thanks \$\endgroup\$
    – emanresu A
    Dec 21, 2021 at 23:44
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 99 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Rare to have {} matching... \$\endgroup\$
    – emanresu A
    Dec 23, 2021 at 5:04
2
\$\begingroup\$

Charcoal, 48 bytes

Nθ≔⁰η⊞υ⁰FL↨貫≔υζ≔⟦⟧υFΦ⊕θ⁼ι⊖Σ↨κ²Fζ⊞υ⁺κλ≧⁺№υθη»Iη

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

Nθ

Input n.

≔⁰η

Start with no partitions found.

⊞υ⁰

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

FL↨貫

Loop over the potential lengths of the partitions.

≔υζ

Save the partitions found so far.

≔⟦⟧υ

Start collecting partitions of this length.

FΦ⊕θ⁼ι⊖Σ↨κ²

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

Fζ⊞υ⁺κλ

Add these integers to all of the previously found partitions.

≧⁺№υθη

Count how many equal n.

»Iη

Output the final total.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.