login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A114994 Numbers whose binary representation has monotonically decreasing sizes of groups of zeros (including zero-length groups between adjacent ones). 54

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 22:35 EDT 2020. Contains 334756 sequences. (Running on oeis4.)