A114994 Numbers whose binary representation has monotonically decreasing sizes of groups of zeros (including zero-length groups between adjacent ones).

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

Offset: 0

Author

Franklin T. Adams-Watters, Feb 22 2006

Keywords

• nonn
• tabf
• easy

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 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.

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 "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.

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.

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)

Examples

			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 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.
-----------------------------------
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 (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}}.
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)
		

Links

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

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.

Programs

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

PARI

is(n, k=0)=if(n==0, return(1)); my(e=valuation(n, 2)); if(e>(e+1), e)) \\ Charles R Greathouse IV, Dec 05 2013

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