|
%I #27 Jul 05 2014 14:09:43
%S 0,1,10,11,12,100,101,110,111,112,121,122,123,211,1000,1001,1010,1011,
%T 1012,1100,1101,1110,1111,1112,1121,1122,1123,1211,1212,1221,1222,
%U 1223,1232,1233,1234,1322,2111,2112,2121,2122,2123,2211,10000
%N Semigreedy Catalan Representation of nonnegative integers.
%C Algorithm for constructing the sequence: Define a(0) as 0, and for larger values of n, find first the largest Catalan number which is less than or equal to n [which is A081290(n)], and the index k = A244160(n), of that Catalan number. Initialize a vector of k zeros, [0, 0, ..., 0]. Set n_remaining = n - A000108(k) and add 1 to the leftmost element of vector, so that it will become [1, 0, ..., 0]. Then check whether the previous Catalan number, C(m) = A000108(m), where m = k-1, exceeds the n_remaining, and provided that C(m) <= n_remaining, then set n_remaining = n_remaining - C(m) and increment by one the m-th element of the vector (where the 1st element is the rightmost), otherwise just decrement m by one and keep on doing the same with lesser and lesser Catalan numbers, and whenever it is possible to subtract them from n_remaining (without going less than zero), do so and increment the corresponding m-th element of the vector, as long as either n_remaining becomes zero, or after subtracting C(1) = 1 from n_remaining, it still has not reached zero. In the latter case, find again the largest Catalan number which is less than or equal to n_remaining, and start the process again. However, after a finite number of such iterations, n_remaining will finally reach zero, and the result of a(n) is then the vector of numbers constructed, concatenated together and represented as a decimal number.
%C This shares with "Greedy Catalan Base" (A014418) the property that a simple weighted sum of Sum_{k=1..} digit(k)*C(k) recovers the natural number n, which the given numeral string like A014418(n) or here, a(n), represents. (Here C(k) = the k-th Catalan number, A000108(k), and digit(1) = the digit in the rightmost, least significant digit position.)
%C In this case, A244158(a(n)) = n holds for only up to 33603, after which comes the first representation containing a "digit" larger than nine, at a(33604), where the underlying string of numbers is [1,2,3,4,5,6,7,8,9,10] but the decimal system used here can no more unambiguously represent them.
%C On the other hand, with the given Scheme-functions, we always get n back with: (CatBaseSumVec (A244159raw n)).
%C For n >= 1, A014138(n) gives the positions of repunits: 1, 11, 111, 1111, ...
%C The "rep-2's": 22222, 222222, 2222222, 22222222, 222222222, ..., etc., occur in positions 128, 392, 1250, 4110, 13834, ... i.e. 2*A014138(n) for n >= 5.
%H Antti Karttunen, <a href="/A244159/b244159.txt">Table of n, a(n) for n = 0..33603</a>
%F If A176137(n) = 1, a(n) = A007088(A244230(n)), otherwise a(n) = A007088(A244230(n)-1) + a(n-A197433(A244230(n)-1)).
%F For all n, a(A197433(n)) = A007088(n).
%F For all n >= 1, a(A000108(n)) = 10^(n-1).
%F Each a(A014143(n)) has a "triangular" representation [1, 2, 3, ..., n, n+1].
%e For n = 18, the largest Catalan number <= 18 is C(4) = 14.
%e Thus we initialize a vector of four zeros [0, 0, 0, 0] and increment the first element to 1: [1, 0, 0, 0] and subtract 14 from 18 to get the remainder 4.
%e We see that the next smaller Catalan number, C(3) = 5 is greater than 4, so we cannot subtract it without going negative, so the second leftmost element of the vector stays as zero.
%e We next check C(2) = 2, which is less than 4, thus we increment the zero at that point to 1, and subtract 4 - 2 to get 2.
%e We compare 2 to C(1) = 1, and as 1 <= 2, it is subtracted 2-1 = 1, and the corresponding element in the vector incremented, thus after the first round, the vector is now [1, 0, 1, 1], and n remaining is 1.
%e So we start the second round because n has not yet reached the zero, and look for the largest Catalan number <= 1, which in this case is C(1) = 1, so we subtract it from remaining n, and increment the element in the position 1, after which n has reached zero, and the vector is now [1, 0, 1, 2], whose concatenation as decimal numbers thus yields a(18) = 1012.
%o (MIT/GNU Scheme, two alternative implementations)
%o ;; Version based on recurrence needs _Antti Karttunen_'s IntSeq-library for memoizing definec-macro:
%o (definec (A244159 n) (if (not (zero? (A176137 n))) (A007088 (A244230 n)) (+ (A007088 (-1+ (A244230 n))) (A244159 (- n (A197433 (-1+ (A244230 n))))))))
%o ;; The other version constructs a representation vector, used by some of the derived sequences:
%o (define (A244159 n) (basevec-as-decimal (A244159raw n)))
%o (define (A244159raw n) (if (zero? n) (make-vector 0) (let* ((maxsize (A244160 n)) (catbasevec (make-vector maxsize 0))) (let outer_loop ((n n)) (let inner_loop ((n n) (i (A244160 n))) (cond ((zero? n) (vector-reverse catbasevec)) ((zero? i) (outer_loop n)) ((<= (A000108 i) n) (begin (vector-set! catbasevec (- i 1) (+ 1 (vector-ref catbasevec (- i 1)))) (inner_loop (- n (A000108 i)) (- i 1)))) (else (inner_loop n (- i 1)))))))))
%o (define (basevec-as-decimal vec) (basevec->n 10 vec))
%o (define (basevec->n base bex) (let loop ((i 0) (n 0)) (cond ((= i (vector-length bex)) n) (else (loop (+ i 1) (+ (* n base) (vector-ref bex i)))))))
%o ;; Not needed for computing, but for demonstrating that the system works, as (CatBaseSumVec (A244159raw n)) = n for all n:
%o (define (CatBaseSumVec digits) (let ((size (vector-length digits))) (let loop ((i size) (s 0)) (if (zero? i) s (loop (- i 1) (+ s (* (vector-ref digits (- size i)) (A000108 i))))))))
%Y Cf. A014418 (a classical greedy variant), A244231 (maximum "digit value"), A244232 (sum of digits), A244233 (product of digits), A244314 (positive terms which have at least one zero digit), A244316 (the one-based position of digit incremented last in the described process).
%Y Cf. also A007088, A014138, A176137, A197433, A244230, A244158, A244160.
%Y Differs from A239903 for the first time at n=10, where a(10) = 121, while A239903(10) = 120.
%K nonn,base
%O 0,3
%A _Antti Karttunen_, Jun 23 2014
|
