| Bytes | Lang | Time | Link |
|---|---|---|---|
| 006 | Nekomata + n | 240614T132720Z | alephalp |
| 073 | Python | 211222T033042Z | tsh |
| 044 | Charcoal | 211222T010107Z | Neil |
| 074 | Haskell | 211224T212953Z | Madison |
| 011 | 05AB1E | 211222T223907Z | Kevin Cr |
| 156 | Python3 | 211222T181921Z | Ajax1234 |
| 099 | Wolfram Language Mathematica | 211222T133159Z | ZaMoC |
| 056 | Pari/GP | 211222T063114Z | alephalp |
| 068 | JavaScript Node.js | 211222T040128Z | tsh |
| 010 | Jelly | 211221T233448Z | caird co |
| 010 | Vyxal | 211221T234213Z | emanresu |
Nekomata + -n, 6 bytes
ṖÞx→↕=
ṖÞx→↕=
Ṗ Find an integer partition of the input
Þ Pop counts (sums of bits) of each element
x Range from 0 to length - 1 (without popping)
→ Increment
↕ Find a permutation of the range
= Check equality
-n counts the number of solutions.
Python, 73 bytes
f=lambda n,m=1:sum(f(n-i,m+1)for i in range(n+1)if i.bit_count()==m)+0**n
-4 bytes suggested by loopy walt. -1 byte suggested by Jitse.
Charcoal, 48 44 bytes
Nθ⊞υ⁰FL↨貫≔υζ≔⟦⟧υFΦ⊕θ⁼ι⊖Σ↨κ²Fζ⊞υ⁺κλM№υθ→»Iⅈ
Try it online! Link is to verbose version of code. Explanation:
Nθ
Input n.
⊞υ⁰
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.
M№υθ→
Count how many equal n.
»Iⅈ
Output the final total.
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!)
-3 bytes thanks to Wheat Wizard
Port of tsh's Python answer.
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)
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)])
Wolfram Language (Mathematica), 99 bytes
(l=Length)@Select[Flatten[Permutations/@IntegerPartitions@#,1],Tr/@IntegerDigits[#,2]==Range@l@#&]&
Pari/GP, 56 bytes
f(n,m=1)=!n+sum(i=1,n,if(sumdigits(i,2)-m,0,f(n-i,m+1)))
A port of tsh's Python answer.
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)
Very slow for n>25. Change !(w^m)*f(...) to (w^m?0:f(...)) may be faster but cost +1 byte.
Jelly, 10 bytes
ŒṗB§Ṣ⁼JƲ€S
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?
Vyxal, 10 bytes
ṄƛbṠs:ż⁼;∑
Ṅ # Integer partitions
ƛ ; # Map...
bṠ # Sums of binary
s # Sorted
⁼ # Equal to
:ż # 1..length?
∑ # Sum (count valid)