cp's OEIS Frontend

For n >= 1, a(n) is the total number of ways the natural numbers in range 1 .. n can be represented as sums of distinct Catalan numbers (A000108). Note that for any one number, number of such solutions may be at most one. In other words, this sequence is one less than the partial sums of A176137 (number of partitions of n into distinct Catalan numbers).

For n >= 1, a(n) tells the one-based position of the digit (from the right) where the iteration stopped at, when constructing a Semigreedy Catalan representation of n as described in A244159.

Algorithm for constructing the sequence: Find the largest Catalan number which is less than or equal to n (this is A081290(n) = A000108(k), where k = A244160(n), that is, the corresponding index of that Catalan number), and subtract that from n. Then check whether the previous Catalan number, C(m) = A000108(m), where m = k-1, exceeds the remaining n, and if it does not, then subtract that also from n, and keep on doing the same for lesser and lesser Catalan numbers, comparing and also subtracting them (whenever it is possible without going less than zero) from n, until either n becomes zero, or after subtracting C(1) = 1 from n, it still has not reached zero. In the latter case, find again the largest Catalan number which is less than or equal to remaining n, and start the process again. However, when at some point n finally reaches zero, then the index k of the last Catalan number, A000108(k) which was subtracted from n before it reached zero, is our result, a(n) = k. [Here n = the original value of n, from which we started subtracting initially from].

If n is one of the terms of A197433, meaning that if it can be represented as a sum of distinct Catalan numbers as n = C(i) + C(j) + ... + C(k) (which representation then necessarily is unique), then a(n) = min(i,j,...,k).

For n >= 1, a(n) tells the zero-based position of the digit (from the right) where the iteration stopped at, when constructing a Semigreedy Catalan representation of n as described in A244159.

Numbers that are sums of distinct factorials (0! and 1! not treated as distinct).

Complement of A115945; A115944(a(n)) > 0; A115647 is a subsequence. - Reinhard Zumkeller, Feb 02 2006

A115944(a(n)) = 1. - Reinhard Zumkeller, Dec 04 2011

From Tilman Piesk, Jun 04 2012: (Start)

The inversion vector (compare A007623) of finite permutation a(n) (compare A055089, A195663) has only zeros and ones. Interpreted as a binary number it is 2*n (or n when the inversion vector is defined without the leading 0).

The inversion set of finite permutation a(n) interpreted as a binary number (compare A211362) is A211364(n).

(End)

From Antti Karttunen, Jun 22 2014: (Start)

Also called "Greedy Catalan Base" for short.

Note: unlike A239903, this is a true base system, thus A244158(a(n)) = n holds for all n. See also A244159 for another, "less greedy" Catalan Base number system.

No digits larger than 3 will ever appear, because C(n+1)/C(n) approaches 4 from below, but never reaches it. [Where C(n) is the n-th Catalan number, A000108(n)].

3-digits cannot appear earlier than at the fifth digit-position from the right, the first example being a(126) = 30000.

The last digit is always either 0 or 1. (Cf. the sequences A244222 and A244223 which give the corresponding k for "even" and "odd" representations). No term ends as ...21.

No two "odd" terms (ending with 1) may occur consecutively.

A244217 gives the k for which a(k) starts with the digit 1, while A244216 gives the k for which a(k) starts with the digit 2 or 3.

A000108(n+1) gives the position of numeral where 1 is followed by n zeros.

A014138 gives the positions of repunits.

A197433 gives such k that a(k) = A239903(k). [Actually, such k, that the underlying strings of digits/numbers are same].

For the explanations, see the attached notes.

(End)

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.

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.)

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.

On the other hand, with the given Scheme-functions, we always get n back with: (CatBaseSumVec (A244159raw n)).

For n >= 1, A014138(n) gives the positions of repunits: 1, 11, 111, 1111, ...

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.

a(n) <= 1;

a(A000108(n)) = 1; a(A141351(n)) = 1; a(A014138(n)) = 1.

A197433 gives all such numbers k that a(k) = 1, in other words, this is the characteristic function of A197433, and all three sequences mentioned above are its subsequences. - Antti Karttunen, Jun 25 2014

This sequence converts any number from various "Catalan Base number systems" (when represented as decimal numbers) back to the integer the numeral represents: e.g. we have a(A014418(n)) = n and a(A244159(n)) = n (except for the latter this is eventually broken by the shortcomings of the decimal representation used, while for the former it works for all n, because no digits larger than 3 will ever appear in the terms of A014418).

A197433 is similar, but replaces 2^k with A000108(k+1) in binary expansion of n.

For 1- and 2-digit numbers the same as A156230. - R. J. Mathar, Jun 27 2014

In range 0 .. 58784, these are numbers k such that A244158(A239903(n)) = k. (see comments at A244157).

Note that a(33604) = A000217(10) = 55 because the sum is computed from the underlying list (vector) of numbers, and thus is not subject to any corruption by decimal representation as A244159 itself is.

Equivalent description: partition n "greedily" as terms of A197433, i.e. n = A197433(i) + A197433(j) + ... + A197433(k), always using the largest term of A197433 that still "fits in" (i.e. is <= n remaining). Then a(n) = A000120(i) + A000120(j) + ... + A000120(k).