A303065 Number of numbers < n whose binary representation has the same difference between the numbers of 0's and 1's as n does.

0, 0, 0, 0, 1, 1, 2, 0, 0, 1, 2, 1, 3, 2, 3, 0, 0, 2, 3, 3, 4, 4, 5, 1, 5, 6, 7, 2, 8, 3, 4, 0, 0, 1, 2, 4, 3, 5, 6, 4, 4, 7, 8, 5, 9, 6, 7, 1, 5, 10, 11, 8, 12, 9, 10, 2, 13, 11, 12, 3, 13, 4, 5, 0, 0, 1, 2, 6, 3, 7, 8, 9, 4, 9, 10, 10, 11, 11, 12, 5, 5, 12, 13

Offset: 0

Author

Alex Ratushnyak, Apr 17 2018

Keywords

• nonn
• look
• base

Comments

First occurrence of k, k=0,1,2,...: 0, 4, 6, 12, 20, 22, 25, 26, 28, 44, 49, ..., . - Robert G. Wilson v, Feb 08 2018

Ordinal transform of A037861, minus one. - David Radcliffe, May 21 2025

Examples

			There are two numbers below 6 with number of 1's in the binary representation minus number of 0's equal to 1, namely 1 and 5, therefore a(6)=2.
There are 3 numbers below 12 with number of 1's in the binary representation minus number of 0's equal to 0, namely 2, 9, 10, therefore a(12)=3.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..32768

Crossrefs

Cf. A037861, A097110.

Programs

Maple

b:= n-> `if`(n=0, 1, add(1-2*i, i=Bits[Split](n))):
p:= proc() -1 end:
a:= proc(n) option remember; local t;
      t:= b(n); p(t):= p(t)+1
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, May 21 2025

Mathematica

d[n_] := DigitCount[n, 2, 1] - DigitCount[n, 2, 0]; f[n_] := Block[{fd = d[n], c = k = 0}, While[k < n, If[d@ k == fd, c++]; k++]; c]; Array[f, 83, 0] (* Robert G. Wilson v, Feb 08 2018 *)

Python

d=[0]*200
for n in range(1024):
    b = bin(n)[2:]
    c0 = b.count('0')
    c1 = len(b) - c0
    diff = c0 - c1
    print(d[100+diff], end=', ')
    d[100+diff] += 1

Python

from collections import Counter
from itertools import count, islice
def a303065_gen():
    counter = Counter()
    for n in count():
        bitstring = format(n, 'b')
        diff = bitstring.count('1') - bitstring.count('0')
        yield counter[diff]
        counter[diff] += 1
a303065_list = list(islice(a303065_gen(), 83)) # David Radcliffe, May 21 2025

Formula

a(n) = 0 iff n belongs to A097110. - Rémy Sigrist, May 16 2018

Extensions

Offset corrected by David Radcliffe, May 21 2025