login
Positive integers that contain only odd-length runs of 0's and 1's in their binary expansion.
2

%I #32 Jan 04 2021 04:08:56

%S 1,2,5,7,8,10,14,17,21,23,29,31,32,34,40,42,46,56,58,62,65,69,71,81,

%T 85,87,93,95,113,117,119,125,127,128,130,136,138,142,160,162,168,170,

%U 174,184,186,190,224,226,232,234,238,248,250,254,257,261,263,273,277,279

%N Positive integers that contain only odd-length runs of 0's and 1's in their binary expansion.

%C Let the binary representation of n be thought of as a string of 0's and 1's. By a "run" of 0's or 1's, it is meant either a contiguous substring all of 0's bounded by 1's or the by the edge of the string, or a contiguous substring all of 1's bounded by 0's or the by the edge of the string.

%C Also, the indices of the compositions that have only odd parts. For the definition of the index of a composition see A298644. For example, 263 is in the sequence since its binary form is 100000111 and the composition [1,5,3] has only odd parts. 132 is not in the sequence since its binary form is 10000100 and the composition [1,4,1,2] also has even parts. The command c(n) from the Maple program yields the composition having index n. - _Emeric Deutsch_, Jan 26 2018

%C From _Robert Israel_, Jan 26 2018: (Start)

%C An even number n is in the sequence if and only if n = 2^k*m where k is odd and m is an odd number in the sequence.

%C An odd number n is in the sequence if and only if n = 2^k*(m+1)-1 where k is odd and m is 0 or an even number in the sequence. (End)

%H Ivan Neretin, <a href="/A160530/b160530.txt">Table of n, a(n) for n = 1..10000</a>

%p Runs := proc (L) local j, r, i, k: j := 1; r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: A := {}: for n to 280 do if type(product(c(n)[j], j = 1 .. nops(c(n))), odd) = true then A := `union`(A, {n}) else end if end do: A; # most of the Maple program is due to _W. Edwin Clark._ - _Emeric Deutsch_, Jan 26 2018

%p # Alternative:

%p filter:= proc(n) option remember; local t;

%p if n::even then

%p t:= padic:-ordp(n,2);

%p if t::even then return false fi;

%p procname(n/2^t)

%p else

%p t:= padic:-ordp(n+1,2);

%p if t::even then return false fi;

%p procname((n+1)/2^t-1)

%p fi

%p end proc:

%p filter(0):= true:

%p select(filter, [$1..1000]); # _Robert Israel_, Jan 26 2018

%t Select[Range[300],And@@OddQ/@Length/@Split[IntegerDigits[ #,2]]&] (* _Ray Chandler_, May 19 2009 *)

%o (Python)

%o from itertools import groupby

%o def ok(n): return all(len(list(g))%2 == 1 for k, g in groupby(bin(n)[2:]))

%o print([i for i in range(1, 280) if ok(i)]) # _Michael S. Branicky_, Jan 04 2021

%Y Cf. A001196, A160531, A298644.

%K base,nonn

%O 1,2

%A _Leroy Quet_, May 17 2009

%E Extended by _Ray Chandler_, May 19 2009