login
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.
10

%I #40 Aug 18 2013 02:40:47

%S 0,1,2,5,4,9,8,17,16,23,32,39,40,71,72,87,80,151,144,167,160,295,288,

%T 327,320,351,576,607,640,671,672,1183,1184,1311,1312,1375,1344,2399,

%U 2368,2655,2624,2719,2688,4767,4736,5279,5248,5407,5376,5503,9472,9599,10496

%N 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.

%C 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.

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

%C 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.

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

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

%H Antti Karttunen, <a href="/A227368/b227368.txt">Table of n, a(n) for n = 0..132</a>

%H <a href="/index/Par#part">Index entries for sequences related to partitions</a>

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

%e n a(n) binary corresponding partition sum = n

%e (cf. A227183 for details)

%e 0 0 0 (0) 0

%e 1 1 1 (1) 1

%e 2 2 10 (1 + 1) 2

%e 3 5 101 (1 + 1 + 1) 3

%e 4 4 100 (2 + 2) 4

%e 5 9 1001 (1 + 2 + 2) 5

%e 6 8 1000 (3 + 3) 6

%e 7 17 10001 (1 + 3 + 3) 7

%e 8 16 10000 (4 + 4) 8

%e 9 23 10111 (3 + 3 + 3) 9

%e 10 32 100000 (5 + 5) 10

%e 11 39 100111 (3 + 4 + 4) 11

%e 12 40 101000 (3 + 3 + 3 + 3) 12

%e 13 71 1000111 (3 + 5 + 5) 13

%e 14 72 1001000 (3 + 3 + 4 + 4) 14

%e 15 87 1010111 (3 + 3 + 3 + 3 + 3) 15

%e 16 80 1010000 (4 + 4 + 4 + 4) 16

%e 17 151 10010111 (3 + 3 + 3 + 4 + 4) 17

%e 18 144 10010000 (4 + 4 + 5 + 5) 18

%e 19 167 10100111 (3 + 4 + 4 + 4 + 4) 19

%e 20 160 10100000 (5 + 5 + 5 + 5) 20

%e a(5) = 9, because 5 occurs for the first time in A227183 as A227183(9).

%e 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.

%e A227761 gives the maximum difference between successive parts that occurs in these partitions.

%o (Scheme, with _Antti Karttunen_'s IntSeq-library)

%o (define A227368 (LEAST-I-WITH-FUN-I-EQ-N 0 0 A227183))

%o (Python)

%o def A227368(n):

%o '''Index k where A227183(k) for the first time gets value n. A naive implementation.'''

%o k = 0

%o while(A227183(k) != n): k += 1

%o return(k)

%Y Same sequence sorted into ascending order: A227369.

%Y Cf. also A227183, A227761, A227762.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jul 08 2013