login
A361079
Number of integers in [n .. 2n-1] having the same binary weight as n.
1
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
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
KEYWORD
nonn,look,base
AUTHOR
Alois P. Heinz, Mar 01 2023
STATUS
approved