%I #43 Apr 20 2017 15:10:26
%S 0,1,2,3,4,5,7,8,9,10,11,15,16,17,18,19,21,23,31,32,33,34,35,36,37,39,
%T 42,43,47,63,64,65,66,67,68,69,71,73,74,75,79,85,87,95,127,128,129,
%U 130,131,132,133,135,136,137,138,139,143,146,147,149,151,159,170,171,175
%N Numbers whose binary representation has monotonically decreasing sizes of groups of zeros (including zero-length groups between adjacent ones).
%C Numbers whose binary representation avoids the sequences 110, 10100, 1001000, etc. Represents partitions. Start with empty partition and process each bit from left to right: if a zero, increase the size of the smallest part; if one, add a new size 1 part. This generates the partitions in Mathematica order. Can be regarded as a table with row lengths A000041(n); values 2^n <= a(m) < 2^(n+1) are in row n, representing the partitions of n. (Interpreting arbitrary binary numbers in this way generates compositions [also known as ordered partitions]; these are the compositions where the part sizes are in decreasing order of size.)
%C From _Vladimir Shevelev_, Dec 09 2013: (Start)
%C Every number in binary is a concatenation of parts of the form 10...0 with k>=0 zeros. For example, 5=(10)(1), 11=(10)(1)(1), 7=(1)(1)(1). Define c-multiplication [*] by adding multiplicities of parts (ordering by nonincreasing numbers of 0's). For example, 5[*]3=(10)(1)(1)(1)=23. Two numbers we call equivalent if they have the same parts with the same multiplicities. So 6~5, 12~9, 14~13~11.
%C The sequence lists equivalence classes of integers, choosing the minimal representative in each.
%C Note that, for two terms x,y we have x[*]y=y[*]x (commutativity), and for three terms x,y,z we have x[*](y[*]z)= (x[*]y)[*]z (associativity). 0 is the unit, i.e., 0[*]x=x. Moreover, one can consider different parts, i.e., {2^n} as "c-primes". Then every term is a unique "c-product" of "c-powers" of c-primes. For example, 7=(1)^3, 10=(10)^2, etc.
%C Further, one can naturally introduce "c-notions": c-divisor, c-divisibility, greatest common c-divisor of several numbers and least common c-multiple, Euler c-totient function (with notion of "r is c-prime to m"), etc.
%C Let x[+]y denote usual sum x+y in which we order parts over nonincreasing number of zeros. Then, of course, A114994 is closed over such operation. Then a(n+1) = a(n)[+]k, where k is the least number such that a(n)[+]k > a(n). For example, since a(10)=11, we have 11[+]1=9, 11[+]2=11, 11[+]3=11, 11[+]4=15>11. So, a(11)=15.
%C (End)
%H Peter J. C. Moses, <a href="/A114994/b114994.txt">Table of n, a(n) for n = 0..4999</a>
%F For n>=0, 2n+1 is in the sequence iff n is in the sequence. For n>0, 2n is in the sequence iff both n is the sequence and, for some k>=0, n is congruent to 2^k mod 4^(k+1).
%F Number terms in interval [2^(n-1), 2^n) is A000041(n); number terms <2^n is A000070(n). - _Vladimir Shevelev_, Dec 06 2013
%e 21 is included, binary 10101 has group sizes 1,1,0; 22 is not, binary 10110 has group sizes 1,0,1, which includes an increase.
%e Applying bits of 21 in order gives sequence of partitions: [], [1], [2], [2,1], [2^2], [2^2,1], so 21 represents the partition [2^2,1].
%e From _Omar E. Pol_, Aug 04 2013: (Start)
%e The positive terms written as an irregular triangle begins:
%e 1;
%e 2, 3;
%e 4, 5, 7;
%e 8, 9, 10, 11, 15;
%e 16, 17, 18, 19, 21, 23, 31;
%e 32, 33, 34, 35, 36, 37, 39, 42, 43, 47, 63;
%e 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 79, 85, 87, 95, 127;
%e ...
%e Column 1 is A000079. Right border gives A000225, n >= 1.
%e T(n,k) represents the k-th partition of n. Example: for n = 5 the seven partitions of 5 (in Mathematica order) are represented in three ways as shown below. The last column (16, 17, 18, 19, 21, 23, 31) is also the 5th row of triangle.
%e -----------------------------------
%e Partitions Binary Decimal
%e of 5 number value
%e -----------------------------------
%e 5 10000 16
%e 4+1 10001 17
%e 3+2 10010 18
%e 3+1+1 10011 19
%e 2+2+1 10101 21
%e 2+1+1+1 10111 23
%e 1+1+1+1+1 11111 31
%e (End)
%e From _Peter J. C. Moses_, Dec 09 2013: (Start)
%e Let us illustrate an algorithm of calculation of all terms in interval of the form [2^k,2^(k+1)). Let k=5. Consider all integer partitions of 5+1=6 ordered over decreasing of maximal parts (see algorithm IntegerPartitions). We have: {{6},{5,1},{4,2},{4,1,1},{3,3},{3,2,1},{3,1,1,1},{2,2,2},{2,2,1,1},{2,1,1,1,1},{1,1,1,1,1,1}}.
%e Now for every number, i, replace it with 1 followed by (i-1) 0's. So that becomes: {{1,0,0,0,0,0},{1,0,0,0,0,1},{1,0,0,0,1,0},{1,0,0,0,1,1},{1,0,0,1,0,0},{1,0,0,1,0,1},{1,0,0,1,1,1},{1,0,1,0,1,0},{1,0,1,0,1,1},{1,0,1,1,1,1},{1,1,1,1,1,1}}.
%e Finally, reading these as binary numbers with transformation of them into decimal, we obtain all terms in interval [32,64): {32,33,34,35,36,37,39,42,43,47,63}.
%e (End)
%t Select[Range[0, 200], FromDigits[Flatten[Sort[Split[IntegerDigits[#, 2], #1>#2||#2==0&], Length[#1]>Length[#2]&]], 2]==#&] (* _Peter J. C. Moses_, Dec 04 2013 *)
%t f:=Map[IntegerDigits[2^(#-1), 2]&, #]&; Flatten[Map[Map[FromDigits[#, 2]&, Map[Flatten, f[IntegerPartitions[#]]]]&, Range[0, 10]]] (* _Peter J. C. Moses_, Dec 05 2013 *)
%o (PARI) is(n, k=0)=if(n==0, return(1)); my(e=valuation(n, 2)); if(e<k, 0, is(n>>(e+1), e)) \\ _Charles R Greathouse IV_, Dec 05 2013
%Y Cf. A004743, A080577, A000041, A232897, A233027, A000070.
%Y Cf. also A227739, A227183 and permutation pair A229119/A229120 for another system of encoding unordered partitions in the binary representation of n.
%K nonn,tabf,easy
%O 0,3
%A _Franklin T. Adams-Watters_, Feb 22 2006