cp's OEIS Frontend

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.

Note the indexing: the domain includes zero, but the range starts from one.

Note the indexing: the domain starts from one, but the range also includes zero.

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)

Row n has A005811(n) terms. In rows 2^(k-1)..2^k-1 we have all the compositions (ordered partitions) of k. Other orderings of compositions: A101211 (same with rows reversed), A066099, A108244 and A124734.

Each row n >= 1 contains the initial A005811(n) nonzero terms from the beginning of row n of A227186. A070939(n) gives the sum of terms on row n, while A167489(n) gives the product of its terms. A136480 gives the first column. A101211 lists the terms of each row in reverse order.

This can be calculated using the binary expansion of n; see the PARI program.

The n-th row consists of all partitions with hook size (maximum + number of parts - 1) equal to n.

The partitions in row n of this sequence are the conjugates of the partitions in row n of A125106 taken in reverse order.

Row n is also the reversed partial sums plus one of the n-th composition in standard order (A066099) minus one. - Gus Wiseman, Nov 07 2022

a(1) = 0 by convention (stands for an empty partition).

For n >= 2, A203623(n-1)+2 gives the index to the beginning of row n and for n>=1, A203623(n)+1 is the index to the end of row n.

a(0) = 1, as 0 is here considered to encode an empty partition {}, and the empty product is one.

Like A129594, this sequence is based on the fact that compositions (i.e., ordered partitions) can be mapped 1-to-1 to partitions by taking the partial sums of the list where one is subtracted from each composant except the first (originally explained by Marc LeBrun in his Jan 11 2006 post on SeqFan mailing list, with an additional twist involving factorization and prime exponents, cf. A129595). The example below show how this works.

Compare the scatterplot of this sequence to those of A002487, A243353, A243499 and A253552.

The word "minimally" in the description means that the integer in whose binary representation some unordered partition of n is encoded should be as small as possible. This sequence gives such a minimal integer for each n, which encodes an unordered partition whose sum is n. The details of the encoding system are explained in A227183.

Also, a(n) gives the index of the first row of A227189/A227739 which sums to n.

Project: Find an algorithm which computes a(n) with a more sophisticated method than just by a blind search. This is a kind of an optimization problem for representing n as a special "bit-packed" sum: the smallest summand of size x costs x bits, and its any subsequent usage in the sum costs just one bit each time. Using any additional summand y > x costs (y-x)+1 bits when used first time, and then again additional usages cost only one bit each. Goal: minimize the number of bits needed. If multiple candidates with the same number of bits are found, then the one which results the smallest integer (when interpreted as a binary number) wins.

For any composite n = t*u, the upper bound for the size of a(n) is t+u-1 bits.

A000267(n) seems to give the binary width of a(n+1). Compare to the conjecture given at A227370.

Discarding the trailing zero terms, on each row n there is a unique partition of integer A227183(n). All possible partitions of finite natural numbers eventually occur. The first partition that sums to n occurs at row A227368(n).

Irregular table A227739 lists only the nonzero terms.