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