13
\$\begingroup\$

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]
\$\endgroup\$
0
12
\$\begingroup\$

MATL, 15 bytes

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

Try it online! Or verify all test cases.

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ Could you explain why \$k\$ is bounded by \$5n\$? It's not immediately obvious to me \$\endgroup\$ – math junkie May 14 '20 at 20:15
  • \$\begingroup\$ @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. :-( \$\endgroup\$ – Noodle9 May 14 '20 at 20:22
  • \$\begingroup\$ 96 bytes, using the fact that there must be exactly \$n\$ numbers smaller than \$k\$ that has different weight. \$\endgroup\$ – Surculose Sputum May 14 '20 at 22:09
  • \$\begingroup\$ @SurculoseSputum Nice one - thanks! :-) \$\endgroup\$ – Noodle9 May 14 '20 at 22:56
2
\$\begingroup\$

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.

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

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.
\$\endgroup\$
1
\$\begingroup\$

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

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

C (gcc), 71 bytes

i,k;f(n){int C[99]={};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[99]={};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[99]={};for(k=0;k++<5*n;)*C+=k-++C[__builtin_popcount(k)]==n;k=*C;}

Try it online!

Port of my Javascript answer

\$\endgroup\$
0

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.