login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

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

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^(n-1), 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 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)

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. Adams-Watters, Feb 22 2006

STATUS

approved

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 December 16 04:05 EST 2019. Contains 330013 sequences. (Running on oeis4.)