cp's OEIS Frontend

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.

Sequence A227368 sorted into ascending order.

A pseudo-logarithmic function in the sense that a(b*c) = a(b)+a(c) and so a(b^c) = c*a(b) and f(n) = k^a(n) is a multiplicative function. [Cf. A248692 for example.] Essentially a function from the positive integers onto the partitions of the nonnegative integers (1->0, 2->1, 3->2, 4->1+1, 5->3, 6->1+2, etc.) so each value a(n) appears A000041(a(n)) times, first with the a(n)-th prime and last with the a(n)-th power of 2. Produces triangular numbers from primorials. - Henry Bottomley, Nov 22 2001

Michael Nyvang writes (May 08 2006) that the Danish composer Karl Aage Rasmussen discovered this sequence in the 1990's: it has excellent musical properties.

All A000041(a(n)) different n's with the same value a(n) are listed in row a(n) of triangle A215366. - Alois P. Heinz, Aug 09 2012

a(n) is the sum of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(33) = 7 because the partition with Heinz number 33 = 3 * 11 is [2,5]. - Emeric Deutsch, May 19 2015

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 (partition) sums of A125106.

a(n) is also the weight (= sum of parts) of the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 24 2017

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. (See table A227189 where the parts for each partition are listed).

The inverse process, from partitions to compositions, occurs by inserting the first (i.e. smallest) element of a partition sorted into ascending order to the front of the list obtained by adding one to the first differences of the elements.

Compositions map bijectively to nonnegative integers by assigning each run of k consecutive 1's (or 0's) in binary expansion of n with summand k in the composition.

The graph of this sequence is quite interesting.

For this sequence the partitions are encoded in the binary expansion of n in the same way as in A129594.

In "Bulgarian solitaire" a deck of cards or another finite set of objects is divided into one or more piles, and the "Bulgarian operation" is performed by taking one card from each pile, and making a new pile of them. The question originally posed was: on what condition the resulting partitions will eventually reach a fixed point, that is, a collection of piles that will be unchanged by the operation. See Martin Gardner reference and the Wikipedia-page.

A037481 gives the fixed points of this sequence, which are numbers that encode triangular partitions: 1 + 2 + 3 + ... + n.

A227752(n) tells how many times n occurs in this sequence, and A227753 gives the terms that do not occur here.

Of further interest: among each A000041(n) numbers j_i: j1, j2, ..., jk for which A227183(j_i)=n, how many cycles occur and what is the size of the largest one? (Both are 1 when n is in A000217, as then the fixed points are the only cycles.) Cf. A185700, A188160.

Also, A123975 answers how many Garden of Eden partitions there are for the deck of size n in Bulgarian Solitaire, corresponding to values that do not occur as the terms of this sequence.

Row n has A005811(n) elements. Each row contains a unique (unordered) partition of some integer, and all possible partitions of finite natural numbers eventually occur. The first partition that sums to k occurs at row A227368(k) and the last at row A000225(k).

Other similar tables of unordered partitions: A036036, A036037, A080576, A080577 and A112798.

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