# Number of solutions to a binary weight equation

We define $$\a(n)\$$ as the 1-indexed position of $$\n\$$ in the sequence of positive integers with the same binary weight, i.e. the same number of 1's in their binary representation. This is A263017.

Given a positive integer $$\n\$$, your task is to determine how many positive integers $$\k\$$ satisfy:

$$k-a(k)=n$$

For instance, $$\n=6\$$ can be expressed as:

• $$\n=7-a(7)=7-1\$$ ($$\7\$$ being the 1st integer with 3 bits set)
• $$\n=12-a(12)=12-6\$$ ($$\12\$$ being the 6th integer with 2 bits set)

There's no other $$\k\$$ such that $$\k-a(k)=6\$$. So the expected answer is $$\2\$$.

This is .

### Test cases

Input Output
1     1
6     2
7     0
25    4
43    0
62    1
103   5
1000  0
1012  6
2000  1
3705  7
4377  8


Or as lists:

Input : [1, 6, 7, 25, 43, 62, 103, 1000, 1012, 2000, 3705, 4377]
Output: [1, 2, 0, 4, 0, 1, 5, 0, 6, 1, 7, 8]


# MATL, 15 bytes

t4*:tB!s&=Rs-=s


This makes use of the following result:

## Claim

$$\a(n) \le 3n/4\$$ for $$\n \geq 3\$$.

Here is a graphical illustration. The bound is quite loose, but it is sufficient to establish that only a finite number of values of $$\k\$$ need to be tested for a given $$\n\$$ (more on that in “How the code works”).

Proof

The sequence $$\a(n)\$$ (A263017) is the amount of numbers in the set $$\\{1,2,\ldots,n\}\$$ that have the same binary weight as $$\n\$$. The binary expansion of $$\n\$$ has $$\b \leq \log_2 n + 1\$$ digits, with a leading 1. Let $$\w\$$ be the binary weight of $$\n\$$. Clearly $$\w \in \{0,\ldots,b\}\$$.

The number of unique permutations of the binary expansion of $$\n\$$, not necessarily with a leading 1, is $$\{b\choose w}\$$. $$\a(n)\$$ will be at most equal to this value. It can be less, because some of the permutations may produce a number exceeding $$\n\$$. Thus,

$$a(n) \leq {b\choose w}.$$

For $$\b\$$ even, the bound

$${2m \choose m} \leq \frac{4^m}{\sqrt{3m+1}} \text{ for all } m \geq 1$$

and the fact that $$\{b\choose w} \leq {b\choose b/2}\$$ imply that

$${b \choose w} \leq \frac{2^b}{\sqrt{\frac{3b+2}{2}}}.$$

For $$\b\$$ not necessarily even, the bound holds with $$\b\$$ replaced by $$\b+1\$$:

$${b \choose w} \leq \frac{2^{b+1}}{\sqrt{\frac{3b+5}{2}}}.$$

Since $$\b \leq \log_2 n + 1\$$,

$$a(n) \leq {b\choose w} \leq \frac{2^{b+1}}{\sqrt{\frac{3b+5}{2}}} \leq \frac{4n}{\sqrt{ 3/2 \cdot \log_2 n + 4}}.$$

This is less than $$\3n/4\$$ for $$\n \geq 80478\$$, because

$$\sqrt{3/2 \cdot \log_2 80478 + 4}\ = 5.3333348 > 16/3.$$

For $$\n = 3, \ldots, 80477 \$$, direct computation of $$\a(n)\$$ shows that $$\a(n) \leq 3n/4\$$. Therefore $$\a(n) \leq 3n/4\$$ for $$\n \geq 3\$$.

## How the code works

The above result implies that

$$k-a(k) \geq k / 4.$$

for all $$\k \geq 3\$$. Thus, given $$\n\$$, to compute the number of positive integers $$\k\$$ that satisfy

$$k-a(k)\ = n$$

it suffices to test the latter equality for $$\k = 1, \ldots, 4n\$$.

Consider input 1 as an example.

t4*  % Implicit input: n. Duplicate. Multiply by 4
% STACK: 1, 4
:    % Range. Gives [1 2 ... 4*n]. This is the vector of k values
% STACK: 1, [1 2 3 4]
tB   % Duplicate. Binary expansion. Gives a binary matrix, where each row
% corresponds to a value of k
% STACK: 1, [1 2 3 4], [0 0 1;
0 1 0;
0 1 1;
1 0 0]
!s   % Tranpose. Sum of each column. This gives the binary weights
% STACK: 1, [1 2 3 4], [1 1 2 1]
&=   % Matrix of pair-wise equality comparisons
% STACK: 1, [1 2 3 4], [1 1 0 1;
1 1 0 1;
0 0 1 0;
1 1 0 1]
R    % Upper triangular part. This sets elements below the diagonal to 0
% STACK: 1, [1 2 3 4], [1 1 0 1;
0 1 0 1;
0 0 1 0;
0 0 0 1]
s    % Sum of each column. For each column k, this gives the amount of
% number up to k with the same weight as k; that is, a(k). Note that
% the condition "up to k" corresponds to having taken the upper
% triangular part of the matrix
% STACK: 1, [1 2 3 4], [1 2 1 3]
-    % Subtract, element-wise. This gives k-a(k)
% STACK: 1, [0 0 2 1]
=    % Equality comparison, element-wise. This compares n with each
% value k-a(k)
% STACK: [0 0 0 1]
s    % Sum. Implicit display
% STACK: 1


# Python 3, 98 96 bytes

Saved 2 bytes thanks to Surculose Sputum!!!

lambda n:sum(n==sum(bin(i).count('1')!=bin(k).count('1')for i in range(1,k))for k in range(5*n))


Try it online!

Brute force and very slow.

• Could you explain why $k$ is bounded by $5n$? It's not immediately obvious to me May 14, 2020 at 20:15
• @mathjunkie Because it works for $1$ and it seems to drop as $n$ increases going down to $3n$ for larger numbers. More ad hoc experimentation than maths. :-( May 14, 2020 at 20:22
• 96 bytes, using the fact that there must be exactly $n$ numbers smaller than $k$ that has different weight. May 14, 2020 at 22:09
• @SurculoseSputum Nice one - thanks! :-) May 14, 2020 at 22:56

# C (gcc), 106 $$\\cdots\$$ 100 96 bytes

Saved 5 bytes thanks to the man himself Arnauld!!!
Saved 1 5 bytes thanks to l4m2!!!
Saved 4 bytes thanks to ceilingcat!!!

b(n){n=n?1+b(n&n-1):0;}k;i;s;p;f(n){for(p=0,k=5*n;i=k--;p+=n==s)for(s=0;--i;)s+=b(i)!=b(k);s=p;}


Try it online!

Port of my Python answer, much a bit faster.

• b(n){n=n?1+b(n&n-1):0;} would be 5 bytes shorter ... but ~10 times slower. May 15, 2020 at 12:49
• @Arnauld Who's watching timers anyway? Nice one - thanks! :D May 15, 2020 at 12:56
• Why do you still leave the newline?
– l4m2
May 15, 2020 at 15:47
• also k++ can be merged into condition
– l4m2
May 15, 2020 at 15:48
• @l4m2 Oops, thanks for pointing that out! :-) May 15, 2020 at 15:53

# APL (Dyalog Unicode), 41 bytesSBCS

{1⊥⍵=i-+⌿(⊢×∘.≤⍨∘⍳∘≢)∘.=⍨+⌿2∘⊥⍣¯1⊢i←⍳4×⍵}


Try it online! (Assumes ⎕IO ← 1)

This is a direct translation of Luis Mendo's really good answer so go give that one an upvote if you haven't.

How it works (reading the submission from right to left):

• i←⍳4×⍵ multiply the input ⍵ by 4, create a range from 1 to 4⍵ and save it in the variable i for later;
• 2∘⊥⍣¯1 create a matrix of binary conversions (one col per number);
• +⌿ column-wise sum;
• ∘.=⍨ matrix of pair-wise equality comparisons;
• (⊢×∘.≤⍨∘⍳∘≢) from which we extract the upper triangular part;
• +⌿ column-wise sum again;
• i- the original range 1 ... 4⍵ minus the new vector;
• ⍵= compared to the input number;
• 1⊥ and summed up.

# JavaScript (Node.js), 70 bytes

n=>f=(i=g=i=>+i&&1+g(i&i-1))=>i>5*n?0:(i-(g[j=g(i)]=-~g[j])==n)+f(-~i)


Try it online!

# JavaScript (Node.js), 81 bytes

n=>[...Array(n*5)].reduce(s=>s+=++i-(g[j=g(i)]=-~g[j])==n,i=0,g=i=>i&&1+g(i&i-1))


Try it online!

Thank Arnauld for -3 bytes

# C (gcc), 71 bytes

i,k;f(n){int C={};for(i=k=0;i++/n/5<=k;)k+=i-++C[*C+=2-ffs(i)]==n;}


Try it online!

WTF is happening?

# C (gcc), 72 bytes mainly by dingledooper

i,k;f(n){int C={};for(i=k=0;i++<5*n;)k+=i-++C[*C+=2-ffs(i)]==n;i=k;}


Try it online!

# C (gcc), 79 bytes

k;f(n){int C={};for(k=0;k++<5*n;)*C+=k-++C[__builtin_popcount(k)]==n;k=*C;}


Try it online!