cp's OEIS Frontend

A161001 Those positive integers n that when read in binary contains runs of 0's and 1's being of distinct lengths, the list of lengths forming a permutation of some number of consecutive positive integers.

%I A161001 #12 Jan 05 2021 03:30:02
%S A161001 1,3,4,6,7,15,24,28,31,35,39,49,55,57,59,63,112,120,127,255,391,399,
%T A161001 451,463,480,483,487,496,511,536,540,560,572,624,632,776,782,784,798,
%U A161001 880,888,900,902,912,926,944,956,964,966,968,974,984,988,1023,1984,2016
%N A161001 Those positive integers n that when read in binary contains runs of 0's and 1's being of distinct lengths, the list of lengths forming a permutation of some number of consecutive positive integers.
%C A161001 Think of binary n as a string S of 0's and 1's. By a "run" of 0's or 1's, it is meant either a substring all of contiguous 0's, each run bounded by 1's or the edge of S; or a substring all of contiguous 1's, each run bounded by 0's or the edge of S.
%H A161001 Michael S. Branicky, <a href="/A161001/b161001.txt">Table of n, a(n) for n = 1..10000</a>
%e A161001 451 in binary is 111000011. This contains a run of three 1's, followed by a run of four 0's, followed by a run of two 1's. Since (3,4,2) is a permutation of some number of consecutive positive integers (2,3,4), then 451 is in the sequence.
%o A161001 (Python)
%o A161001 from itertools import groupby
%o A161001 def ok(n):
%o A161001   runlengths = [len(list(g)) for k, g in groupby(bin(n)[2:])]
%o A161001   minrl = min(runlengths)
%o A161001   return sorted(runlengths) == list(range(minrl, minrl+len(runlengths)))
%o A161001 print([n for n in range(1, 2021) if ok(n)]) # _Michael S. Branicky_, Jan 04 2021
%o A161001 (Python) # alternate that directly generates terms
%o A161001 from itertools import permutations
%o A161001 def runlengths(k, r): # all terms with runlengths a permutation of k, ..., r
%o A161001   c = ['1', '0']
%o A161001   return sorted([int("".join([c[j%2]*p[j] for j in range(r-k+1)]), 2)
%o A161001     for p in permutations(range(k, r+1))])
%o A161001 def aupto(nn):
%o A161001   digits, k, r, out = 1, 1, 1, []
%o A161001   while len(out) < nn:
%o A161001     for r in range(1, digits + 1):
%o A161001       for k in range(1, r + 1):
%o A161001         if sum(range(k, r+1)) == digits:
%o A161001           out += runlengths(k, r)
%o A161001     digits += 1
%o A161001   return sorted(set(out))[:nn]
%o A161001 print(aupto(56)) # _Michael S. Branicky_, Jan 04 2021
%Y A161001 Cf. A161000.
%K A161001 base,nonn
%O A161001 1,2
%A A161001 _Leroy Quet_, Jun 01 2009
%E A161001 Extended by _Ray Chandler_, Jun 13 2009