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

Author

Rémy Sigrist, Dec 10 2023

Keywords

• nonn
• base

Comments

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

Examples

			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.
		

Links

• 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

Crossrefs

See A060351 and A368070 for similar sequences.

Cf. A000225.

Programs

PARI

See Links section.

Formula

a(n) = 1 iff n belongs to A000225.

a(2^k) = k + 1 for any k >= 0.

a(n) <= A368070(n).