A229119 -id:A229119 - cp's OEIS frontend

A229120 Inverse of permutation A229119.

1, 3, 2, 7, 6, 5, 15, 14, 4, 13, 10, 31, 30, 12, 29, 9, 26, 21, 63, 62, 28, 61, 8, 25, 58, 11, 18, 53, 42, 127, 126, 60, 125, 24, 57, 122, 17, 27, 50, 117, 22, 37, 106, 85, 255, 254, 124, 253, 56, 121, 250, 16, 49, 59, 114, 245, 19, 34, 54, 101, 234, 20, 45, 74, 213, 170, 511, 510, 252, 509, 120, 249, 506, 48

Offset: 1

Wouter Meeussen, Sep 14 2013

nonn

Defines an infinite permutation on the integers, containing cycles of infinite length, but with an inverse (A229119) that can be generated.

The least integer producing an infinite cycle is n=4: {4, 7, 15, 29, 42, 37, 17, 26, 11, 10, 13, 30, 127, 77, 242, 266, 173, 205, 2034, 6474, ...}.

			See A229119.

Index entries for sequences related to permutations

Cf. A226062.

<< Combinatorica`; unrankpartition[n_Integer, k_Integer] := Block[{ove, res, qq, zz, mem}, ove=PartitionsP[n]-k; res={}; While[n-Tr[res]>0, qq=0; zz=0; While[(mem=NumberOfPartitions[n-Tr[res], qq + 1]) <= ove, zz = mem; qq++]; AppendTo[res, qq + 1]; ove = ove-zz]; res] /; k <= PartitionsP[n] && k > 0; unrankpartition[n_Integer,All]:=Block[{k=1,z},While[( z=Tr[PartitionsP[Range@k]])

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

Original entry on oeis.org

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

Franklin T. Adams-Watters, Feb 22 2006

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)

			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)

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

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.

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

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

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

A227183 a(n) is the sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n; row sums of A227739 for n >= 1.

Original entry on oeis.org

0, 1, 2, 2, 4, 3, 3, 3, 6, 5, 4, 6, 5, 4, 4, 4, 8, 7, 6, 8, 8, 5, 7, 9, 7, 6, 5, 7, 6, 5, 5, 5, 10, 9, 8, 10, 10, 7, 9, 11, 12, 9, 6, 10, 11, 8, 10, 12, 9, 8, 7, 9, 9, 6, 8, 10, 8, 7, 6, 8, 7, 6, 6, 6, 12, 11, 10, 12, 12, 9, 11, 13, 14, 11, 8, 12, 13, 10, 12, 14

Offset: 0

Antti Karttunen, Jul 05 2013

Like A129594 this sequence utilizes the fact that compositions (i.e., ordered partitions) can be bijectively mapped to (unordered) partitions by taking the partial sums of the list of composants after one has been subtracted from each except the first one. Compositions in turn are mapped to nonnegative integers via the runlength encoding, where the lengths of maximum runs of 0's or 1's in binary representation of n give the composants. See the OEIS Wiki page and the example below.

Each n occurs A000041(n) times in total and occurs for the first time at A227368(n) and for the last time at position A000225(n). See further comments and conjectures at A227368 and A227370.

			19 has binary expansion "10011", thus the maximal runs of identical bits (scanned from right to left) are [2,2,1]. We subtract one from each after the first one, to get [2,1,0] and then form their partial sums as [2,2+1,2+1+0], which thus maps to unordered partition {2+3+3} which adds to 8. Thus a(19)=8.

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen et al., Run-length encoding, OEIS Wiki.
Index entries for sequences related to partitions

Row sums of A227189 and A227739. Cf. A227184 (corresponding products), A227185, A227189, A227192, A129594, A226062, A227368.

Analogous sum sequences computed for other encoding schemes of unordered partitions: A036042, A056239, A161511, A243503. Cf. also A229119, A003188, A075157, A243353 (associated permutations mapping between these schemes).

Table[Function[b, Total@ Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b] - Boole[n == 0]]@ Map[Length, Split@ Reverse@ IntegerDigits[n, 2]], {n, 0, 79}] // Flatten (* Michael De Vlieger, May 09 2017 *)

def A227183(n):
  '''Sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n.'''
  s = 0
  b = n%2
  i = 1
  while (n != 0):
    n >>= 1
    if ((n%2) == b): # Staying in the same run of bits?
      i += 1
    else: # The run changes.
      b = n%2
      s += i
  return(s)

a(n) = Sum_{i=0..A005811(n)-1} A227189(n,i). [The defining formula]
Equivalently, for n>=1, a(n) = Sum_{i=(A173318(n-1)+1)..A173318(n)} A227739(i).
a(n) = A227192(n) - A000217(A005811(n)-1).
Other identities:
a(A129594(n)) = a(n). [This follows from the fact that conjugating a partition doesn't change its total sum]
a(A226062(n)) = a(n). [Which is also true for the "Bulgarian operation"]
From Antti Karttunen, Mar 08 2015: (Start)
Can be also obtained by mapping with an appropriate permutation from the sequences giving sizes of each partition (i.e., sum of their parts) computed for other enumerations similar to A227739:
a(n) = A036042(A229119(n)).
a(n) = A161511(A003188(n)).
a(n) = A056239(A243353(n)).
a(n) = A243503(1+A075157(n)).
(End)

cp's OEIS Frontend

A229120 Inverse of permutation A229119.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A227183 a(n) is the sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n; row sums of A227739 for n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula