A361079 Number of integers in [n .. 2n-1] having the same binary weight as n.

0, 1, 1, 2, 1, 3, 3, 3, 1, 4, 4, 5, 4, 6, 6, 4, 1, 5, 5, 8, 5, 9, 9, 7, 5, 10, 10, 9, 10, 10, 10, 5, 1, 6, 6, 12, 6, 13, 13, 13, 6, 14, 14, 15, 14, 16, 16, 9, 6, 15, 15, 18, 15, 19, 19, 12, 15, 20, 20, 14, 20, 15, 15, 6, 1, 7, 7, 17, 7, 18, 18, 23, 7, 19, 19

Offset: 0

Author

Alois P. Heinz, Mar 01 2023

Keywords

• nonn
• look
• base

Comments

Or number of steps it takes to double n, where each step goes to the next larger integer with the same binary weight.

Examples

			a(9) = 4: 9 -> 10 -> 12 -> 17 -> 18 or in binary: 1001_2 -> 1010_2 -> 1100_2 -> 10001_2 -> 10010_2.
		

Links

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

Crossrefs

Cf. A000079, A000120, A057168, A068076, A263017.

Programs

Maple

b:= proc(n) option remember; uses Bits; local c, l, k;
      c, l:= 0, [Split(n)[], 0];
      for k while l[k]<>1 or l[k+1]<>0 do c:=c+l[k] od;
      Join([1$c, 0$k-c, 1, l[k+2..-1][]])
    end:
a:= proc(n) option remember; local i, m, t; m, t:=n, 2*n;
      for i from 0 while m<>t do m:= b(m) od; i
    end:
seq(a(n), n=0..100);

Mathematica

f[n_] := f[n] = DigitCount[n, 2, 1]; a[n_] := Count[ Array[f, n, n], f[n]]; Array[a, 75, 0] (* Robert G. Wilson v, Mar 15 2023 *)

PARI

a(n) = my(w=hammingweight(n)); sum(k=n, 2*n-1, hammingweight(k) == w); \\ Michel Marcus, Mar 16 2023

Python

from math import comb
def A361079(n):
    c, k = 0, 1
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            c += comb(i+1,k)-comb(i,k)
            k += 1
    return c # Chai Wah Wu, Mar 01 2023

Formula

a(n) = |{ k in [n, 2n-1] : A000120(k) = A000120(n) }|.

((x-> A057168(x))^a(n))(n) = 2*n.

a(n) = A068076(2n) - A068076(n) = A263017(2n) - A263017(n).

a(n) = 1 <=> n in { A000079 }.