|
| |
|
|
A114994
|
|
Numbers whose binary representation has monotonically decreasing sizes of groups of zeros (including zero-length groups between adjacent ones).
|
|
109
|
|
|
|
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.)
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
|
|
|
|
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).
|
|
|
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].
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;
...
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)
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. also A227739, A227183 and permutation pair A229119/A229120 for another system of encoding unordered partitions in the binary representation of n.
|
|
|
KEYWORD
|
nonn,tabf,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
