cp's OEIS Frontend

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.

%I A227368 #40 Aug 18 2013 02:40:47
%S A227368 0,1,2,5,4,9,8,17,16,23,32,39,40,71,72,87,80,151,144,167,160,295,288,
%T A227368 327,320,351,576,607,640,671,672,1183,1184,1311,1312,1375,1344,2399,
%U A227368 2368,2655,2624,2719,2688,4767,4736,5279,5248,5407,5376,5503,9472,9599,10496
%N 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.
%C A227368 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 A227368 Also, a(n) gives the index of the first row of A227189/A227739 which sums to n.
%C A227368 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 A227368 For any composite n = t*u, the upper bound for the size of a(n) is t+u-1 bits.
%C A227368 A000267(n) seems to give the binary width of a(n+1). Compare to the conjecture given at A227370.
%H A227368 Antti Karttunen, <a href="/A227368/b227368.txt">Table of n, a(n) for n = 0..132</a>
%H A227368 <a href="/index/Par#part">Index entries for sequences related to partitions</a>
%F A227368 a(n) = A227369(A227370(n)) [See comments and conjecture at A227370]
%e A227368    n   a(n)   binary   corresponding partition    sum = n
%e A227368                        (cf. A227183 for details)
%e A227368    0     0         0   (0)                          0
%e A227368    1     1         1   (1)                          1
%e A227368    2     2        10   (1 + 1)                      2
%e A227368    3     5       101   (1 + 1 + 1)                  3
%e A227368    4     4       100   (2 + 2)                      4
%e A227368    5     9      1001   (1 + 2 + 2)                  5
%e A227368    6     8      1000   (3 + 3)                      6
%e A227368    7    17     10001   (1 + 3 + 3)                  7
%e A227368    8    16     10000   (4 + 4)                      8
%e A227368    9    23     10111   (3 + 3 + 3)                  9
%e A227368   10    32    100000   (5 + 5)                     10
%e A227368   11    39    100111   (3 + 4 + 4)                 11
%e A227368   12    40    101000   (3 + 3 + 3 + 3)             12
%e A227368   13    71   1000111   (3 + 5 + 5)                 13
%e A227368   14    72   1001000   (3 + 3 + 4 + 4)             14
%e A227368   15    87   1010111   (3 + 3 + 3 + 3 + 3)         15
%e A227368   16    80   1010000   (4 + 4 + 4 + 4)             16
%e A227368   17   151  10010111   (3 + 3 + 3 + 4 + 4)         17
%e A227368   18   144  10010000   (4 + 4 + 5 + 5)             18
%e A227368   19   167  10100111   (3 + 4 + 4 + 4 + 4)         19
%e A227368   20   160  10100000   (5 + 5 + 5 + 5)             20
%e A227368 a(5) = 9, because 5 occurs for the first time in A227183 as A227183(9).
%e A227368 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 A227368 A227761 gives the maximum difference between successive parts that occurs in these partitions.
%o A227368 (Scheme, with _Antti Karttunen_'s IntSeq-library)
%o A227368 (define A227368 (LEAST-I-WITH-FUN-I-EQ-N 0 0 A227183))
%o A227368 (Python)
%o A227368 def A227368(n):
%o A227368   '''Index k where A227183(k) for the first time gets value n. A naive implementation.'''
%o A227368   k = 0
%o A227368   while(A227183(k) != n): k += 1
%o A227368   return(k)
%Y A227368 Same sequence sorted into ascending order: A227369.
%Y A227368 Cf. also A227183, A227761, A227762.
%K A227368 nonn
%O A227368 0,3
%A A227368 _Antti Karttunen_, Jul 08 2013