A175061 A positive integer n is included if n, when written in binary, is made of run-lengths (lengths of runs of 0's as well as of runs of 1's) that form a permutation of some number of consecutive positive integers starting with 1.

1, 4, 6, 35, 39, 49, 55, 57, 59, 536, 540, 560, 572, 624, 632, 776, 782, 784, 798, 880, 888, 900, 902, 912, 926, 944, 956, 964, 966, 968, 974, 984, 988, 16775, 16783, 16835, 16847, 16867, 16871, 17159, 17183, 17283, 17311, 17379, 17383, 17935, 17951

Offset: 1

Author

Leroy Quet, Dec 12 2009

Keywords

• base
• nonn

Comments

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.

This sequence contains those terms of A161001 that each contain a run of length 1.

Examples

			536 in binary is 1000011000. This contains a run of one 1, followed by a run of four 0's, followed by a run of two 1's, followed finally by a run of three 0's. So the run lengths are (1,4,2,3). And since this is a permutation of (1,2,3,4), then 536 is in the sequence.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A161001, A175062

Programs

Python

from itertools import groupby
def ok(n):
  runlengths = [len(list(g)) for k, g in groupby(bin(n)[2:])]
  return sorted(runlengths) == list(range(1, len(runlengths)+1))
print([n for n in range(1, 17952) if ok(n)]) # Michael S. Branicky, Jan 04 2021

Python

# alternate that directly generates terms
from itertools import permutations
def runlength(r): # all terms with runlengths a permutation of 1, ..., r
  c = ['1', '0']
  return sorted([int("".join([c[j%2]*p[j] for j in range(r)]), 2)
    for p in permutations(range(1, r+1))])
def aupto(nn):
  r, out = 1, []
  while len(out) < nn:
    out += runlength(r)
    r += 1
  return out[:nn]
print(aupto(47)) # Michael S. Branicky, Jan 04 2021

Extensions

Extended by Ray Chandler, Dec 16 2009