cp's OEIS Frontend

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.

%I A368070 #33 Jun 03 2025 08:42:49
%S A368070 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,
%T A368070 10,14,5,1,6,29,78,55,99,181,132,50,64,181,272,155,111,169,78,20,15,
%U A368070 55,111,71,90,155,99,34,20,50,64,34,15,20,6,1,7,41,133,99
%N 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.
%C A368070 Leading zeros may appear in binary words w_2, ..., w_{k-1}.
%C A368070 a(n) gives the number of ways to erase the binary expansion of n bit by bit.
%H A368070 Rémy Sigrist, <a href="/A368070/b368070.txt">Table of n, a(n) for n = 0..8192</a>
%H A368070 Rémy Sigrist, <a href="/A368070/a368070.gp.txt">PARI program</a>
%H A368070 Natalia L. Skirrow, <a href="/wiki/User:Nathan_L._Skirrow/bitwise_permutations">bitwise permutations</a>
%H A368070 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A368070 a(n) = 1 iff n belongs to A000225.
%F A368070 a(2^k) = k + 1 for any k >= 0.
%F A368070 a(n) >= A367019(n).
%F A368070 a(n) <= A383254(n). (See comment there) - _Natalia L. Skirrow_, Apr 20 2025
%e A368070 For n = 5:
%e A368070 - the binary expansion of 5 is "101",
%e A368070 - we have the following appropriate sequences of binary words:
%e A368070      ("101", "11", "1", "")
%e A368070      ("101", "10", "1", "")
%e A368070      ("101", "10", "0", "")
%e A368070      ("101", "01", "1", "")
%e A368070      ("101", "01", "0", "")
%e A368070 - hence a(5) = 5.
%o A368070 (PARI) \\ See Links section.
%o A368070 (Python)
%o A368070 def A368070(n):
%o A368070   m=0
%o A368070   r=[1]
%o A368070   for k in range(n.bit_length()):
%o A368070     if m!=(m:=n>>k&1): r=r[::-1]
%o A368070     for j in range(k): r[j+1]+=r[j]
%o A368070     r.insert(0,0)
%o A368070   return sum(r) # _Natalia L. Skirrow_, Apr 20 2025
%o A368070 (Python)
%o A368070 from fractions import Fraction as frac
%o A368070 inte=lambda p: [0]+[frac(c,i+1) for i,c in enumerate(p)]
%o A368070 from math import factorial as fact
%o A368070 def A368070(n):
%o A368070   r=[1]
%o A368070   for k in range(n.bit_length()):
%o A368070     i=inte(r)
%o A368070     r=i if n>>k&1 else [sum(i)]+[-c for c in i[1:]]
%o A368070   return int(fact(n.bit_length()+1)*sum(inte(r)))
%o A368070 #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
%Y A368070 See A060351 and A367019 for similar sequences.
%Y A368070 Cf. A000225.
%K A368070 nonn,base
%O A368070 0,3
%A A368070 _Rémy Sigrist_, Dec 10 2023