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

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.

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

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

Example

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.

Prog

(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

Crossrefs

See A060351 and A367019 for similar sequences.

Cf. A000225.

Sequence in context: A019588 A193953 A201377 * A322942 A060083 A069931

Adjacent sequences: A368067 A368068 A368069 * A368071 A368072 A368073

Keyword

nonn,base

Author

Rémy Sigrist, Dec 10 2023

Status

approved