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,4

Comments

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

Links

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

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 }.

Example

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

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 *)

Prog

(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
(PARI) a(n) = my(w=hammingweight(n)); sum(k=n, 2*n-1, hammingweight(k) == w); \\ Michel Marcus, Mar 16 2023

Crossrefs

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

Sequence in context: A373953 A302291 A300510 * A302439 A331855 A178244

Adjacent sequences: A361076 A361077 A361078 * A361080 A361081 A361082

Keyword

nonn,look,base

Author

Alois P. Heinz, Mar 01 2023

Status

approved