A368070 -id:A368070 - cp's OEIS frontend

A367019 a(n) is the number of strictly decreasing sequences (w_1, ..., w_k) such that w_1 = n, for m = 1..k-1, w_{m+1} is obtained by removing one significant binary digit from w_m, and w_k = 0.

1, 1, 2, 1, 3, 4, 3, 1, 4, 8, 12, 6, 6, 8, 4, 1, 5, 13, 26, 15, 25, 38, 25, 8, 10, 22, 30, 15, 10, 13, 5, 1, 6, 19, 46, 29, 59, 96, 69, 24, 44, 106, 156, 82, 66, 92, 42, 10, 15, 45, 88, 52, 75, 118, 75, 24, 20, 45, 58, 29, 15, 19, 6, 1, 7, 26, 73, 49, 114, 194

Offset: 0

Rémy Sigrist, Dec 10 2023

a(n) gives the number of ways to zero n bit by bit.

			For n = 5:
- the binary expansion of 5 is "101",
- we have the following appropriate sequences:
     (5, 3, 1, 0)
     (5, 2, 1, 0)
     (5, 2, 0)
     (5, 1, 0)
- hence a(5) = 4.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Rémy Sigrist, PARI program
Index entries for sequences related to binary expansion of n

See A060351 and A368070 for similar sequences.

Cf. A000225.

PARI
```
See Links section.
```

a(n) = 1 iff n belongs to A000225.
a(2^k) = k + 1 for any k >= 0.
a(n) <= A368070(n).

A383718 a(n) is the multinomial coefficient (length of n in binary) choose (the lengths of runs in n's binary expansion).

Original entry on oeis.org

1, 1, 2, 1, 3, 6, 3, 1, 4, 12, 24, 12, 6, 12, 4, 1, 5, 20, 60, 30, 60, 120, 60, 20, 10, 30, 60, 30, 10, 20, 5, 1, 6, 30, 120, 60, 180, 360, 180, 60, 120, 360, 720, 360, 180, 360, 120, 30, 15, 60, 180, 90, 180, 360, 180, 60, 20, 60, 120, 60, 15, 30, 6, 1

Offset: 0

Natalia L. Skirrow, Apr 20 2025

			2025_10 = 11111101001_2, with run lengths {6,1,1,2,1}; 11!/(6!*1!^3*2!) = 27720.

Natalia L. Skirrow, bitwise permutations

Cf. A101211, A368070, A023758, A000975, A000111.

from itertools import groupby
from math import prod, factorial as fact
rlenomial=lambda n: fact(l:=n.bit_length())//prod(map(lambda n: fact(len(list(n[1]))),groupby(map(lambda i: n>>i&1,range(l)))))

a(n) >= A368070(n), with equality iff n is in A023758. (In particular, if n' is formed by appending a bit to n's expansion, a(n')/A368070(n') >= a(n)/A368070(n).)
The ratio r = a(n)/A368070(n) reaches minima when n is in A000975; a(A000975(n)) = n!, whereas A368070(A000975(n)) = A000111(n+1).
As such, lim inf r = 0, but lim inf_{n>=m} log(a(n))/log(A368070(n)) is 1, converging as about 1 - log_{log_2(n)}(Pi/2)

cp's OEIS Frontend

A367019 a(n) is the number of strictly decreasing sequences (w_1, ..., w_k) such that w_1 = n, for m = 1..k-1, w_{m+1} is obtained by removing one significant binary digit from w_m, and w_k = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula