A227368 a(n) = Index k where A227183(k) for the first time gets value n; the runlength binary code for minimally runlength-encoded unordered partition of size n.

0, 1, 2, 5, 4, 9, 8, 17, 16, 23, 32, 39, 40, 71, 72, 87, 80, 151, 144, 167, 160, 295, 288, 327, 320, 351, 576, 607, 640, 671, 672, 1183, 1184, 1311, 1312, 1375, 1344, 2399, 2368, 2655, 2624, 2719, 2688, 4767, 4736, 5279, 5248, 5407, 5376, 5503, 9472, 9599, 10496

Offset: 0

Author

Antti Karttunen, Jul 08 2013

Keywords

• nonn

Comments

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.

Examples

			   n   a(n)   binary   corresponding partition    sum = n
                       (cf. A227183 for details)
   0     0         0   (0)                          0
   1     1         1   (1)                          1
   2     2        10   (1 + 1)                      2
   3     5       101   (1 + 1 + 1)                  3
   4     4       100   (2 + 2)                      4
   5     9      1001   (1 + 2 + 2)                  5
   6     8      1000   (3 + 3)                      6
   7    17     10001   (1 + 3 + 3)                  7
   8    16     10000   (4 + 4)                      8
   9    23     10111   (3 + 3 + 3)                  9
  10    32    100000   (5 + 5)                     10
  11    39    100111   (3 + 4 + 4)                 11
  12    40    101000   (3 + 3 + 3 + 3)             12
  13    71   1000111   (3 + 5 + 5)                 13
  14    72   1001000   (3 + 3 + 4 + 4)             14
  15    87   1010111   (3 + 3 + 3 + 3 + 3)         15
  16    80   1010000   (4 + 4 + 4 + 4)             16
  17   151  10010111   (3 + 3 + 3 + 4 + 4)         17
  18   144  10010000   (4 + 4 + 5 + 5)             18
  19   167  10100111   (3 + 4 + 4 + 4 + 4)         19
  20   160  10100000   (5 + 5 + 5 + 5)             20
a(5) = 9, because 5 occurs for the first time in A227183 as A227183(9).
Note that for 20, there is for example also a code 175, "10101111" in binary, which results a partition (4 + 4 + 4 + 4 + 4) (= 20), but as 160 < 175, and there are no other partitions of 20 which would result even smaller code number, 160 is the winner (the minimal code), and thus a(20)=160.
A227761 gives the maximum difference between successive parts that occurs in these partitions.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..132
• Index entries for sequences related to partitions

Crossrefs

Same sequence sorted into ascending order: A227369.

Cf. also A227183, A227761, A227762.

Programs

Python

def A227368(n):
  '''Index k where A227183(k) for the first time gets value n. A naive implementation.'''
  k = 0
  while(A227183(k) != n): k += 1
  return(k)

Formula

a(n) = A227369(A227370(n)) [See comments and conjecture at A227370]