A368070 a(n) is the number of sequences of binary words (w_1, ..., w_k) such that w_1 corresponds to the binary expansion of n (without leading zeros), for m = 1..k-1, w_{m+1} is obtained by removing one bit from w_m, and w_k is the empty word.

1, 1, 2, 1, 3, 5, 3, 1, 4, 11, 16, 9, 6, 9, 4, 1, 5, 19, 40, 26, 35, 61, 40, 14, 10, 26, 35, 19, 10, 14, 5, 1, 6, 29, 78, 55, 99, 181, 132, 50, 64, 181, 272, 155, 111, 169, 78, 20, 15, 55, 111, 71, 90, 155, 99, 34, 20, 50, 64, 34, 15, 20, 6, 1, 7, 41, 133, 99

Offset: 0

Author

Rémy Sigrist, Dec 10 2023

Keywords

• nonn
• base

Comments

Leading zeros may appear in binary words w_2, ..., w_{k-1}.

a(n) gives the number of ways to erase the binary expansion of n bit by bit.

Examples

			For n = 5:
- the binary expansion of 5 is "101",
- we have the following appropriate sequences of binary words:
     ("101", "11", "1", "")
     ("101", "10", "1", "")
     ("101", "10", "0", "")
     ("101", "01", "1", "")
     ("101", "01", "0", "")
- hence a(5) = 5.
		

Links

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

Crossrefs

See A060351 and A367019 for similar sequences.

Cf. A000225.

Programs

PARI

\\ See Links section.

Python

def A368070(n):
  m=0
  r=[1]
  for k in range(n.bit_length()):
    if m!=(m:=n>>k&1): r=r[::-1]
    for j in range(k): r[j+1]+=r[j]
    r.insert(0,0)
  return sum(r) # Natalia L. Skirrow, Apr 20 2025

Python

from fractions import Fraction as frac
inte=lambda p: [0]+[frac(c,i+1) for i,c in enumerate(p)]
from math import factorial as fact
def A368070(n):
  r=[1]
  for k in range(n.bit_length()):
    i=inte(r)
    r=i if n>>k&1 else [sum(i)]+[-c for c in i[1:]]
  return int(fact(n.bit_length()+1)*sum(inte(r)))
#without the multiplication, this is the probability that a sequence of real numbers in [0,1] satisfies the chain of inequalities. # Natalia L. Skirrow, Apr 20 2025

Formula

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

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

a(n) >= A367019(n).

a(n) <= A383254(n). (See comment there) - Natalia L. Skirrow, Apr 20 2025