

A114994


Numbers whose binary representation has monotonically decreasing sizes of groups of zeros (including zerolength groups between adjacent ones).


16



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, 42, 43, 47, 63, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 79, 85, 87, 95, 127, 128, 129, 130, 131, 132, 133, 135, 136, 137, 138, 139, 143, 146, 147, 149, 151, 159, 170, 171, 175
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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.)
From Vladimir Shevelev, Dec 09 2013: (Start)
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 cmultiplication [*] 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.
The sequence lists equivalence classes of integers, choosing the minimal representative in each.
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 "cprimes". Then every term is a unique "cproduct" of "cpowers" of cprimes. For example, 7=(1)^3, 10=(10)^2, etc.
Further, one can naturally introduce "cnotions": cdivisor, cdivisibility, greatest common cdivisor of several numbers and least common cmultiple, Euler ctotient function (with notion of "r is cprime to m"), etc.
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.
(End)


LINKS

Peter J. C. Moses, Table of n, a(n) for n = 0..4999


FORMULA

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).
Number terms in interval [2^(n1), 2^n) is A000041(n); number terms <2^n is A000070(n).  Vladimir Shevelev, Dec 06 2013


EXAMPLE

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.
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].
From Omar E. Pol, Aug 04 2013: (Start)
The positive terms written as an irregular triangle begins:
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, 42, 43, 47, 63;
64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 79, 85, 87, 95, 127;
...
Column 1 is A000079. Right border gives A000225, n >= 1.
T(n,k) represents the kth 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.

Partitions Binary Decimal
of 5 number value

5 10000 16
4+1 10001 17
3+2 10010 18
3+1+1 10011 19
2+2+1 10101 21
2+1+1+1 10111 23
1+1+1+1+1 11111 31
(End)
From Peter J. C. Moses, Dec 09 2013: (Start)
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}}.
Now for every number, i, replace it with 1 followed by (i1) 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}}.
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}.
(End)


MATHEMATICA

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 *)
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 *)


PROG

(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


CROSSREFS

Cf. A004743, A080577, A000041, A232897, A233027, A000070.
Cf. also A227739, A227183 and permutation pair A229119/A229120 for another system of encoding unordered partitions in the binary representation of n.
Sequence in context: A324845 A107686 A004743 * A137706 A324766 A039224
Adjacent sequences: A114991 A114992 A114993 * A114995 A114996 A114997


KEYWORD

nonn,tabf,easy


AUTHOR

Franklin T. AdamsWatters, Feb 22 2006


STATUS

approved



